Prove that $a^ n\equiv b^n\pmod{p^k}$ if and only if $n(a-b)\equiv 0 \pmod{p^k}$ Let $p$ be an odd prime number, $a,b\in\mathbb{Z}$ such that $\gcd(a,p)=\gcd(b,p)=1$ and $a\equiv b\pmod{p}$. Prove that $a^ n\equiv b^n\pmod{p^k}$ if and only if $n(a-b)\equiv 0 \pmod {p^k}$ in which $k,n\in\mathbb{N}$.
This is what I did(spoiler: I did almost nothing):
$p$ is an odd prime number, therefore $(\mathbb{Z}/p^k\mathbb{Z})^\times =\{\overline{x}\in\mathbb{Z}/p^k\mathbb{Z}:\gcd (x,p^k)=1\}$ with the multiplication is a cyclic group. By hypothesis we have that $\gcd(a,p)=1$ and $\gcd(b,p)=1$. Therefore $\gcd(a,p^k)=1$ and $\gcd(b,p^k)=1$ which implies that $\overline{a},\overline{b}\in (\mathbb{Z}/p^k\mathbb{Z})^\times$.
Let $\varphi(n)$ be the Euler's totient function. Then the cardinality of $(\mathbb{Z}/p^k\mathbb{Z})^\times$ is $\varphi(p^k)=(p-1)p^{k-1}$.
$(\Rightarrow)$ Suppose that $\overline{a}^n=\overline{b}^n$. Therefore $\overline{ab^{-1}}^n=1$.
My strategy is to prove that $ab^{-1}$ is a generator of the group $(\mathbb{Z}/p^k\mathbb{Z})^\times$ because this implies that $\varphi(p^k)$ is the order of $ab^{-1}$ which implies that $\varphi(p^k)|n$. I believe that this can indeed occur since, by hypothesis, $a\equiv b\mod p\Rightarrow ab^{-1}\equiv 1\pmod{p}$. But unfortunately I could not prove it. 
If $\varphi(p^k)|n$, then exists $m\in\mathbb{Z}$ such that $n=\varphi(p^k)m$. We know that $a-b=cp$ in which $c\in\mathbb{Z}$. Therefore $n(a-b)=(p-1)p^{k-1}mcp=(p-1)p^kcm\Rightarrow n(a-b)\equiv 0 \mod p^k$. Therefore we can prove this implication if $\varphi(p^k)|n$. But does this actually occur?
Could someone please help me?
Below are some lemmas that may be helpful.
Lemma 1: Let $p$ be a prime number. If the class of $x\in\mathbb{Z}$ generates $\mathbb{Z}/p\mathbb{Z}$ then $\overline{x}$ or $\overline{x+p}$ generates $(\mathbb{Z}/p^2\mathbb{Z})^\times$.
Lemma 2: Let $p$ be an odd prime number. If the class of $x\in\mathbb{Z}$ generates $(\mathbb{Z}/p^2\mathbb{Z})^\times$ then it also generates $(\mathbb{Z}/p^k\mathbb{Z})^\times$.
Lemma 3: Let $m\geq 1$ be an integer. Then $|\{\overline{x}\in (\mathbb{Z}/p^k\mathbb{Z})^\times :\overline{x}^m=1\}|=\gcd(m,\varphi (p^k))$. Here |A| means the cardinality of the set $A$.

EDIT: I realized that the above strategy will not work. To see this, just pick $(p,a,b,k,n)=(3,5,2,2,3)$. But I thought of other strategies:
We know that $\overline{ab^{-1}}^n=\overline{1}$. Let $c=ab^{-1}$.
Therefore $c^n\equiv 1\pmod {p^k}\Rightarrow (c-1)(1+c+\cdots +c^{n-1})\equiv 0\pmod {p^k}$.
If we demonstrate that $1+c+\cdots +c^{n-1}\equiv n\pmod {p^k}$, then we will finish the demonstration. Maybe we can prove this using $c=ab^{-1}\equiv 1\pmod p$.
 A: This is acutually trivial if you know the LTE lemma. It says that if we have $p\mid a-b$ with $(p,a)=(p,b)=1$ and $p$ being an odd prime (Note that these are the exact same conditions in the OP) then $$\nu_{p}(a^n-b^n)=\nu_{p}(a-b)+\nu_{p}(n)=\nu_p((a-b)n).$$
