Originally posted by genius
prove that there are infinetly many primes of the form 6k+5.
Off the top of my head:
Claim: If x is a natural number such that x = -1 mod 6, then x has a prime factor which is congruent to -1 mod 6.
Proof: x is clearly not a multiple of 2 or 3, so its prime factors are all congruent to either 1 or -1 mod 6. But if they were all congruent to 1 mod 6, x would also be congruent to 1 mod 6.
Now suppose that p1,p2,...,pn is a complete list of primes which are congruent to -1 mod 6. Then (p1p2...pn)^2 - 2 is a natural number which
a) is congruent to -1 mod 6
b) doesn't have any of p1,p2,...,pn as a prime factor, contradicting the claim.
Hence there are infinitely many primes of the form 6k+5, QED.
Apparently, it is known that every arithmetic sequence either contains infinitely many primes, or every term in the sequence is divisible by a particular prime. I have no idea how this was proved, but I get the impression that it's quite a hard result.