Mod 6 Research Paper

Lemma: If p > 3 is prime, then either p = 1 (mod 6) or p = 5 (mod 6).

Proof: The residue classes modulo 6 partition Z, so any z in Z satisfies a congruence z = n (mod 6) where n is in {0,1,...,5}. z is divisible by 6 if n = 0, 2 if n = 2, 3 if n = 3, and 2 if n = 4. These cases cover the primes z = 2 and z = 3; if z > 3 is prime, it follows that n = 1 or n = 5, i.e., z = 1 (mod 6) or z = 5 (mod 6).

Now suppose there are only finitely many primes congruent to 5 modulo 6, say p_1, ..., p_k. Write M for p_1 * p_2 * ... * p_k and put N = 6M - 1. Now N = 5 (mod 6). If p is a prime divisor of 6 and p | N, then p | N - 6M = 1, a contradiction. This means that 2 and 3 are not prime factors of N. Thus it follows from the lemma that every prime p | N is either 1 or 5 mod 6. If every such prime is 1 mod 6, then N would be as well, a contradiction, so there is some prime p | N that is congruent to 5 mod 6.

Now if p = p_i for some i in {1,...,k}, then p | 6M and p | N, so p | 6M - N = 1, which is impossible. Thus the list p_1, ..., p_k was not exhaustive as supposed, so the desired result follows. …show more content…
There's a really interesting way to see that the converse is false (not every number congruent to 5 modulo 6 is prime). You could of course just find a counterexample, but this is a special case of a more general phenomenon, described below.

Claim: There is no polynomial P in Z[x] of positive degree such that the values P(0), P(1), ... are all prime.

Proof: Suppose otherwise, so P(0) = p for some prime p. Then the constant term of P is p, so p | P(kp) for k >= 1 an integer. Since these values are prime by hypothesis, P(kp) = p for k >= 1. Thus the polynomial P(x) - p has infinitely many roots over the field R (the real numbers), a