But since $p^k\mid a^n-b^n$ we have $\nu_{p}(a^n-b^n)\ge k$ therefore $$\nu_p ((a-b)n)\ge k$$
Which by definition means $p^k\mid (a-b)n$.
A: Here's a proof of the reverse implication . . .

Claim:

If $p,a,b,k,n$ are such that


*

*$p$ is prime.$\\[4pt]$

*$a,b$ are integers such that $p{\mid}(a-b)$.$\\[4pt]$

*$k,n$ are positive integers for which $p^k{\,{\large{\mid}}\,}\bigl(n(a-b)\bigr)$.


then $p^k{\,{\large{\mid}}\,}\bigl(a^n-b^n\bigr)$.

Proof:

If $a=b$, the truth of the claim is immediate, so assume $a\ne b$.

Next, a lemma . . .

Lemma:

If $m$ is a positive integer, and $x,y$ are distinct integers such that $m{\mid}(x-y)$, then $m\,{\Large{\mid}}\!\left(\!{\Large{\frac{x^m-y^m}{x-y}}}\!\right)$.

Proof of the lemma:

Since $m{\mid}(x-y)$, we have $x\equiv y\;(\text{mod}\;m)$, so
\begin{align*}
\frac{x^m-y^m}{x-y}
&=\sum_{i=1}^p x^{m-i}y^{i-1}\\[4pt]
&\equiv \sum_{i=1}^m x^{m-i}y^{i-1}\;(\text{mod}\;m)\\[4pt]
&\equiv \sum_{i=1}^m x^{m-i}x^{i-1}\;(\text{mod}\;m)\\[4pt]
&\equiv \sum_{i=1}^m x^{m-1}\;(\text{mod}\;m)\\[4pt]
&\equiv mx^{m-1}\;(\text{mod}\;m)\\[4pt]
&\equiv 0\;(\text{mod}\;m)\\[4pt]
\end{align*}
which completes the proof of the lemma.

Returning to the main proof . . .

Let $j$ be such that $p^j||(a-b)$.

Since $p^k{\,{\large{\mid}}\,}\bigl(n(a-b)\bigr)$, it follows that $p^h{\mid\,}n$, where $h=k-j$.

Identically, we have
$$a^{p^h}-b^{p^h}=(a-b)\prod_{i=1}^h\frac{a^{p^i}-b^{p^i}}{a^{p^{i-1}}-b^{p^{i-1}}}$$

Applying the lemma, each of the factors
$$\frac{a^{p^i}-b^{p^i}}{a^{p^{i-1}}-b^{p^{i-1}}}$$
is a multiple of $p$, hence, since there are $h$ such factors, we get
$$p^h{\Large{\mid}}\prod_{i=1}^h\frac{a^{p^i}-b^{p^i}}{a^{p^{i-1}}-b^{p^{i-1}}}$$
then, since $p^j{\mid}(a-b)$, and $j+h=k$, we get
$$p^k{\,{\large{\mid}}\,}\bigl(a^{p^h}-b^{p^h}\bigr)$$
and since $p^h{\mid\,}n$, we get 
$$(a^{p^h}-b^{p^h}\bigr){\,{\large{\mid}}\,}\bigl(a^n-b^n\bigr)$$
hence
$$p^k{\,{\large{\mid}}\,}\bigl(a^n-b^n\bigr)$$
as was to be shown.
A: Since someone has already proved the right implication, I thought the following Lemma might help with the left:

Lemma:$$\tag{1}a \equiv b \pmod{rq } \implies a^r \equiv b^r \pmod{r^2 q}.$$

