Exercise 2.8.36 (The arithmetic progression $1+m, 1+2m,1+3m,\ldots$ contains infinitely many primes)

Proof.

(i)

Suppose that the arithmetic progression ${(1+\mathit{km})}_{k\in {\mathbb{N}}^{\text{∗}}}$ contains at least one prime $p_1=1+k_{1}m$. Applying this property to different values of $m$ we can find prime numbers $p_1,p_2,p_3,\dots$ such that $$\begin{array}{llll}\hfill p_1& =1+k_{1}m,& \hfill & \\ \hfill p_2& =1+k_2(p_{1}m),& \hfill & \\ \hfill p_3& =1+k_3(p_1{p}_{2}m),& \hfill & \\ \hfill \text{⋯}& & \hfill \\ \hfill p_j& =1+k_j(p_1{p}_2\cdots p_{j-1}m),& \hfill & \end{array}$$

For all $j\ge 1$, $p_j\equiv 1(\mathit{mod}m)$, and $p_j\equiv 1(\mathit{mod}{p}_i)$ for $i<j$, so the $p_j$ are distinct. This shows that the arithmetic progression ${(1+\mathit{km})}_{k\in {\mathbb{N}}^{\text{∗}}}$ contains infinitely many primes.

So it suffices to show that for every positive integer $m$, the arithmetic progression ${(1+\mathit{km})}_{k\in {\mathbb{N}}^{\text{∗}}}$ contains at least one prime.

If $m=1$, then the arithmetic progression ${(1+\mathit{km})}_{k\in {\mathbb{N}}^{\text{∗}}}$ contains all integers $n\ge 2$, and if $m=2$, the progression contains all odd intgers $n\ge 3$. We know that there are infinitely many primes, all odd except the prime $2$, so the arithmetic progression ${(1+\mathit{km})}_{k\in {\mathbb{N}}^{\text{∗}}}$ contains infinitely many primes if $m=1$ or $m=2$. We may suppose now that $m\ge 3$.

We now show that for any integer $m\ge 3$, the number $m^m-1$ has at least one prime divisor $q\equiv 1(\mathit{mod}m)$.

(ii)

Assume for contradiction that $m^m-1$ has no prime divisor congruent to $1$ modulo $m$. Let $q$ be any prime divisor of $m^m-1$, so that $q\not\equiv 1(\mathit{mod}m)$. Let $h$ denote the order of $m(\mathit{mod}q)$.

Since $q\mid m^m-1$, $m^m\equiv 1(\mathit{mod}q)$. By Lemma 2.31, $h\mid m$. Moreover, $q\nmid m$ otherwise $q\mid m-(m^m-1)=1$. By Fermat’s Theorem, $m^{q-1}\equiv 1(\mathit{mod}q)$, thus $h\mid q-1$.

Since $h\mid m$, where $m\ne 0$, $h\le m$. If $h=m$, then $m\mid q-1$, but this is impossible, since $q\not\equiv 1(\mathit{mod}m)$. Thus $h<m$, so that $m=\mathit{hc}$ with $c>1$.

(iii)

Let $q^r$ be the highest power of $q$ dividing $m^m-1$, so $q^r\mid \mid m^m-1$, or equivalently ${\nu }_q(m^m-1)=r$. We prove now that ${\nu }_q(m^h-1)=r$.

Since $m=\mathit{hc}$, $m^m-1=(m^h-1)F(m)$, where

$$F(m)=\underset{j=0}{\overset{c-1}{\sum }}{m}^{\mathit{hj}}=m^{h(c-1)}+m^{h(c-2)}+\cdots +m^h+1.$$

Since $m^h\equiv 1(\mathit{mod}q)$, $F(m)\equiv {\sum <!--\; FUNCTION\; APPLICATION\; -->}_{j=0}^{c-1}{1}^j=c(modq)$. Here $q\nmid c$, otherwise $q\mid m$, which is false, so $q\nmid F(m)$ and ${\nu }_q(F(m))=0$. Therefore

$${\nu }_q(m^m-1)={\nu }_q(m^h-1)+{\nu }_q(F(m))={\nu }_q(m^h-1),$$

that is $q^r\mid \mid m^h-1$.

Now if $d$ is such that $h\mid d$ and $d\mid m$, then $m^h-1\mid m^d-1$, and $m^d-1\mid m^m-1$, thus

$$r={\nu }_q(m^h-1)\le {\nu }_q(m^d-1)\le {\nu }_q(m^m-1)=r.$$

