# Infinitely many primes of the form $pn+1$

Prove: Given a prime $p$, there are infinitely many $n\in \mathbb{Z}^+$, for which $pn+1$ is a prime.

This is a simplified version of Dirichlet's theorem, so is there any elementary solution to this problem?

A proof by contradiction is recommended. Just like the proof of the existence of infinitely many primes by Euclid.

• There are infinitely many primes of the form $nk+1$ for a fixed $n\in\Bbb Z$ by an elementary proof here (using cyclotomic polynomials). Your claim follows. – user236182 Oct 1 '15 at 13:13
• – lhf Oct 1 '15 at 13:20
• Where did you get this question? It has been posted a number of times in, say, the past week. – Will Jagy Oct 1 '15 at 18:21
• This is a trivial consequence of the Dirichlet-Legendre-Vallée-Poussin Theorem. In fact, for large $x > 0$, the are roughly $\frac{1}{\phi(p)}\textrm{Li}(x) = \frac{1}{p-1}\textrm{Li}(x)$ such primes $\le x$. – dohmatob Oct 2 '15 at 19:22

All prime divisors of $\frac{(pr)^{p}-1}{pr-1}$ for any positive integer $r$ are of the form $pk+1$ (proof below).

Now assume for contradiction there are finitely many primes $\{p_1,p_2,\ldots, p_t\}$ of the form $pk+1$. Let $r=p_1p_2\cdots p_t$.

Then all prime divisors of $\frac{(pr)^{p}-1}{pr-1}$ are of the form $pk +1$ and coprime to $p_1,p_2,\ldots, p_t$. Contradiction.

Proof: Define $\text{ord}_n(a)$ to be the least positive integer $m$ such that $a^m\equiv 1\pmod{n}$.

Lemma: if $x^t\equiv 1\pmod{n}$, then $\text{ord}_n(x)\mid t$. Proof: if $t=\text{ord}_n(x)l+r,\, 0<r<\text{ord}_n(x)$, then $1\equiv x^t\equiv \left(x^{\text{ord}_n(x)}\right)^lx^r\equiv x^r\pmod{n}$, contradiction. q.e.d.

Let $q$ be a prime divisor of $\frac{(pr)^{p}-1}{pr-1}$. Then $\text{ord}_q(pr)\in\{1,p\}$ and $\gcd(q,pr)=1$. For contradiction, assume $q\mid pr-1$.

$$q\mid (pr)^{p-1}+(pr)^{p-2}+\cdots+1\equiv 1^{p-1}+1^{p-2}+\cdots + 1\equiv p\not\equiv 0\pmod{q},$$

contradiction. Therefore $\text{ord}_q(pr)=p$, so by Fermat's Little Theorem and the lemma $p\mid q-1$. Q.E.D