# Euclid's Theorem

• Oct 2nd 2008, 06:47 AM
knguyen2005
Euclid's Theorem
How do you prove that there exists infinitely many primes p such that p = 2 mod 3 ?

I know that we can use the Euclid's Theorem but I have no idea how to do this kind of question, can anyone give me some hints?

Thanks alot
• Oct 2nd 2008, 07:58 AM
ThePerfectHacker
Quote:

Originally Posted by knguyen2005
How do you prove that there exists infinitely many primes p such that p = 2 mod 3 ?

Assume there are finitely many \$\displaystyle p_1,...,p_n\$.
Form \$\displaystyle N = 3p_1....p_n - 1\$.

We know that \$\displaystyle N\$ has an odd prime divisor \$\displaystyle p\$. If all its prime divisiors were of the form \$\displaystyle 3k+1\$ then \$\displaystyle N\$ would be of the form \$\displaystyle 3k+1\$ and impossibility. Therefore there is a prime divisor \$\displaystyle p\$ of the form \$\displaystyle 3k+2\$. Thus, \$\displaystyle p|N\$ and it must be amongst \$\displaystyle p_1,...,p_n\$. But that leads to \$\displaystyle p|1\$ which is a contradiction.
• Oct 2nd 2008, 11:52 AM
knguyen2005
thank you very much ThePerfectHacker