Prove that there are infinitely many primes of the form ## 8k-1 ##

[Math100]

Homework Statement

By considering the number $N=16p_{1}^2p_{2}^2\dotsb p_{2}^2-2$, where $p_{1}, p_{2}, ..., p_{n}$ are primes, prove that there are infinitely many primes of the form $8k-1$.

Relevant Equations

If $p$ is an odd prime, then $(2|p)=1$ if $p\equiv \pm 1\pmod {8}$.

Proof:

Suppose for the sake of contradiction that the only primes of the form $8k-1$ are $p_{1}, p_{2}, ..., p_{n}$
where $N=16p_{1}^2p_{2}^2\dotsb p_{n}^2-2$.
Then $N=(4p_{1}p_{2}\dotsb p_{n})^2-2$.
Note that there exists at least one odd prime divisor $p$ of $N$ such that $(4p_{1}p_{2}\dotsb p_{n})^2\equiv 2\pmod {p}$.
This implies $(2|p)=1$.
Thus $p\equiv \pm 1\pmod {8}$ where $p$ is one of the primes $p_{i}$.
Observe that if all the odd prime divisors of $N$ were of the form $8k+1$, then $N$ would be of the form $8a+1$.
This is impossible, because $N$ is of the form $16a-2$.
Thus, $N$ must have a prime divisor $q$ of the form $8k-1$.
But $q\mid N$ and $q\mid (4p_{1}p_{2}\dotsb p_{n})^2$ leads to the contradiction that $q\mid 2$.
Therefore, there are infinitely many primes of the form $8k-1$.

 

[fresh_42]

I will take the reply button for my remarks.

Homework Statement:: By considering the number $N=16p_{1}^2p_{2}^2\dotsb p_{2}^2-2$, where $p_{1}, p_{2}, ..., p_{n}$ are primes, prove that there are infinitely many primes of the form $8k-1$.
Relevant Equations:: If $p$ is an odd prime, then $(2|p)=1$ if $p\equiv \pm 1\pmod {8}$.

Proof:

Suppose for the sake of contradiction that the only primes of the form $8k-1$ are $p_{1}, p_{2}, ..., p_{n}$
where $N=16p_{1}^2p_{2}^2\dotsb p_{n}^2-2$.
Then $N=(4p_{1}p_{2}\dotsb p_{n})^2-2$.
Note that there exists at least one odd prime divisor $p$ of $N$ such that $(4p_{1}p_{2}\dotsb p_{n})^2\equiv 2\pmod {p}$.

Why? We know $N=2\cdot (8p_1^2p_2^2\ldots p_n^2-1)$. If $8p_1^2p_2^2\ldots p_n^2-1=1$ then $4p_1^2p_2^2\ldots p_n^2=1$ which is always wrong. So the factor in the parentheses is odd and greater than $1,$ i.e. has an odd prime factor.

This implies $(2|p)=1$.

This is absolutely crucial! $p\,|\,((4p_1p_2\ldots p_n)^2-2)$ means $2$ is a square modulo $p$ which is the definition of $\left(\dfrac{2}{p}\right)=1.$ On the other hand, we have
$$
\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}=\begin{cases}1 &\text{ if }p\equiv \pm 1\pmod{8}\\-1&\text{ if }p\equiv 3,5\pmod{8}\end{cases}
$$
So all prime divisors $p\,|\,N$ are either of the form $8k+1$ or $8k-1.$

Thus $p\equiv \pm 1\pmod {8}$ where $p$ is one of the primes $p_{i}$.

Observe that if all the odd prime divisors of $N$ were of the form $8k+1$, then $N$ would be of the form $8a+1$.
This is impossible, because $N$ is of the form $16a-2$.

Let's see. If $N=2^s(8k_1+1)\cdot \ldots \cdot(8k_r+1)=2^s\cdot (8k+1),$ i.e. $(8k+1)\,|\,N=2\cdot (8p_1^2p_2^2\ldots p_n^2 -1)$ and $(8k+1)\,|\,(8p_1^2p_2^2\ldots p_n^2 -1)$ or $8p_1^2p_2^2\ldots p_n^2 -1=(8k+1) \cdot a.$ Thus $-1\equiv a\pmod{8}$ or $a=8b-1.$ However, $a$ is odd and $a\,|\,N$ so its prime factors cannot all be of the form $8k+1,$ at least one is not. But this prime factor also divides $N.$ This proves that not all prime divisors of $N$ are of the form $8k+1.$

Thus, $N$ must have a prime divisor $q$ of the form $8k-1$.
But $q\mid N$ and $q\mid (4p_{1}p_{2}\dotsb p_{n})^2$ leads to the contradiction that $q\mid 2$.
Therefore, there are infinitely many primes of the form $8k-1$.

 

[WWGD]

You can always be heavy-handed and use Dirichlet's theorem to the effect that a progression an+b , with (a,b)=1 , contains infinitely-many primes.

 

[fresh_42]

You can always be heavy-handed and use Dirichlet's theorem to the effect that a progression an+b , with (a,b)=1 , contains infinitely-many primes.

I assume that the above exercise is part of Legendre's proof of Dirichlet's theorem, which by the way seems to be rather complicated:

The problem was first formulated in full by Adrien-Marie Legendre in 1798. This was linked to a first attempt of a proof. In the second edition of his book "Essai sur la théorie des nombres" (published in 1808) he gave an erroneous proof. In the third edition of 1830 he repeated the same mistake. Legendre's error lay behind the words "As you can easily see..." appearing at the end of Section 409 of the third edition.
...
Legendre's lemma, which according to A. Desboves (1855) would have resulted in Legendre's conjecture, which has not yet been proven, ultimately turned out to be wrong. The error was first named by A. Dupré in a paper submitted to the Paris Academy. Dupré showed that already with $k=1$ and with the choice $q_{j}$ as the first $r$ prime numbers with $q_{r }=23,37$ or $43\leq q_{r}\leq 113$ fails. In 1930 A. Brauer and H. Zeitz showed that the lemma fails in this constellation even for all $q_{r}\geq 43.$

This was an experience I also made by proofreading the above solution. It is extraordinarily important to keep track of the quantifiers. I first thought we had only proven the existence of at least one prime factor satisfying $\left(\dfrac{2}{p}\right)=1$. Then I ran into desperate attempts to rule out the possibilities $p\equiv 3,5\pmod{8}$ before I saw, that all odd prime factors had to be $p\equiv \pm 1.$ This was only one obstacle in the proof. The use of the Legendre symbol is crucial. I thought during my first read that it was not really used to its full extent, but it was, hidden in a quantifier that wasn't explicitly written out.

 

[nuuskur]

A different $N$ also does the trick.

Let $p_1,\ldots,p_n$ be all the primes of the form $8k+7$. Verify that $N := (p_1\ldots p_n)^2-2 \equiv 7\pmod{8}$ (and therefore $N$ is odd). For any prime $p\mid N$ it follows that $p\equiv \pm 1\pmod{8}$. It is impossible that all of them are of the form $8k+1$, thus there must exist a prime $q=8k+7$ such that $q\mid N$.