Therefore ${\nu }_q(m^d-1)=r$, so $q^r\mid \mid m^d-1$.

Consider the set $𝒮$ of integers $d$ of the form $m∕s$, where $s$ is any square-free divisor of $m$, excluding $s=1$. We partition this set into two disjoint subsets $𝒯$ and $𝒱$ according as the number of primes dividing $s$ is odd or even. Put

$$\begin{array}{lll}\hfill Q=\left(\underset{d\in 𝒯}{\prod }(m^d-1)\right){\left(\underset{d\in 𝒱}{\prod }(m^d-1)\right)}^{-1}.& & \hfill \text{(1)}\end{array}$$

(iv)

Let $q$ be the prime factor of $m^m-1$ considered in (ii). Let $m^d-1$ be a factor in (1), where $d\in 𝒮$, so that $d=m∕s$ where $s$ is square-free, $s\ne 1$. Then, knowing that $h$ is the order of $m$ modulo $q$, and $m=\mathit{hc}$, $$\begin{array}{llll}\hfill q\mid m^d-1& ⟺m^d\equiv 1(\mathit{mod}q)& \hfill & \\ \hfill & ⟺h\mid d& \hfill & \\ \hfill & ⟺\frac{m}{c}\mid \frac{m}{s}& \hfill & \\ \hfill & ⟺s\mid c.& \hfill & \end{array}$$

This shows that

$$q\mid m^d-1⟺s\mid c.$$

(v)

Let $k$ denote the number of distinct primes dividing $c$. Since $c>1$, $k>0$ and we may write $c=p_1^{a_1}\cdots p_k^{a_k}$. By (iv), there are as many $d\in 𝒯$ for which $q\mid m^d-1$, than square-free divisors $s$ of $c$ with an odd number of prime factors chosen among $p_1,p_2,\dots ,p_k$. The number $S$ of subsets of $A=\{p_1,\dots ,p_k\}$ with odd cardinality is $$S=\left(\genfrac{}{}{0.0pt}{}{k}{1}\right)+\left(\genfrac{}{}{0.0pt}{}{k}{3}\right)+\left(\genfrac{}{}{0.0pt}{}{k}{5}\right)+\cdots =\underset{j=0}{\overset{\lfloor (k-1)∕2\rfloor }{\sum }}\left(\genfrac{}{}{0.0pt}{}{k}{2j+1}\right).$$

Similarly, the number of $d\in 𝒱$ for which $q\mid m^d-1$ is the number $T$ of non empty (because $s\ne 1$) subsets of $A=\{p_1,\dots ,p_k\}$ with even cardinality, where

$$T=\left(\genfrac{}{}{0.0pt}{}{k}{2}\right)+\left(\genfrac{}{}{0.0pt}{}{k}{4}\right)+\cdots =\underset{j=1}{\overset{\lfloor k∕2\rfloor }{\sum }}\left(\genfrac{}{}{0.0pt}{}{k}{2j}\right).$$

