# Infinitely many primes of the form $8n+1$

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?

• Is your $p$ prime? – aschepler Dec 11 '13 at 6:30

## 2 Answers

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.

• 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. – user7530 Dec 11 '13 at 6:52
• You consider the existence of infinitely many primes in an arithmetic progression more elementary than these facts about the orders of elements modulo $p$? – Greg Martin Dec 11 '13 at 8:13
• This particular arithmetic progression, yes. – user7530 Dec 11 '13 at 14:43
• A chacun son goût! – Greg Martin Dec 11 '13 at 18:32

Claim:

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$.