The proof that there are infinitely many primes for 4n + 3 and 6n + 5 I'm trying to prove that there are infinitely many primes for $6n + 5$. I see the same proof for $4n + 3$, and can't understand why we say that all of the primes are either in the form $4n + 1$ or $4n + 3$. If I apply it to $6n + 5$ they will be either in the form $6n + 1$ or $6n + 5$, but why not in the $6n + 3$?
I'm sorry if it's confusing, I will be very grateful if someone could explain it to me.
 A: Because in modular arithmetic, the integers are closed under multiplication just as they are in regular arithmetic, and $(-1)^2 = 1$.
Since $4n + 3 = 4(n + 1) - 1$, it follows that $3 \equiv -1 \pmod 4$ and then $$(4a + 3)(4b + 3) = (4m - 1)(4n - 1) = 16mn - 4m - 4n - 1 = 4k - 1,$$ with $a = m - 1$ and $b = n - 1$. Or, if you prefer, $$(4m + 3)(4n + 3) = 16mn + 12m + 12n + 3 = 4k + 3.$$
Pretend for a minute that you don't know the factorization of 39. That number could actually be a prime of the form $4n + 3$. But it could just as easily be the product of a prime $p \equiv -1 \pmod 4$ and a prime $q \equiv 1 \pmod 4$; then $pq \equiv -1 \pmod 4$. Or it could even be the product of three primes of the form $4n - 1$, since $(-1)^3 = -1$.
Likewise with $6n - 1$ and $6n + 1$. Pretend that you don't know the factorization of 35. This can't be a multiple of any prime of the form $6n + 3$ because $3x \equiv -1 \pmod 6$ has no solutions in integers: $3x$ must either be 0 or 3.
Of course these are toy examples. By the frivolous theorem of arithmetic, almost all integers are very large. We might not know the factorization of a googolplex plus 7, but we can easily figure out what it is modulo 4 or 6 and draw a few conclusions from that.
