# Need help with the following theorem

Theorem 4-5. If p is prime and d divides p-1, then there are exactly d roots of the congruence

$$x^d \equiv 1(mod\text{ } p)$$

Proof: Since $d|(p-1)$, we have

$$x^{p-1}-1 \equiv (x^d-1)q(x)$$

where $q(x)$ is a polynomial of degree $p-1-d$ in x. By lagrange's theorem, the congruence

$$q(x) \equiv 0(mod\text{ } p)$$

has at most $p-1-d$ solutions. Since $x^{p-1} \equiv 1(mod\text{ } p)$ has exactly p-1 solutions, $x^d \equiv 1(mod\text{ } p)$ must have at least

$$p-1-(p-1-d)=d$$

solutions. Since it can have no more than this number, it must have exactly d solutions

The first thing that I would like to understand is why $x^{p-1}-1=(x^d-1)q(x)$

• If we put $y=x^{d}$, then $x^{p-1}-1=y^{(p-1)/d}-1=(y-1)(y^{(p-1)/d-1}+\cdots+1)=(x^{d}-1)q(x)$ where $q(x)=x^{p-1-d}+x^{p-1-2d}+\cdots+1$. – Seewoo Lee Jul 11 '16 at 0:39
• @Bill Dubuque . Why is the following true $p-1-(p-1-d)=d$? – TheMathNoob Jul 12 '16 at 7:27
• @TheMathNoob The idea is simple: if $\, f = gh\,$ and $\,f\,$ has $\,\deg f\,$ roots, then also $\,g\,$ has $\,\deg g\,$ roots and $\,h\,$ has $\,\deg h\,$ roots, since if one of $\,g,h\,$ had less, then the other would have to have more, contra Lagrange. – Bill Dubuque Jul 12 '16 at 13:50
• @Bill Dubuque. How does the factorization show that that the roots of $x^{p-1}-1$ are either roots of $x^d-1$ or roots of q(x)? – TheMathNoob Jul 13 '16 at 1:38
• $0 \equiv f(n)\equiv g(n)h(n)\,\Rightarrow\, g(n)\equiv 0\,$ or $\,h(n)\equiv 0\,$ since $\,\Bbb Z/p\,$ is a domain; or, equivalently, $\,p\mid g(n)h(n)\,\Rightarrow\, p\mid g(n)\,$ or $\,p\mid h(n).\$ – Bill Dubuque Jul 13 '16 at 2:04

Let $x^d=y.$ Since $d|(p-1)$ we have $p-1=dk$ with $k\in N.$ So $$x^{p-1}-1=x^{dk}-1=y^k-1=(y-1)\sum_{j=0}^{k-1}y^j=(x^d-1)\sum_{j=0}^{k-1}x^{dj}.$$
• thanks now why does $x^{p-1} \equiv 1(mod \text{ } p)$ have p-1 roots by fermat's little theorem? – TheMathNoob Jul 11 '16 at 1:04
• Fermat's Little Theorem (which is a special case of Lagrange's Theorem ) is that $x^{p-1}\equiv 1 \pmod p$ when $x\not \equiv 0 \pmod p.$ So the members of $\{j:1\leq j\leq p-1\}$ are all solutions of $x^{p-1}\equiv 1\pmod p$ and they are all distinct, $\pmod p.$ – DanielWainfleet Jul 11 '16 at 1:17
• Since it is endemic, any text on introduction to number theory ought to have it. The wikipedia article Proofs Of Fermat's Little Therorem has many. but most of them look obscure and difficult, except for Euler's first proof, by induction on x, that (equivalently) $x^p\equiv x\pmod p$ for all $x$: In the (binomial theorem) expansion of $(x+1)^p$ all the terms except the first and last are divisible by $p$, since for $0<j<p$ the co-efficient $\binom {p}{j}=$ $p\cdot (p-1)!/j!(p-j)!$ and no combination of terms in the denominator can cancel the "$p$" in the numerator (because $p$ is prime). – DanielWainfleet Jul 11 '16 at 16:40
• Fermat's little theorem is a special case of Lagrange's theorem that the number $|H|$ ,of members of a subgroup $H$ of a finite group $G,$ divides $|G|.$ Now multiplication mod $p$ on $G=\{1,...,p-1\}$ is a finite group with $|G|=p-1$. For any $0<x<p$ the smallest subgroup containing $x$ has $d$ members, where $d$ is the least $n\in N$ such that $x^d\equiv 1\pmod p.$ Since $d|(p-1)$ we have therefore $x^{p-1}\equiv 1.$ Note: The set of remainders mod $p$ of $\{x^n:n\in N\}$ is finite so for some $n,d\in N$ we have $x^n\equiv x^{n+d},$ so $d$ exists. – DanielWainfleet Jul 11 '16 at 16:59