0
$\begingroup$

Lately I was studying about Modular Arithmetic and the way modulus is used to calculate large numbers. What caught my attention was calculating powers with modulus. It's generally that we calculate the mod of the base and then proceed with our further calculations. Now I was thinking, is it possible to take mod of the power and then mod of that answer to produce the same answer as $(a^b)$%m.

I tried on a few examples to see myself but the answers matched sometimes or would differ many times. So is this really possible with some linear relation, maybe, in the answers by the two methods or is it just not possible?

$\endgroup$
  • 1
    $\begingroup$ Euler's theorem might be an interesting read for you. $\endgroup$ – Math Lover Jul 12 '18 at 21:50
  • $\begingroup$ Please, can you explain it specifically to this question? Euler's Theorem uses the Euler-Totient function but here my power is a mod of some other number. How do I relate? $\endgroup$ – sh1ve9 Jul 12 '18 at 21:59
  • 1
    $\begingroup$ That's simple: if $a$ and the modulus $n$ are coprime, then $ a^b\equiv a^{b\bmod\varphi(n)}\mod n$ by Euler's theorem. $\endgroup$ – Bernard Jul 12 '18 at 22:05
  • $\begingroup$ Oh I see. However if I wish to calculate $b$ mod any arbitrary number, maybe 13 to say evaluate to $x$ ($b$mod 13 = $x$) and then proceed with $a^x$%13. How wrong or correct would this be? @Bernard $\endgroup$ – sh1ve9 Jul 12 '18 at 22:11
  • $\begingroup$ I don't understand what $a^x&%13 denotes. $\endgroup$ – Bernard Jul 12 '18 at 22:14
1
$\begingroup$

If you're asking whether $a^b \pmod x = a^{b\pmod x} \pmod x$, then the answer is no.

Counterexample: $2^{10} \equiv 4 \neq 2^{10 \pmod 5} \pmod 5$

$\endgroup$
  • $\begingroup$ I just wanted a way to reduce the power using modulus. After a read on Euler-totient I found that instead of power % $x$ it should be power % $phi(m)$ and then we can calculate the answer. So I have my problem pretty much solved! $\endgroup$ – sh1ve9 Jul 13 '18 at 16:05
0
$\begingroup$

You obviously can't assume that if $w \equiv v \mod n$ that $b^w \equiv b^v \mod n$. There is simply no reason that should be true and obvious reasons it should be false. [$w\equiv v \mod n \implies w = v + kn$ for some $k \implies b^w = b^{v + kn}=b^v*b^{kn}$ and why the @\$^# would anyone think $b^v*b^{kn}\equiv b^v\mod n$?]

HOWEVER If $b^m \equiv 1 \mod n$ and $w \equiv v \mod m$ then $w = v + km$ for some $k$ and $b^w = b^{v + km} = b^v*(b^m)^k \equiv b^v*(1^k) \equiv b^v \mod n$.

So you can do modulus to powers provide the modulus that use to evaluate the power is not the same modulus you use to evaluate the bases, but is instead a different modulus $m$ with the property in conjunction with the base $b$ that $b^m \equiv 1 \mod n$.

A fundamental result (Euler's theorem) will be if you have modulus $n$ and a base $b$ so that $b$ and $n$ are relatively prime and that $m = $ then number of natural numbers less than $n$ that are relatively prime to $n$ then $b^m \equiv 1 \mod n$ and then, yes,

you can state: If $a \equiv b \mod n$ and $\gcd(b, n) = 1$ and $w \equiv v \mod m$ (where $m$ is the same $n$ as in the previous paragraph) then $a^w \equiv b^v \mod n$.

$\endgroup$
  • $\begingroup$ I understand the explanation, though I'd say Bernard solved it in an easier way and more 'exactly'! Thanks for the help though! $\endgroup$ – sh1ve9 Jul 13 '18 at 16:06

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.