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.

  • $\begingroup$ Look at what $q$ divides. Can any $q_i$ divide the same thing ? $\endgroup$ – 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$.

This is a special case of Dirichlet's theorem on primes in arithmetic progression. The full theorem is harder to prove.

| cite | improve this answer | |
  • $\begingroup$ Where does it state that q divides $a^n$? $\endgroup$ – J. Masterson Oct 28 '18 at 18:23
  • $\begingroup$ Also is it necessary to state $a=n$ if $k=0$? $\endgroup$ – J. Masterson Oct 28 '18 at 18:23
  • $\begingroup$ That just depends on whether you've established a convention that the empty product is equal to 1. $\endgroup$ – C Monsour Oct 28 '18 at 21:46
  • $\begingroup$ 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$. $\endgroup$ – C Monsour Oct 28 '18 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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