# modular arithmetic, prime powers, existence and uniqueness

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

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