20
$\begingroup$

Is that true that all the prime numbers are of the form $6m \pm 1$ ?

If so, can you please provide an example?

Thanks in advance.

  • 2
    See also http://math.stackexchange.com/questions/27883/is-it-true-that-all-senary-numbers-ending-in-1-and-5-are-primes2011-05-27

7 Answers 7

37

This is true of all prime numbers except for $2$ and $3$. The reason is that numbers with remainders $0$, $2$ and $4$ modulo $6$ are divisible by $2$, and numbers with remainders $0$ and $3$ modulo $6$ are divisible by $3$, so other than $2$ and $3$ themselves, all prime numbers must have remainder $1$ or $5$ modulo $6$.

  • 0
    even for 2 and 3 we have 2 modulo 6 = 2 and 3 modulo 6 = 3 but that we can't generate them with this formula2011-05-27
  • 0
    @oussama: Yes, this is what I was trying to say: $2$ and $3$ are primes, but you can't generate them with this formula, since their remainders modulo $6$ are $2$ and $3$, respectively, not $1$ or $5$. A number divisible by $2$ or $3$ can only be prime if it is $2$ or $3$, since otherwise it would be divisible by a number other than itself.2011-05-27
  • 0
    can we use a bigger number than 6 (that verify this propriety) to generate prime numbers in a faster way. sorry for my english2011-05-30
  • 5
    @oussama: You can do the same thing with any number; for each natural number $n$, primes (except for the prime factors of $n$ themselves) can only have remainders modulo $n$ that are coprime to $n$. For instance, all primes except $3$ and $5$ have remainder $1$, $2$, $4$, $7$, $11$, $13$ or $14$ modulo $15$.2011-05-31
  • 4
    @tatan That edit is far too drastic.2016-05-21
  • 4
    @tatan: I agree; I reverted it. Regarding your question, please see the comment right above it.2016-05-21
  • 0
    From your answer I understand that $6k+1$ or $6k+5$ is a prime...but it is not always true....if $k=4$,$6k+1=25$ which is composite...what about that?2016-05-21
  • 1
    @tatan: No, you had edited the claim that $6k+1$ and $6k+5$ are prime into the answer; I took it out again. The question and the answer are about the converse claim that all primes (except two exceptions) are of the form $6k+1$ or $6k+5$.2016-05-21
  • 0
    @joriki Its about proving primes are in $6k\pm 1$ form and not that $6k\pm 1$ are primes....2016-05-21
  • 2
    @tatan May I advise you to use your edit privileges with MUCH MORE restraint, in the future? Thanks in advance.2016-05-21
18

The classes $1$ and $5$ are the two reduced residue classes modulo $6$, i.e., they are the congruence classes modulo $6$ which are relatively prime to $6$. Any sufficiently large prime number has to lie in one of these reduced residue classes, since otherwise it would share a common factor with $6$. In this case it is pretty clear that "sufficiently large" means any prime $p \geq 5$.

More generally, let $d$ be any positive integer. Then by the same reasoning all but finitely many primes must lie in one of the $\varphi(d)$ reduced residue classes modulo $d$. Since there are $d$ residue classes modulo $d$ in all, this shows that the "probability" that a large number is prime is at most $\frac{\varphi(d)}{d}$. It is not hard to show that for all $\epsilon > 0$, there exists $N \in \mathbb{Z}^+$ such that $\frac{\varphi(N)}{N} < \epsilon$. This shows that the "probability that a large number is prime" is zero -- or, when this probability business is made rigorous by recasting it in terms of density -- that the prime numbers have zero density inside the positive integers:

$\lim_{n \rightarrow \infty} \frac{ \pi(n)}{n} = 0$.

(This is a weak consequence of the Prime Number Theorem, but as we saw, one certainly need not know PNT in order to prove it.)

This argument is given in $\S 3$ of these notes from an undergraduate number theory course. The argument seems not to be entirely standard, but I think it is an appealingly direct way to show that the primes have density zero. There is also a funny irony here in that the way to see the above claim about the $\varphi$ function is to take $N = p_1 \cdots p_k$ for large $k$ (the argument is given in $\S 3$ of this other handout). Thus, in order to show that the primes have density zero, we are using the fact that there are infinitely many of them. Well, if we happened not to know that, then we would divide the proof into two cases: in case there were only finitely many primes, their density would clearly be zero!

  • 0
    Did you mean for all $\epsilon >0$, there exists $N \in \mathbb{Z}^{+}$ such that $\frac{\phi(N)}{N} < \epsilon$?2016-05-21
7

All integers $n\ge 3$ take one of these forms

$$6k,6k\pm 1,6k\pm 2=2\left( 3k\pm 1\right) ,6k\pm 3=3(2k\pm 1),\qquad k=1,2,3,\dots$$

