1
$\begingroup$

Let $p$ be a prime and $x$ a fixed integer. Show there is a unique $y \in \{0, 1 \dots p^n-1 \}$ such that: $ y \equiv x \space (mod $ $p)$ and $y^p \equiv y \space (mod $ $p^n) $

$\endgroup$
2
$\begingroup$

For $n=1$ it is clear that there is one and only one $y\equiv x\pmod{p}$ in $\{0,1,...,p-1\}$, and this single $y$ satisfies $p|y^p-y$ by Fermat's theorem.

Assume that the proposition is true for $n$.

If $y_1,y_2\in\{0,1,...,p^{n+1}-1\}$ are two such solutions for the proposition with $n+1$ instead of $n$. Their remainders modulo $p^n$ must satisfy the same proposition, but for $n$. By the uniqueness for the case $n$ (which are inductively assuming) we have that $y_1-y_2\equiv0\pmod{p^n}$. This means (up to exchanging their indexes) that $y_2=y_1+p^{n}$.

We are assuming that $y_1^p-y_1\equiv0\pmod{p^{n+1}}$. Then

$$\begin{align}y_2^p-y_2&\equiv(y_1+p^n)^p-(y_1+p^n)\pmod{p^{n+1}}\\&\equiv y_1^p-y_1-p^n\\&\equiv p^n\not\equiv0\pmod{p^{n+1}}\end{align}$$

This is a contradiction with $y_2^p-y_2\equiv\pmod{p^{n+1}}$. Therefore, there are not two solutions for $n+1$. There are one or less.

We still need to prove that there is one solution.

We can inductively lift the solution from $n$ (which we inductively assume exits). Assume that $\{0,1,...,p^n-1\}\ni y_0\equiv x\pmod{p}$ and $y_0^p-y_0\equiv0\pmod{p^n}$. Let's search the solution for $n+1$ in the form $y=y_0+kp^{n}$, for some $k=0,1,...,p-1$.

We have $y_0+kp^n\equiv x\pmod{p}$ for all $k$. We need

$$\pmod{p^{n+1}}0\equiv y^p-y=(y_0+kp^n)^p-(y_0+kp^n)\equiv y_0^p-y_0-kp^n$$

Since $y_0^p-y_0$ is divisible by $p^n$, we can divide the whole equation by $p^n$ $$\pmod{p}0\equiv \frac{y_0^p-y_0}{p^n}-k$$

This gives us the solution for $k$, the remainder of $\frac{y_0^p-y_0}{p^n}\pmod{p}$.

$\endgroup$

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.