0
$\begingroup$

Assume that $a \equiv b \text{ (mod m)}$, the following: $$a^n\equiv b^n \text{ (mod m)}$$ is true.

However, does $a^n\equiv b^n \text{ (mod m)}$ imply that $a \equiv b \text{ (mod m)}$ is true when n is odd?

If n is odd, it seems like this is justifiable because negative numbers do not become positive numbers if raised to an odd power.

Also would it be true for when n is even if say $a^n\equiv b^n \text{ (mod m)}$ imply $a \equiv ±b \text{ (mod m)}$?

$\endgroup$
  • $\begingroup$ No, its is not true. For example, if $m=7$ and $n=3$, then $2^3\equiv 1^3 \pmod{7}$, but $2\not{\equiv} 1 \pmod{7}$. $\endgroup$ – xarles Jul 29 '18 at 6:52
2
$\begingroup$

The above example by Lord Shark the Unknown indicates that no complete answer can be found. But sometimes, we do have that kind of higher cancellation:

We have, by telescopic sum, $$ a^n - b^n = (a - b) \sum_{j=0}^{n-1} a^{n-1-j}b^j, $$ so that $a^n \equiv b^n \mod m$ implies $a \equiv b \mod m$ if $$ \sum_{j=0}^{n-1} a^{n-1-j}b^j $$ is not a zero divisor.

$\endgroup$
0
$\begingroup$

$2^3\equiv4^3\pmod 7$, but $2\not\equiv4\pmod7$.

$\endgroup$
0
$\begingroup$

First, all you say about being positive or negative modulo $n$ makes really no sense, since $a\equiv a-m \pmod{m}$, so any positive number is equivalent to a negative number and viceversa.

However, there is a natural condition to put on $n$ related to $m$, if $m$ is prime: if $n$ and $m-1$ are coprime (so they share no comon divisor) , then $a^n\equiv b^n \pmod{m}$ implies $a \equiv b \pmod{m}$.

$\endgroup$
  • $\begingroup$ Is there a reason they have to be coprime? $\endgroup$ – LHC2012 Jul 29 '18 at 7:08
  • $\begingroup$ See my posting for a counterexample to your final claim. $\endgroup$ – Lord Shark the Unknown Jul 29 '18 at 7:11
  • $\begingroup$ Ups, I forgot to write the $\varphi$ in front of $m$... $\endgroup$ – xarles Jul 29 '18 at 7:16
  • 1
    $\begingroup$ OK, then $2^5\equiv 6^5\pmod 8$ and $2\not\equiv6\pmod 8$. Here $n=5$ and $\phi(m)=4$ are coprime. $\endgroup$ – Lord Shark the Unknown Jul 29 '18 at 7:25
  • 1
    $\begingroup$ Sorry for the errors, now stated in the prime modulus case. If $m$ is not prime, the result is true for the invertible elements modulo $m$, changing $m-1$ by Euler's $\varphi$ function. $\endgroup$ – xarles Jul 29 '18 at 7:35
0
$\begingroup$

For $\gcd(n,\phi(m))=1$, then you will have $a^n\equiv b^n \implies a\equiv b \bmod m.$ (Since $\phi(m)$ is always even for $m>2$, $n$ will always be odd under this condition, but many odd numbers will not fulfill this).

When $\gcd(n,\phi(m))>1$, you can have two (or more) different values producing the same $n$th power - for example, $4^3\equiv 9^3\equiv 29 \bmod 35$.

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