# Number of solutions modulo $p^2$

I am asked to do the following:

Let $p$ be a prime number, suppose that $d|p-1$, investigate the number of solutions to the equations $$x^d\equiv 1 \mod p$$ and $$x^d\equiv 1 \mod p^2$$

There is also a hint to the second one: Consider $s+py$ where $s$ is a solution to the first equation, and $y\in\mathbb{Z}$.

Now I have already done the first one. Here's the sketch:

By Lagrange's Theorem, $x^d\equiv 1 \mod p$ has at most $d$ solutions.

Conversly, since $d|p-1$, let $e$ be such that $de=p-1$. Then $$x^{p-1}-1=x^{de}-1=(x^d-1)(x^{d(e-1)}+x^{d(e-2)}+...+x^{d}+1)$$ Since $p$ is prime, all solutions to $x^{p-1}-1 \equiv 0 \mod p$ must be a solution to either the congruence modulo $p$ equations of $x^d-1$ or $x^{d(e-1)}+...$ . By Fermat's Little Theorem, $x^{p-1}-1 \equiv 0 \mod p$ has exactly $p-1$ solutuons. And by Lagrange's Theorem, $$x^{d(e-1)}+x^{d(e-2)}+...+x^{d}+1\equiv 0 \mod p$$ has at most $d(e-1)=p-1-d$ solutions. It follows that $x^{d}-1 \equiv 0 \mod p$ has at least $p-1-(p-1-d)=d$ solutions.

So $x^d\equiv 1 \mod p$ has exactly $d$ solutions.

The second equation (the $p^2$ one) is where I am having trouble. The only thing I have spotted so far is that any solutions to the $p^2$ equation must also be a solution to the $p$ equation, so the $p^2$ equation can have at most $d$ solution again. I am not sure how to use the hint given either.

• Have you already studied Hensel's Lemma? – DonAntonio May 12 '14 at 11:35
• No idea what that is lol. I think the relevant theorems I have been taught are Fermat's Little Theorem and Lagrange's theorem. – Gawin May 12 '14 at 11:37
• Well, you can try to google it anyway. It's proof isn't hard (but don't mess with $\;p$-adic numbers!), and it talks of "lifting" solutions of some equation modulo $\;p^n\;$ to solutions modulo $\;p^{n+1}\;$ ... – DonAntonio May 12 '14 at 11:39

If $a$ and $b$ are integers, $(a+bp)^d = a^d + dba^{d-1}p \pmod {p^2}$.
So if you look for values $a,b \in \{0\ldots p-1\}$ such that $(a+bp)^d = 1 \pmod {p^2}$, first you need to have $a^d \equiv 1 \pmod p$. Then, for such an $a$, you need to have $\frac{a^d-1}p + dba^{d-1} = 0 \pmod p$, which gives you a unique possible value for $b$ modulo $p$ (because $da^{d-1} \neq 0 \pmod p$)
So for each solution $a$ to $a^d = 1 \pmod p$ there is a unique solution $a' = (a+bp)$ to $a'^d = 1 \pmod {p^2}$ where $a' = a \pmod p$.