# Prove that there are infinitely many primes $q$ such that $q \equiv 1 \pmod{n}$, when $n$ is prime.

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}$$

This is copied from this question, the answer I found doesn't quite make sense to me, more specifically why is it that the $$q_i \not\equiv 1 \pmod n$$ ? Would anyone be able to explain it, here is the answer provided

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.

• Look at what $q$ divides. Can any $q_i$ divide the same thing ? – Maxime Ramzi Oct 27 '18 at 22:24

The fact you need is that $$q$$ divides $$a^n-1$$, and $$q_i$$ cannot, since it divides $$a^n$$.
• Where does it state that q divides $a^n$? – J. Masterson Oct 28 '18 at 18:23
• Also is it necessary to state $a=n$ if $k=0$? – J. Masterson Oct 28 '18 at 18:23
• It doesn't say that $q$ divides $a^n$. But you set $a=nq_1\cdot\cdot\cdot q_k$, so $q_i$ divided $a$ and thus also $a^n$, for $1\le i\le k$. – C Monsour Oct 28 '18 at 21:48