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.
Best Answer
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