I'm looking at this funny little problem involving proving the existence of an infinite number of primes of a certain form:

Prove that there are infinitely many prime numbers expressible in the form $8n+1$ where $n$ is a positive integer.

My proof goes like this:

Assume by way of contradiction that there are only finitely many of such prime numbers, say $p_1,p_2,\ldots,p_r$. Consider $p = 16p_1^4p_2^4\cdots p_r^4 +1 = (2p_1p_2 \cdots p_r)^4+1$. Recall that the congruence $x^4 \equiv -1 \mod p$ is solvable if and only if $p \equiv 1 \mod 8$. $p$ cannot be a prime of the form $8n+1$, but $p \equiv 1 \mod 8$, contradiction. Thus, there must be infinitely many prime numbers of the form $8n+1$.

I'm not quite sure if I actually achieve a contradiction here. Can you help me clarify this?

  • $\begingroup$ Is your $p$ prime? $\endgroup$
    – aschepler
    Dec 11, 2013 at 6:30

2 Answers 2


This idea seems fine, although notice that $p$ does not have to be your number itself, but can be one of its divisors.

$16p_1^4p_2^4\ldots p_r^4+1$ must have some prime divisor $p$, and it is not one of the existing $p_i$, nor is it 2. Moreover $x=2p_1p_2\ldots p_r$ satisfies the congruence $x^4+1\equiv 0 \pmod p$, and therefore $p\equiv 1\pmod 8$, a contradiction.

  • $\begingroup$ Incidentally, is there a clever way of seeing that last fact? Certainly you can argue that the order of $x$ must be 8, and therefore $8\vert \phi(p)$, but that requires rather a lot of machinery for a very elementary problem. $\endgroup$
    – user7530
    Dec 11, 2013 at 6:52
  • $\begingroup$ You consider the existence of infinitely many primes in an arithmetic progression more elementary than these facts about the orders of elements modulo $p$? $\endgroup$ Dec 11, 2013 at 8:13
  • $\begingroup$ This particular arithmetic progression, yes. $\endgroup$
    – user7530
    Dec 11, 2013 at 14:43
  • $\begingroup$ A chacun son goût! $\endgroup$ Dec 11, 2013 at 18:32


The odd prime divisors of $n^4+1$ are of the form $8k+1$

From $n^4\equiv -1\pmod{p}$ we have $n^8\equiv 1\pmod{p}$, therefore the order of $n$ modulo $p$ is $8$, and from the following theorem:

If $a$ is of order $k$ modulo $n$, then $a^h\equiv 1\pmod{n}$ iff $k|h$. Also $k|\phi(n)$.

It follows that $8|\phi(p)$, or in other words: $p=8k+1$.

  • $\begingroup$ This is neat, but does not yet prove infiniteness. What if the set of all values of $n^4 + 1$ has only a few odd prime divisors? $\endgroup$ Oct 13, 2021 at 5:12

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.