Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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??

share|cite|improve this question
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.

share|cite|improve this answer
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
as it is right now, I would say the proof is incomplete. – Badshah Sep 25 '14 at 22:07
You are right the proof is incomplete, let me think if I can find a way to patch it otherwise I will remove it. – Esteban Crespi Sep 26 '14 at 8:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.