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?
Answer
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$.
No comments:
Post a Comment