Since $S+T={(1+1)}^k-1=2^k-1$, and $-S+1+T={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^k{(-1)}^i\left(\genfrac{}{}{0.0pt}{}{k}{i}\right)={(1-1)}^k=0$, we obtain

$$S=2^{k-1},T=2^{k-1}-1.$$

Let $q$ be a prime factor of $m^m-1$, and $r={\nu }_q(m^m-1)$. If $d\in 𝒮=𝒯\cup 𝒱$ and $q\mid m^d-1$, then $h\mid d$ and $d\mid m$. By part (iii), ${\nu }_q(m^d-1)=r$. Since there are $S=2^{k-1}$ elements $d\in 𝒯$ for which $q\mid m^d-1$, and $T=2^{k-1}-1$ elements $d\in 𝒱$ for which $q\mid m^d-1$, we obtain

$$\begin{array}{lll}\hfill {\nu }_q\left(\underset{d\in 𝒯}{\prod }(m^d-1)\right)=\mathit{Sr},& & \hfill \\ \hfill {\nu }_q\left(\underset{d\in 𝒱}{\prod }(m^d-1)\right)=\mathit{Tr}.& & \hfill \end{array}$$

Therefore

$$\begin{array}{llll}\hfill {\nu }_q(Q)& ={\nu }_q\left[\left(\underset{d\in 𝒯}{\prod }(m^d-1)\right){\left(\underset{d\in 𝒱}{\prod }(m^d-1)\right)}^{-1}\right]& \hfill & \\ \hfill & =\mathit{Sr}-\mathit{Tr}& \hfill & \\ \hfill & =2^{k-1}r-(2^{k-1}-1)r& \hfill & \\ \hfill & =r.& \hfill & \end{array}$$

For every prime factor $q$ of $m^m-1$, such that $q^r\mid \mid m^m-1$, we have also $q^r\mid \mid Q$.

Moreover, if some prime $q^{\prime }$ divides $Q$, then $q^{\prime }$ divides $m^d-1$ for some $d\in 𝒯$. Since $d\mid m$, then $m^d-1\mid m^m-1$, thus $q^{\prime }\mid m^m-1$. So $m^m-1$ and $Q$ have the same prime factors with the same exponents, therefore $m^m-1=Q$, thus

$$\begin{array}{lll}\hfill (m^m-1)\left(\underset{d\in 𝒱}{\prod }(m^d-1)\right)=\left(\underset{d\in 𝒯}{\prod }(m^d-1)\right).& & \hfill \text{(2)}\end{array}$$

Example: Note that the equality (2) is true only under the hypothesis that $m^m-1$ has no prime factor $q\equiv 1(\mathit{mod}m)$. For instance, for $m=6$,

$$(6^6-1)\left(\underset{d\in 𝒱}{\prod }(m^d-1)\right)=(6^6-1)(6^{\frac{6}{2\cdot 3}}-1)=(6^6-1)(6-1),$$

and

$$\left(\underset{d\in 𝒯}{\prod }(m^d-1)\right)=(6^{\frac{6}{2}}-1)(6^{\frac{6}{3}}-1)=(6^3-1)(6^2-1).$$

But $(6^6-1)(6-1)\ne (6^3-1)(6^2-1)$ (otherwise $6^3+1=6+1$). Therefore $6^6-1$ has a prime factor $q\equiv 1(\mathit{mod}6)$. Indeed $6^6-1=46655=5\cdot 7\cdot 31\cdot 43$ has three prime factors of the form $6k+1$. It remains to show that (2) is never true.

(vi)

Let $b$ be a positive integer, and $m\ge 3$.

If $m^b-1\equiv -1(\mathit{mod}{m}^{b+1})$, then $m^{b+1}\mid m^b$, thus $m\mid 1$. This is impossible because $m\ge 3$.

If $m^b-1\equiv 1(\mathit{mod}{m}^{b+1})$, then $m^{b+1}\mid m^b-2$, therefore $m\mid 2$. This is impossible because $m\ge 3$. So

$$m^b-1\not\equiv \pm 1(b\ge 1,m\ge 3).$$

(vii)

Let $b=\min <!--\; FUNCTION\; APPLICATION\; -->(𝒮)$, so that $b$ is the least integer of the type $d$ that appears in the definition of $Q$. We evaluate both sides of (3) modulo $m^{b+1}$. If we write $m=q_1^{a_1}{q}_2^{a_2}\cdots q_l^{a_l}$ the decomposition of $m$ in prime factors, then the least $d$ if obtained with the greatest square-free $s$, which is $s=q_1{q}_2\cdots q_l$, so that $b=q_1^{a_1-1}{q}_2^{a_2-1}\cdots q_j^{a_l-1}$.

Since $b<m$, $m^{b+1}\mid m^m$. For every $d\in 𝒮$, $b\le d$. If $b\ne d$, then $b<d$, so $b+1\le d$, and $m^{b+1}\mid m^d$. Therefore all factors $m^d-1$ (and $m^m-1$) in (3) are congruent to $-1$ modulo $m^{b+1}$, except perhaps $m^b-1$ (in the left or the right member, according to $b\in 𝒯$ or $b\in 𝒱$). Therefore

$$m^b-1\equiv \pm 1(\mathit{mod}{m}^{b+1}).$$

(In the example above, $(6^6-1)(6-1)\equiv -(6-1)=-5\not\equiv 1\equiv (6^3-1)(6^2-1)(\mathit{mod}{6}^2)$).

By (vi), this is impossible, so (2) is false for every $m\ge 3$. This is the waited contradiction, which shows that for $m\ge 3$, $m^m-1$ has always a prime factor $q\equiv 1(\mathit{mod}m)$. By (i), every arithmetic progression ${(1+\mathit{km})}_{k\in {\mathbb{N}}^{\text{∗}}}$, where $m\ge 1$ contains infinitely many primes.