# 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?

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

• For your approach, $c\equiv ab^{-1} \pmod{p^k}$ need not be a generator. However the given condition $$a\equiv b\pmod p$$ forces $$c \equiv g^{(p-1)w}\pmod{p^k}$$ for some integer $w$ (details in my answer), so it's some power of $g$. Sep 28, 2018 at 15:20

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

• This is a great answer, but there's a couple of issues. First, you should handle $a=b$ as a special case since then $\nu_p(a-b)=\nu_p(a^n-b^n)=\infty$. Second, the OP's condition of $a^n \equiv b^n \pmod{p^k}$ actually means that $\nu_p(a^n-b^n) \ge k$ (e.g., $3^2 \equiv 1\pmod{2^2}$, but $\nu_2(9-1)=3\gt 2$). Thus, you should change what you wrote, along with your next part to then be $\nu_p((a-b)n)\ge k$. Feb 7 at 19:40

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

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

• Unfortunately I don’t know anything about p-adic numbers. Could you suggest an introductory material for me to learn this subject?
– user477271
Sep 29, 2018 at 13:49
• Fernando Gouvêa’s book “$p$-adic Numbers” is the one I like best, @rfloc. Sep 29, 2018 at 21:42

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

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.

• At first glance, it looks right, and probably clearer than my argument. But where did you use the hypothesis that $p\ne2$? Sep 28, 2018 at 13:54
• @Lubin: I didn't use it, but since I'm only proving the reverse implication, is it actually needed? In other words, for the reverse implication, is there a counterexample for the case $p=2$? Sep 28, 2018 at 23:47
• The example is $3^2=9$. For, $v_2(1-3)=1$, but $v_2(1-3^2)=3$. The reason is that $3$ is “too close” to a $p$-th root of unity. When you go to finite extensions of $\Bbb Q_p$, the phenomenon occurs for other values of $p$ than two. This is one of the phenomena that make $2$ the oddest prime. Sep 29, 2018 at 2:24
• @Lubin: But in my answer, I'm only proving the reverse implication, not the equivalence. Sep 29, 2018 at 3:08
• @Lubin: I like your "$2$ is the oddest prime" remark. Sep 29, 2018 at 3:10