where $6$ is the product of the first two primes ($2$ and $3$). Since $6k,6k\pm 2,6k\pm 3$ are not primes, we are left with $p=6k\pm 1$. So, all primes $p>3$ are of the form $$6k\pm 1\qquad k=1,2,3,\dots .$$

Added: as examples (asked for in the edited question), we can take the prime number $17$, which is of the form $17=6k-1=6\cdot 3-1$ and the prime number $31$, of the form $31=6k+1=6\cdot 5+1$.


Taking the product of the first three primes $30=2\cdot 3\cdot 5$ this argument generalizes immediately to

$$p=30k\pm r,\qquad p\geq 13,$$

with $r=1,7,11,13$.

And by an easier argument we could also prove that if a positive integer is not of the form $4k\pm 1$, ($k=1,2,3,\dots$), then it is not a prime.


This generalizes the

Proposition. If a number $p>2$ is a prime, then

$$p=4k\pm 1.$$

  • 0
    @Américo: You forgot 1 and 29.2011-05-27
  • 0
    @TonyK: $17$ and $31$ were given as *examples* of primes $p>3$ which satisfy $p=6k\pm 1$.2011-05-27
  • 0
    Américo: what Tony is referring to is your statement about primes of the form p=30k+-r - you forgot r=1 in your list of residue classes mod 30...2011-05-27
  • 0
    @Steven, @TonyK: Thanks! That's right. Corrected.2011-05-27
  • 0
    @Américo: Perhaps remove $17$ too, to avoid redundancy...2011-05-29
  • 0
    @TonyK: Thanks again! (corrected).2011-05-29
3

Your question could be formally written as

Every prime number is an adjacent of multiple of six with two exceptions ($2,3$).

Which is a well known result.


Here goes an elementary proof

For any integer $n$ write $$ n=6q+r, \qquad \mbox{where } q\in \Bbb Z^+ \mbox{ and } r=\{0,1,2,3,4,5\}$$ If $r=\{0,2,4\}$, then $2|n$ and $n$ can't be prime.

If $r=3$, then $3|n$ again $n$ can't be prime.

So if $n$ is a prime the remainder $r$ is either $1$ or $5$.

1

We know that every integer has one of the forms 6K+r, with 0 ≤ r < 6. Other than 2, each integer of the form 6K, 6K+2 or 6K+4 has a proper factor 2. Other than 3, each integer of the form 6K or 6K+3 has a proper factor 3. Thus, any prime other than 2, 3 has one of the forms 6K+1, 6K+5. Numbers of the latter type can be rewritten as 6L-1, where L = K-1.

0

In fact, more is true. The primes are equally distributed between these two residue classes, as per the stronger version of the Dirichlet's theorem on arithmetic progressions -- a prominent theorem in analytic number theory.

More generally, given any positive integer $N$, the primes are equally distributed among the residue classes that are relatively prime to $N$. In the case of $N =6$, your surprise arises because there are only two such residue classes: $\pm 1$. The same is true for $N =4$ and might be less surprising for you there.

0

Let $A = \{2n \, | \, n \ge 2\}$.

Let $B = \{3n \, | \, n \ge 2\}$.

Let $C = \{n \in \Bbb N \, | \, n \ge 2 \} \setminus (A \cup B)$.

It is evident that any prime number must belong to the set $C$ (c.f. the Sieve of Eratosthenes).

For $-4 \le k \le 1$ let $D_k = \{6n + k \, | \, n \ge 1\}$. It follows from Euclidean division that the sets $D_k$ partition the set $\{n \in \Bbb N \, | \, n \ge 2 \}$. Moreover, it is easy to show that

$\quad A = (D_{-4} \cup D_{-2} \cup D_0) \setminus \{2\}$

and

$\quad B = (D_{-3} \cup D_0) \setminus \{3\}$

So it is immediate that

$\tag 1 C = \{2,3\} \cup D_{-1} \cup D_{1} = \{2,3\} \cup \{6n - 1, 6n+1 \, | \, n \ge 1\}$

Example 1: With $n = 4$ and using $\text{(1)}$ we get

$\quad 6 \times 4 - 1 = 23 \in C$

$\quad 6 \times 4 + 1 = 25 \in C$

After examining $23$, we determine that it is a prime number.

After examining $25$, we determine that it is not a prime number.

Example 2: The number $547$ is a prime number. Also, using Euclidean division,

$\quad 547 = 6 \times 91 + 1 \text{ and } 547 = 6n + 1 \text{ when } n = 91$

Example 3: The number $29$ is a prime number. Also

$\quad 29 = 6 \times 4 + 5$

After a moments thought, we see that $29 = 6 \times n - 1$ with $n = 5$.

Exercise: Let $m \ge 4$ and $m = 6 q + r$ with $0 \le r \le 5$. Explain why it is impossible for $m$ to be a prime number when $m \in \{0,2,3,4\}$.