From Example Problems
Jump to: navigation, search

Prove that there are infinitely many primes of the form p=6k-1\,.

Suppose on the contrary that there are just a finite number of these primes, say p1, ..., pn. Let a = p1...pn. Obviously, a = (–1)n modulo 6. If n is even, let b = a + 4 and otherwise let b = a + 6. Then b = 5 modulo 6 = –1 modulo 6. Moreover, any prime number q dividing both a and b will also divide either 4 or 6, hence such a q will equal 2 or 3. In particular, none of the pj will divide b. Now write b as a product of prime numbers. Since b is odd, every prime factor q of b can be written as q = 6r + 1, q = 6r + 3 or q = 6r + 5. However, the last type (which is –1 modulo 6) is already ruled out, since none of the pj divides b. 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 3m = 3 modulo 6), a contradiction which completes the proof.