1

So, if we know that $a\equiv b\pmod n $ under what circumstances can we say that:

$${x^a}\equiv {x^b}\pmod n$$

It seems through experimental evidence that this works for $n=10$, but does it work for all $a,b,x$ when $n=10$? What about other values for $n$?

hardmath
  • 37,015
Aaron Carter
  • 11
  • 1

1 Answers1

0

This does not work in general. In your case, $2 = 12 \mod 10$ but $3^2 \ne 3^{12} \mod 10$.

The correct statement covering this situation is given by Euler's Theorem which says essentially that if $x$ and $n$ are coprime, then $a = b \mod \varphi(n)$ implies that $x^a = x^b \mod n$. Here $\varphi$ is Euler's totient function (see the wikipedia article).

Hans Engler
  • 15,439
  • Thank you very much so for explaining this in full for me. Side question that arose from this, is there some way to solve the inverse of Euler's Totient function? For instance if you knew that phi(n) = 4, is there any way to figure out what n is? – Aaron Carter Oct 21 '17 at 02:34
  • There is usually more than one solution of $\phi(n) = m$. For example $\phi(5) = \phi(8) = 4$. Carmichael conjectured in fact that there is always more than one solution. It is known that the number of solutions can become arbitrarily large. This question seems to be largely open. – Hans Engler Oct 21 '17 at 20:35