1

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.

joriki
  • 238,052
E. Shcherbo
  • 533
  • 1
    $2, 3, 4$ are not coprime to $6$ so if a prime has the form $6n + 2$ (for instance) then you have $2\cdot (3n + 1)$, a non-trivial factorisation. – Edward Evans Jun 16 '18 at 15:07
  • 2
    $6n+3$ is a multiple of 3. – MJD Jun 16 '18 at 15:09
  • 1
    $6n + 3$ is divisible by $3$ so only one prime is of the form. – fleablood Jun 16 '18 at 15:09
  • 1
    The reason primes (other than 2) have the form $4n+1$ or $4n+3$ is: Every number has the form $4n+k$ for $k=0,1,2 $ or $3$. (Proof: divide by 4. $n$ is the quotient and $k$ is the remainder.). But when $k$ is even, then so is $4n+k$, and so isn't prime. – MJD Jun 16 '18 at 15:12
  • @MJD I got it. Thank you for your help! – E. Shcherbo Jun 16 '18 at 15:13
  • I'm glad I could help. – MJD Jun 16 '18 at 15:14
  • Why doe we say all primes are of the form $4k + 1$ or $4k + 3$? What about $4k$ and $4k + 2$? The same apply to $6n + 2$ (2 is of the form but that is the only one) and $6n+3$ (3 is of the form but that is the only one) and no primes are of the form $6n$ or $6n + 4$.... Any don't see why the proof isn't similar. – fleablood Jun 16 '18 at 15:17
  • @MJD I'm sorry if it's a stupid question, but why don't we consider $4n + 5$ or $6n + 7$ ? Because $4n + 1$, $4n + 3$ and $6n + 1$, $6n + 5$ cover all of the numbers we need? – E. Shcherbo Jun 16 '18 at 15:20
  • 1
    Because $4n + 5 = 4(n+1) +1$ and is of the form $4n + 1$. – fleablood Jun 16 '18 at 15:27
  • @fleablood Oh, you are the best :-) Thank you very much! – E. Shcherbo Jun 16 '18 at 15:29
  • There is a theorem called Dirichlet's theorem on arithmetic progressions with a more advanced result. According to this theorem, because $\gcd(4,3)=1$ and $\gcd(6,5)=1$, both arithmetic progressions will yield infinitely many primes. – rtybase Jun 16 '18 at 16:42

1 Answers1

0

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.

Robert Soupe
  • 14,663