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

**posted on**

- be left blank

April 3, 2011, 7:50 am

(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}.

Contradiction. QED

Musatov=3D=3D

This Thread

http://www.1-script.com/forums/Infinitely-many-primes-of-the-form-p-6k-1-ar=

ticle37304--8.htm

#### Site Timeline

- » Re: PHP Runs In WinXP Command Window But Not In Browser
- — Next thread in » HTML Authoring Forum

- » Does it exist? Prefabbed polling and dynamic lists
- — Previous thread in » HTML Authoring Forum

- » Converting old code to be html5 conformant
- — Newest thread in » HTML Authoring Forum

- » Anyone Using ESET NOD32??
- — The site's Newest Thread. Posted in » Anti-Virus Software