# If $p$ and $q$ are primes such that $q \mid {\frac{x^p-1}{x-1}}$ then prove that $q\equiv 1 \pmod{p}$ or $q\equiv 0 \pmod{p}$.

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 °_°

• 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. – user208649 Jul 28 '20 at 5:01
• @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? – 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$$.