Prove that $a^ n\equiv b^n\pmod{p^k}$ if and only if $n(a-b)\equiv 0 \pmod{p^k}$

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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.