1
$\begingroup$

Establish that there are infinitely many primes of the form $4k+1$.

I was studying primitive roots, and it was recently proven that the odd prime divisors $n^2 +1$ are all of the form of $4k+1$.

A proof in Burton's Elementary Number Theory assumes that there are finitely many primes of the form $4k+1$. The book lets $N = (2p_1...p_n)^2 +1$ ($p_i$ are the primes of form $4k+1$ then proceeds that this number would have a prime of the form $4k+1$ that is not $p_i$ ($i$ between $1$ and $n$) because $p_i$ does not divide 1, thus does not divide $N$.

I was wondering why you would use $N =(2p_1...p_n)^2+1$, doesn't letting $N=(p_1...p_n)^2 +1$ achieve the exact same thing?

$\endgroup$
7
  • 2
    $\begingroup$ It isn't true that every prime factor of $n^2+1$ is of the form $4k+1$. If $n$ is odd then $2$ is a factor. We want to avoid that case. $\endgroup$
    – lulu
    Sep 14, 2020 at 11:28
  • 1
    $\begingroup$ Because $N$ is not generally of a form $4k+1$ $\endgroup$
    – EDX
    Sep 14, 2020 at 11:29
  • $\begingroup$ For the purpose of the proof , we could also use the second expression, but we would have to argue more complicated because of the additional factor $2$. $\endgroup$
    – Peter
    Sep 14, 2020 at 11:31
  • $\begingroup$ N does not need to be in the form $4k+1$, just$n^2+1$. I do not get why having a factor of 2 is relevant, since the number N would still have odd divisors, which would be in the form 4k+1? and every prime 4k+1 would still not be able to divide N? $\endgroup$
    – SuperMage1
    Sep 14, 2020 at 11:32
  • 1
    $\begingroup$ As @Peter remarks, you can do it without the factor of $2$ if you want to, but then you need a separate argument to the effect that $n^2+1$ can't be a power of $2$ (unless $n=0$). That's an easy exercise and worth doing. Including the factor of $2$ lets you skip that step. $\endgroup$
    – lulu
    Sep 14, 2020 at 13:17

1 Answer 1

1
$\begingroup$

For every integer $n$, every odd prime divisor $p$ of $n^2+1$ is of the form $p=4k+1$ for some integer $k$. It follows that for every even integer $n$, every prime divisor $p$ of $n^2+1$ is of the form $p=4k+1$ for some integer $k$.

Let $p_1,\ldots,p_m$ be a finite list of primes. Then every odd prime divisor of $$N=(p_1\cdot p_2\cdots p_m)^2+1,$$ is a prime number of the form $4k+1$, and is coprime to $p_1,\ldots,p_m$. This shows that if $N$ has an odd prime divisor, then the finite list $p_1,\ldots,p_m$ is incomplete. So it remains to show that $N$ has an odd prime divisor, i.e. that $N$ is not a power of $2$.

On the other hand, every prime divisor of $$M=(2p_1\cdot p_2\cdots p_m)^2+1,$$ is a prime number of the form $4k+1$, and is coprime to $p_1,\ldots,p_m$. This shows that the finite list $p_1,\ldots,p_m$ is incomplete. No further argument is needed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.