Prove that there are infinitely many primes $q$ such that $q \equiv 1 \pmod{n}$, when $n$ is prime.
Use the hint: Consider the order of $a + kN$ in the multiplicative group of $\mathbb{Z}/N\mathbb{Z}$, where $N=a^n-1$ and $k \in \mathbb{Z}$
Anyone can help??
Best Answer
Let $q$ be a prime divisor of $$ A = \frac{a^n-1}{a-1} = a^{n-1}+a^{n-2} + \dots + a + 1, $$ then $$ a^n-1 = A (a-1) \equiv 0 \pmod{q},$$ so by Fermat's little theorem either $q \vert a-1$ or $n \vert q-1$ (or both). Now if $q$ is also a divisor of $a-1$, then $$ 0 \equiv A \equiv 1^{n-1} + 1^{n-2} + \dots + 1 \equiv n \pmod{q} $$ and so $q$ is also a divisor of $n$, so if we chose $a$ equal to a multiple of $n$ then we are sure that a prime divisor $q$ of $A$ is not a divisor of $a-1$.
Now we can use Euclid's argument in the following way: suppose that there is only a finite number of primes $\equiv 1 \pmod{n}$, say $q_1,q_2,\dots,q_k$, set $a = nq_1q_2\dots q_k$ or $a = n$ if $k=0$. Let $q$ a divisor of $a^{n-1}+a^{n-2}+\dots+1$, then by the previous discussion $q$ is not a divisor of $a-1$, but $a^n \equiv 1\pmod{q}$ so by Fermat's little theorme $n \vert q-1$, and we found a prime $q \equiv 1 \pmod{n}$, which by construction is not possibly any of the $q_i$'s a contradiction.