QUESTION: If $p$ and $q$ are primes such that $$q \mid {\frac{x^p-1}{x-1}} , (x\in\Bbb{N}, x>1)$$ then prove that $q\equiv 1 \pmod{p}$ or $q\equiv 0 \pmod{p}$.

MY ANSWER: I came across this lemma, but couldn't prove the second part properly. Here's what I did -

By Fermat's Little Theorem we know that $x^p\equiv{x}\pmod{p}$. Therefore, $$\frac{x^7-1}{x-1}\equiv\frac{x-1}{x-1}=1\pmod{7}$$ Therefore, $q\equiv{1}\pmod{7}$.

Now, I cannot prove that $q\equiv{0}\pmod{7}$. Not simultaneously ofcourse, I know that 😅..

Here's my try -

We can write the above equation as $$x^6+x^5+x^4+x^3+x^2+x+1$$ But what after this? Even if I chose $q=7$, it does not divide the above equation for all values of $x$. Say $x=7$, then the equation can be rewritten as $$7^6+7^5+7^4+7^3+7^2+7+1$$ and $$7\nmid{7^6+7^5+7^4+7^3+7^2+7+1}$$ So, how do I rigorously prove that $q\equiv{0}\pmod{p}$ ? Or, for which cases is this true?

Any help will be much appreciated. Thank you :)

EDIT: Terrible Mistake :P The first proof of $q\equiv{1}\pmod{7}$ is wrong. So, now I am left with a full question to be proved °_°

  • $\begingroup$ I don't understand how the first piece proves $q=1$ mod $7$. It seems to just show that $q$ divides something congruent to $1$ mod $7$. Also it may help to observe that if $q=0$ mod $p$ then $q=p$ since they're primes. $\endgroup$ – user208649 Jul 28 '20 at 5:01
  • $\begingroup$ @TokenToucan Oh yes!! That's a terrible mistake.. my first part is wrong.. let me edit it.. but can you state a detailed proof of this lemma? $\endgroup$ – Stranger Forever Jul 28 '20 at 5:03

There are $2$ cases to consider.

Case $1$: $x \equiv 1 \pmod{q}$

Dividing $x - 1$ into $x^p - 1$, and using $x \equiv 1 \pmod{q}$, gives

$$0 \equiv \sum_{i=0}^{p-1}x^{i} \equiv \sum_{i=0}^{p-1}1^{i} = p \pmod{q} \tag{1}\label{eq1A}$$

Since $p$ and $q$ are primes, this means $p = q$, i.e., $q \equiv 0 \pmod{p}$.

Case $2$: $x \not\equiv 1 \pmod{q}$

In this case, you have

$$x^p - 1 \equiv 0 \pmod{q} \implies x^p \equiv 1 \pmod{q} \tag{2}\label{eq2A}$$

The multiplicative order of $x$ modulo $q$ divides any power of $x$ which is congruent to $1$. Since $x \not\equiv 1 \pmod{q}$, this means the multiplicative order must be $\gt 1$. As $p$ is prime, its only factors are $1$ and $p$, so this means the multiplicative order of $x$ modulo $q$ must be $p$.

However, Fermat's little theorem states

$$x^{q-1} \equiv 1 \pmod{q} \tag{3}\label{eq3A}$$

This means $p \mid q - 1$, i.e.,

$$q \equiv 1 \pmod{p} \tag{4}\label{eq4A}$$

In summary, this shows

$$q \equiv 1 \pmod{p} \; \; \text{ or } \; \; q \equiv 0 \pmod{p} \tag{5}\label{eq5A}$$


Generalizing this answer first suppose that $q \not \equiv 1\pmod{p}$ so that $\gcd(q-1, p) =1$. Then there exists integers $n,m$ such that $pn + (q-1)m =1$ by Bezout's lemma. Then we have $$x \equiv x^{pn +(q-1)m} \equiv (x^p)^n(x^{q-1})^m \equiv 1 \pmod{q} $$ by Fermat's little theorem and the fact that $q|x^p-1.$ Hence $$\frac{x^p-1}{x-1} = 1+x+\dots+x^{p-1} \equiv p \pmod{q}.$$ This shows that $q=p$. The contrapositive says $q \ne p$ implies $q \equiv 1 \pmod{p}$, so we're done since either $q=p$ or $q \ne p$.


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.