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$
3
  • 1
    $\begingroup$ Have you already studied Hensel's Lemma? $\endgroup$
    – DonAntonio
    May 12, 2014 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, 2014 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, 2014 at 11:39

1 Answer 1

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$
1
  • $\begingroup$ That makes sense (after quite a bit of thinking), thanks! $\endgroup$
    – Gawin
    May 12, 2014 at 13:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .