Exercise 2.8.35 (There exist infinitely many prime numbers $q \equiv 1 \pmod p$)

Proof. Let $p$ be a given prime number, and let $q_1,q_2,\dots ,q_r$ be primes such that $q_i\equiv 1(\mathit{mod}p)$ for $1\le i\le r$. Take $a=p{q}_1{q}_2\cdots q_r$. Then $a\ge p\ge 2$. By Problem 33,

Take $m=a^p-1$. Since $a\wedge m=a\wedge (a^p-1)=1$, and $p\mid a$, then $p\nmid m$.

Since $p\mid \varphi (m)$ and $p\nmid m$, by Problem 34, there is at least one prime factor $q$ of $m$ such that

Moreover $q\nmid a$, otherwise $q\mid a^p-m=1$. Therefore $q\notin \{q_1,q_2,\dots ,q_r\}$.

If the set $A$ of prime numbers $q\equiv 1(\mathit{mod}p)$ was finite, say $A=\{q_1,q_2,\dots ,q_r\}$, then we have proved that there exists a prime $q$ such that $q\equiv 1(\mathit{mod}p)$, so $q\in A$, but $q\notin \{q_1,q_2,\dots ,q_r\}$, so $q\notin A$. This contradiction shows that $A$ is finite.

There exist infinitely many prime numbers $q\equiv 1(\mathit{mod}p)$. □