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^n-1$, then $a^n \equiv 1 \pmod{q}$, so by Fermat's little theorem $n \vert q-1$ or equivalently $q \equiv 1 \pmod{n}$. So starting with an arbitrary integer $a > 1 $ we get a prime $q$ such that $ q\equiv 1 \pmod{n}$. To see that there is an infinite number of them, you can use Euclides argument, given any set of primes $q_1,q_2, \dots,q_k$ of that form we can find a prime of the same form not in the list, just set $a = q_1 q_2\dots q_k$, an pick any prime divisor of $a^n-1$.

share|improve this answer

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.