4
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – user236182 Oct 1 '15 at 13:13
  • 1
  • $\begingroup$ Where did you get this question? It has been posted a number of times in, say, the past week. $\endgroup$ – Will Jagy Oct 1 '15 at 18:21
  • 1
    $\begingroup$ 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$. $\endgroup$ – dohmatob Oct 2 '15 at 19:22
5
$\begingroup$

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

$\endgroup$

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.