1
$\begingroup$

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.

Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ Have you already studied Hensel's Lemma? $\endgroup$ – DonAntonio May 12 '14 at 11:35
  • $\begingroup$ No idea what that is lol. I think the relevant theorems I have been taught are Fermat's Little Theorem and Lagrange's theorem. $\endgroup$ – Gawin May 12 '14 at 11:37
  • $\begingroup$ 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}\;$ ... $\endgroup$ – DonAntonio May 12 '14 at 11:39
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ That makes sense (after quite a bit of thinking), thanks! $\endgroup$ – Gawin May 12 '14 at 13:07

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.