# Infinitely many primes congruent to 1 mod 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}$

Anyone can help??

-
What are your thoughts on this problem? – abiessu Jun 1 '14 at 1:31

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.
If you set $a=q_1\cdots q_k$ then a prime divisor $p$ of $a^n-1$ is not in the list $\{q_1,\dots,q_k\}$. But how can I show that $a\neq 1 \mod p$? Because if $a=1\mod p$ then we cannot say that $n|p-1$. So how does this work then? – Badshah Sep 25 '14 at 21:53