My attempt to use the Lemma:
For the case $k=2^m$, let $q=1$ and $r=p$ in $(1)$, then $$\tag{2}a^p\equiv b^p\pmod{p^2}.$$
Now, let $a’=a^p$, $b’=b^p$, and $p’=p^2$ in $(2)$, then by another application of $(1)$ $$(a’)^{p’}\equiv(b’)^{p’}\pmod{\left(p’\right)^2}\\\implies a^{p^3}\equiv b^{p^3}\pmod{p^4}.$$
Continuing this process, we eventually get $$\tag{3} a^{p^t}\equiv b^{p^t}\pmod{p^k}.$$
From $(3)$, I think if $$a\not\equiv b\pmod{p^k},$$ then assuming $$a^n\equiv b^n\pmod{p^k},$$ should imply that $n$ is also some power of $p$, from which it follows $$n(a-b)\equiv 0\pmod{p}.$$
A: The person whose only tool is a hammer sees every problem as a nail. The $p$-adic approach isn’t my only tool, but I see $p$-adic phenomena in this every nice problem. I’ll try to hide my prejudice, though.
Given our odd prime $p$, I’m going to measure divisibility of an integer by $p$ with the function $v:\Bbb Z^{\ne0}\to\Bbb Z^{\ge0}$. Its definition is that if $z=p^kw$, where $\gcd(p,w)=1$, then $v(z)=k$. That is, $v$ just counts how many $p$’s there are in $z$. You see that $v(zz')=v(z)+v(z')$, and that if $v(z')>v(z)$, then $v(z+z')=v(z)$.
Using $v$, then, I can restate your problem as: if $v(a)=v(b)=0$ and $v(a-b)\ge0$, we have the equivalence
$$
v(a^n-b^n)\ge k\Leftrightarrow v(n(a-b))\ge k\,.
$$
Now, although it’s not essential, I’m going to take the special case $a=1$. For me, things become a little more conceptual that way. Then I’m going to put forth a series of restatements of the problem, which I hope you’ll see are equivalent to the original one. After it’s all over, I’ll deal with general $a$, not just $a=1$.
Statement. $v(1-b^n)\ge k\Leftrightarrow v(n)+v(1-b)\ge k$.
Restatement 1. $v(1-b^n)=k\Leftrightarrow v(n)+v(1-b)=k$.
Restatement 2. $v(1-b^n)=v(n)+v(1-b)$.
Restatement 3. Set $b=1+\varepsilon$ (so that $1-b=-\varepsilon)$, and similarly $b^n=1+\varepsilon'$. Then $v(\varepsilon')=v(n)+v(\varepsilon)$.
Restatement 4. If $v(\varepsilon)\ge1$, then $v\bigl((1+\varepsilon)^n-1\bigr)=v(n)+v(\varepsilon)$.
It’s this last restatement that I’m going to prove, first for $n$ prime to $p$ and then for $n=p^k$. You see that these combine to prove the last restatement.
Case 1. Let $\varepsilon\in\Bbb Z$, with $v(\varepsilon)\ge1$, and let $v(m)=0$. Then $v\bigl((1+\varepsilon)^m-1\bigr)=v(\varepsilon)$.
Proof. Expand $(1+\varepsilon)^m$, and see that
$-1+(1+\varepsilon)^m=m\varepsilon+\varepsilon^2w$, for an integer $w$, so that $v(\varepsilon^2w)>v(m\varepsilon)$. The desired equality follows.
Case 2. Let $\varepsilon\in\Bbb Z$, with $v(\varepsilon)\ge1$. Then for $k\ge0$, we get the equality $v\bigl((1+\varepsilon)^{p^k}-1\bigr)=k+v(\varepsilon)$.
Proof. Follows from the case $k=1$, which I now show. Again we expand:
$$
-1+(1+\varepsilon)^p=p\varepsilon+\frac{p(p-1)}2\varepsilon^2+\cdots+p\varepsilon^{p-1}+\varepsilon^p\,,
$$
in which all the terms from the $p\varepsilon$ to the $p\varepsilon^{p-1}$ have a factor of $p\varepsilon^2$ (because $p-1\ge2$: here finally is where we use the hypothesis that $p>2$ !) and the last term $\varepsilon^p$ also is divisible by $p\varepsilon^2$ because $p|\varepsilon$ (here again we use $p>2$). Thus $v\bigl((1+\varepsilon)^p-1\bigr)=1+v(\varepsilon)$, as desired.
So you see that we have proved Restatement 4, which gives us the original boldface Statement.
Now for the general case. Let $v(a-b)=k$. Since $\gcd(a,p^{k+1})=1$, there’s an $a'$ such that $aa'=1+p^{k+1}u$, that is, $a'$ is a modulo-$p^{k+1}$-inverse of $a$. Thus, since $v(1-aa')>k$ we also get $v(1-a^n{a'}^n)>k+v(n)$. Since $v(a')=0$, we see that $v(aa'-ba')=k$. Also,
$$
a(1-ba')=(a-b)+b(1-aa')\,,
$$
where $v(a-b)=k$ and $v\bigl(b(1-aa')\bigr)>k$, so that $v(1-ba')=k$. Now,
$$
a^n-b^n=a^n(1-b^n{a'}^n)\quad-\quad b^n(1-a^n{a'}^n)\,,
$$
where, on the right-hand side, the first block has $v$-value equal to $k+v(n)$ because $v(1-ba')=k$ and the second block has $v$-value greater than $k+v(n)$. Thus $v(a^n-b^n)=k+v(n)=v(a-b)+v(n)$.
A: Let $c\equiv ab^{-1}\pmod{p^k}$, then we can prove instead that
$$
c^n\equiv 1 \pmod{p^k} \Longleftrightarrow n(c-1)\equiv 0 \pmod{p^k}
$$


Lemma. Let $g$ be a generator of $(\mathbb Z/p^k \mathbb Z)^*$, which is also a generator of $(\mathbb Z/p\mathbb Z)^*$. Then
  $$
c \equiv g^{(p-1)w} \pmod{p^k}
$$
  for some integer $w$.

Proof. Let $c\equiv g^u\pmod{p^k}$ for some $0\leq u< p^{k-1}(p-1)$. Since
$$
a\equiv b \pmod p \implies g^u\equiv c\equiv ab^{-1}\equiv 1 \pmod p,
$$
this shows that
$$
u\equiv 0 \pmod{p-1} \implies u=(p-1)w
$$
for some integer $w$.
$$\tag*{$\square$}$$

So we are reduced to proving
$$
g^{(p-1)nw}\equiv c^n\equiv 1\pmod{p^k} \Longleftrightarrow n(g^{(p-1)w}-1)\equiv 0 \pmod{p^k}
$$
The next step is to split the proof depending on how many times $p$ divides $n$. Write
$$
n = p^tm,\quad \gcd(m,p)=1
$$
Case 1: $t\geq k-1$
If $t\geq k-1$, then both sides are trivially true:
$$
\begin{align}
g^{(p-1)nw} &\equiv (g^{(p-1)p^{t}})^{mw} \equiv (1)^{mw} \equiv 1 \pmod{p^k}\\
n(g^{(p-1)w}-1) &\equiv (mp^{t})(c-1) \equiv 0 \pmod{p^k}
\end{align}
$$
(Recall that $c-1 \equiv 0\pmod p$ is a given condition.)   
Case 2: $t\leq k-2$
Next we assume that $0\leq t \leq  k-2$. (We are also assuming $k\geq 2$, since $k=1$ is trivial.) Then starting on the LHS we have
$$
\begin{align}
g^{(p-1)nw}-1 &\equiv 0 \pmod{p^k}\\
g^{(p-1)p^tmw}&\equiv 1 \pmod{p^k}\\
(p-1)p^tmw &\equiv 0 \pmod{p^{k-1}(p-1)}\\
p^tmw &\equiv 0 \pmod{p^{k-1}}\\
p^tw &\equiv 0 \pmod{p^{k-1}},\quad \text{since }\gcd(m,p)=1\\
(p-1)p^tw &\equiv 0 \pmod{p^{k-1}(p-1)}\\
(p-1)w &\equiv 0 \pmod{p^{k-t-1}(p-1)}\\
g^{(p-1)w}-1 &\equiv 0 \pmod{p^{k-t}}\\
m(g^{(p-1)w}-1) &\equiv 0 \pmod{p^{k-t}}\\
p^t m(g^{(p-1)w}-1) &\equiv 0 \pmod{p^k}\\
n(g^{(p-1)w}-1) &\equiv 0 \pmod{p^k}
\end{align}
$$
Since we transformed LHS to RHS, they are equivalent. (Edit 1: I felt like I could have jumped from step 2 to step 8.)
