Do you have a question? Post it now! No Registration Necessary. Now with pictures!
- Subject
- Posted on
- Infinitely many primes of the form p=6k-1.
- 12-06-2009
- +this -that +this _that_
December 6, 2009, 4:29 am
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
Re: Infinitely many primes of the form p=6k-1.
On Dec 5, 8:29=A0pm, "+this -that +this _that_"
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
Site Timeline
- » Top 25 Web Design Tips How to desing Simple Web site
- — Next thread in » HTML Authoring Forum
- » Fast Fourier Solutions
- — Previous thread in » HTML Authoring Forum
- » Converting old code to be html5 conformant
- — Newest thread in » HTML Authoring Forum
- » ssh on command line: force using a group size (prime size) of 1024 (and no...
- — The site's Newest Thread. Posted in » Secure Shell Forum