# (–1 modulo 6) dismissed

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Infinitely many primes of the form p=3D6k-1.

(Originally) posted by +this -that +this _that_ on December 5, 2009,
11:29 pm

Task:Prove infinitely many primes of the form p=3D6k-1.

Argument:

a) Suppose there are just a finite number of these primes, say

p1, ..., pn. Let a=3Dp<1>...p<n>.

b) Rationally, a = (=961)<n>modulo 6.

c) If n is even, let b = a + 4.
Otherwise let b = a + 6.
Then b = 5 modulo 6 =1 modulo 6.

d) Any prime q dividing both a and b will divide either 4 or 6, hence
such a q equals 2 or 3.

e) None of the p<j> will divide b.

f) Write b as a product of primes. Since b is odd, every prime factor
q of b can be written as q = 6r + 1, q = 6r + 3 or q = 6r + 5.

g) The last type (=961 modulo 6) is dismissed: none of p<j> divides b.

h) The second type only permits q = 3. Therefore b, being the product

of all its prime factors, is either 1 or 3 modulo 6 (since 3<m> = 3
modulo 6): a contradiction=3D=3Dcompletes the proof.

Cheers,
M. Michael Musatov
Founder, http://www.meami.org

Posted by Ostap S. B. M. Bender Jr. on December 6, 2009, 12:27 am

On Dec 5, 8:29 pm, "+this -that +this _that_"
Task:Prove infinitely many primes of the form p=3D6k-1.z
Argument:
a) Suppose there are just a finite number of these primes, say
p1, ..., pn. Let a=3Dp<1>...p<n>.
b) Rationally, a = (=961)<n>modulo 6.
c) If n is even, let b = a + 4.
Otherwise let b = a + 6.
Then b = 5 modulo 6 =1 modulo 6.
d) Any prime q dividing both a and b will divide either 4 or 6, hence
such a q equals 2 or 3.
e) None of the p<j> will divide b.
f) Write b as a product of primes. Since b is odd, every prime factor
q of b can be written as q = 6r + 1, q = 6r + 3 or q = 6r + 5.
g) The last type (=961 modulo 6) is dismissed: none of p<j> divides b.
h) The second type only permits q = 3. Therefore b, being the product
of all its prime factors, is either 1 or 3 modulo 6 (since 3<m> = 3
modulo 6): a contradiction=3D=3Dcompletes the proof.
Cheers,
M. Michael Musatov
Founder,http://www.meami.org

You can prove this even simpler. I just gave this problem to my 11
year-old son, and here is his proof:

Theorem: there exist infinitely many primes of the form p=3D6k-1.

Proof: Suppose there are just a finite number of these primes, say
p1, ..., pn.

Put A = 2*3*p1*p2*...*pn - 1

Clearly, A = -1 mod 6

Look at the prime decomposition of A. All primes higher than 3 are
either 1 or -1 mod 6. But if all primes in the decomposition of A
were
equal to 1 mod 6, then A = 1 mod 6. But A = -1 mod 6. Thus, there
must
exist a prime q, which divides A, s.t. q = -1 mod 6.

But A is relatively prime with p1, p2,...,pn. So must be q. Thus, q
is
prime, q = -1 mod 6, and q doesn't belong to  {p1, ..., pn}.