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 '13 at 6:30

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 '13 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$ – Greg Martin Dec 11 '13 at 8:13
  • $\begingroup$ This particular arithmetic progression, yes. $\endgroup$ – user7530 Dec 11 '13 at 14:43
  • $\begingroup$ A chacun son goût! $\endgroup$ – Greg Martin Dec 11 '13 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$.


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.