# Fermat's Little Theorem: group and multiplication modulo

• $p$ is a prime number.

• $G$ is a group of integers $\{1,2,\dots,p-1\}$ under multiplication mod $p$.

• $d$ is a divisor of $(p-1)$

Is it possible to prove that the number of elements $a$ in $G$ such that $a^d\equiv1$ (mod $p$) is exactly $d$?

The Fermat's little theorem $a^{p-1} \equiv1$ should come in handy somewhere.

• Can one use the fact that there is a primitive root? – André Nicolas Oct 21 '14 at 21:45
• @AndréNicolas In fact, this result is stronger... – ajotatxe Oct 21 '14 at 21:52
• Yes, if course it's possible. It follows from the fact that $G$ is cyclic. – egreg Oct 21 '14 at 21:56
• @egreg To say that $G$ is cyclic is the same as to say that $G$ has a primitive root. – ajotatxe Oct 21 '14 at 21:58
• @ajotatxe Yes, of course, but perhaps it's clearer terminology for the OP. – egreg Oct 21 '14 at 22:04

Usually the proof relies on the following fact: let $p$ be a prime number, and let $f(x) = c_k x^k + \cdots + c_1 x + c_0$ be a polynomial with integer coefficients, where $p\nmid c_k$. Then $f(x)\equiv0\pmod p$ has at most $k$ solutions (meaning, at most $k$ residue classes modulo $p$ contain integers that are solutions to the congruence).
To derive the OP's result from this, note that if $d\mid(p-1)$, so that $p-1=de$, then $$x^{p-1} - 1 = (x^d-1)(x^{(e-1)d} + \cdots + x^d + 1).$$ But the left-hand polynomial has exactly $p-1$ roots modulo $p$ by Fermat's little theorem, while the second polynomial on the right-hand side has at most $(e-1)d$ roots modulo $p$. Therefore $x^d-1$ must have at least $(p-1)-(e-1)d=d$ roots modulo $p$ (hence has exactly $d$ roots, since it has at most $d$).
• Thank you Greg. Thank you very much for your response. For the last part, I got that $p−(e−1)d=d+1$ instead of $d$. Am I missing a 1 somewhere? – Alicia Hargrove Oct 22 '14 at 22:23
• Thanks Greg! Just one more question: for the polynomial $f(x)$, do we require that $p$ doesn't divide only $c_k$, or all $c_i$ ($1\le i \le k$)? – Alicia Hargrove Oct 22 '14 at 22:27
• Just $c_k$. We need the polynomial to "have degree $k$ modulo $p$". For example, we shouldn't think of $10x^3+2x^2-5x-3\equiv0\pmod5$ as a cubic congruence - we should think of it as a quadratic congruence. – Greg Martin Oct 22 '14 at 22:34
• Looking back at the question, I am still a little unsure about one part. Could you pleas elaborate a little more on how may one argue that $(x^{(e-1)d} + x^{(e-2)d} + \dots + x^d + 1)$ has at most $(e-1)d$ roots? – Alicia Hargrove Oct 23 '14 at 5:57