# If $a^b\equiv c^b\mod p$, can we conclude that $a\equiv c\mod p$?

If $a^b\equiv c^b\mod p$, is is true that $a\equiv c\mod p$, where $b$ is odd and $p$ is prime?

We know that if $a\equiv c\mod p$, then $a^b\equiv c^b\mod p$. Is the reverse true?

• Upvoters why? How is this question well researched? Jul 25 '15 at 17:09

As the other answers pointed out, the reverse is generally false.

However, if $b$ and $p-1$ are coprime, then $a^b \equiv c^b \bmod p$ implies $a \equiv c \bmod p$.

Proof. If $a \equiv 0 \bmod p$ or $c \equiv 0 \bmod p$ the result is clear (because $p$ is prime), so we will assume that $a \not\equiv 0 \bmod p$ and $c \not\equiv 0 \bmod p$. In this case, Fermat's little theorem shows that $a^{p-1} \equiv 1 \bmod p$ and $c^{p-1} \equiv 1 \bmod p$.

Therefore, for all integers $u,v$, the relation $a^b \equiv c^b \bmod p$ implies $$(a^b)^u(a^{p-1})^v \equiv (c^b)^u(c^{p-1})^v \bmod p$$ By Bezout's theorem we can find integers $u,v$ such that $bu + (p-1)v = 1$, so what we have actually proven is $a^1 \equiv c^1 \bmod p$.

The condition that $b$ and $p-1$ are coprime is actually necessary and sufficient if $p$ is a prime number.

Indeed, if $b$ and $p-1$ are not coprime, we can find integers $b',k$ and $d \geq 2$ such that $b=b'd$ and $p-1 = kd$. Then for all $x$ which is a generator of the cyclic group $(\Bbb Z/p\Bbb Z)^\times$, the integers $a = x^k$ and $c = 1$ will satisfy $$a^b \equiv x^{kb'd} \equiv (x^{p-1})^{b'} \equiv 1 \equiv c^b \bmod p$$ but $a \not\equiv c \bmod p$ because $x^k \equiv 1 \bmod p$ would imply $(p-1) \mid k$, which contradicts $0 < k < p-1$.

• By the way, this explains why the other answers gave the counterexample $b=3$ and $p=7$: it is the smallest possible. Jul 24 '15 at 8:11
• You mean $a^b\equiv c^b\pmod{\! p}$ implies $a\equiv c\pmod{\! p}$. This is a consequence of $a^x\equiv b^x,\, a^y\equiv b^y\,\pmod{\! p}\,\Rightarrow\, a^{\gcd(x,y)}\equiv b^{\gcd(x,y)}\,\pmod{\! p}$ Jul 24 '15 at 8:47
• @user236182: thanks for noticing the typo. Jul 24 '15 at 8:48
• The smallest counterexample is $b=2$ and $p=5$: $1^2 \equiv 4^2 \mod 5$. Mar 29 '16 at 1:24

Hint: Try out some examples with $p=7$ and $b=3$. (The important aspect is that $b\mid p-1$, because $p-1$ is the size of the group $(\mathbb{Z}/p\mathbb{Z})^\times$.)

$$2^3\equiv 1^3\mod7$$but $$2 \not\equiv 1\mod7$$

$2^3=1^3 \mod 7$ and $2 \neq 1\mod 7$ but $(2)=(1)$ as ideals since we are in a field. So if you mean $(a), (b)$ as ideals the assertion is true since we have only one nonzero ideal in a field. But if you mean $(a)=(b)$ as elements there are counter examples.