Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
What are your thoughts on this problem? –  abiessu Jun 1 at 1:31

1 Answer 1

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|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 at 21:53
    
as it is right now, I would say the proof is incomplete. –  Badshah Sep 25 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 at 8:00

Your Answer

 
discard

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.