## Prime Numbers

Some primes, like 2 and 5, are congruent to 2 modulo 3. Others like 3 and 7 are not
congruent to 2 modulo 3. In this question you will show that there are infinitely many
primes p such that p ≡ 2 (mod 3) using an argument by contradiction as follows. Suppose there are only finitely many such primes and let them be p1, . . . , pn. Define

N = 3p1 ・ ・ ・ pn − 1.

(a) Show that N ≡ 2 (mod 3).

(b) Show that if q is a prime factor of N then q does not= pi, for i = 1, . . . , n.

(c) Show that N has at least one prime factor p such that p ≡ 2 (mod 3).

(d) Combine the above to complete the proof.