3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Upvoters why? How is this question well researched? $\endgroup$
    – Alec Teal
    Jul 25 '15 at 17:09
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ By the way, this explains why the other answers gave the counterexample $b=3$ and $p=7$: it is the smallest possible. $\endgroup$
    – Siméon
    Jul 24 '15 at 8:11
  • $\begingroup$ 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}$ $\endgroup$
    – user236182
    Jul 24 '15 at 8:47
  • 1
    $\begingroup$ @user236182: thanks for noticing the typo. $\endgroup$
    – Siméon
    Jul 24 '15 at 8:48
  • $\begingroup$ The smallest counterexample is $b=2$ and $p=5$: $1^2 \equiv 4^2 \mod 5$. $\endgroup$
    – mathguy
    Mar 29 '16 at 1:24
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.