Let A = {4n + 3 | n ∈ ℕ}.  Show that A contains infinitely many prime numbers.

(Hint: any prime > 2 is odd, hence of the form 4n + 1 or 4n + 3.)

Solution:

  Assume there are only finitely many primes of the form 4n + 3, say p1,...,pm
  
    Consider the number N = 4p1...pm - 1 = 4(p1...pm - 1) + 3
    We will show that N must have a factor p of the form 4n + 3
  
      Suppose N does not have a factor of the form 4n + 3
      Note the fact that (4a + 1)(4b + 1) is of the form 4c + 1
      If all factors of N is of the form 4n + 1, N will be of the form 4n + 1, but N is not
      Thus N must have a factor of the form 4n + 3
  
    Based on the assumption, it follows p is a member of {p1,...,pm} and p divides N
    But dividing N by p would result in the form 4c - 1/p which is a fraction (where c ∈ ℕ)
    So p cannot divide N.  A contradiction.
  
  Thus there are infinitely many primes of the form 4n + 3.

# posted by rot13(Unafba Pune) @ 11:02 PM