2
$\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$
8
  • 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$ – resound 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$ – resound Jul 12 '18 at 22:11
  • $\begingroup$ I don't understand what $a^x&%13 denotes. $\endgroup$ – Bernard Jul 12 '18 at 22:14
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$
1
  • $\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$ – resound Jul 13 '18 at 16:06
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$
1
  • $\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$ – resound Jul 13 '18 at 16:05
0
$\begingroup$

I'm going to guess what the intent of your question is. Two columns of numbers below are surmounted by arrows pointing downward. In the first of those columns, going from each horizontal row to the next, one multiplies by $3$ and reduces modulo $11$ at each step. In the second of those two columns, one reduces modulo $11$ only after multiplying (unreduced) numbers. My guess is that the intent of the question is this: Will these always be the same? The answer to that is "yes". Further comments appear below this table. $$ \begin{align} \downarrow\phantom{\pmod{11}} & & & & \downarrow \\ (3^1 \equiv 3) \pmod {11} & \qquad & & 3^1 = 3 & \equiv 3 \\ (3^2 \equiv 9) \pmod {11} & & & 3^2=9 & \equiv9 \\ (3^3 \equiv 3\times 9= 27 \equiv 5) \pmod {11} & & & 3^3 = 3\times9 = 27 & \equiv 5 \\ (3^4 \equiv 3\times 5 = 15 \equiv 4) \pmod{11} & & & 3^4 = 3\times27 = 81 & \equiv 4 \\ (3^5 \equiv3\times 4 = 12 \equiv1) \pmod{11} & & & 3^5 = 3\times81 = 243 & \equiv 1 \\ (3^6 \equiv 3\times 1 = 3 \equiv 3) \pmod{11} & & & 3^6 = 3\times243 = 729 & \equiv3 \end{align} $$ That these are always the same follows from this theorem: \begin{align} \text{Suppose } & (a \equiv b) & & \pmod n \\ \text{and } & (c \equiv d) & & \pmod n. \\[4pt] \text{Then } & (ac \equiv bd) & & \pmod n. \end{align} Proof: \begin{align} & ac-bd \\[8pt] = {} & (ac-bc) + (bc-bd) \\[8pt] = {} & c(a-b) + b(c-d) \\[8pt] = {} & c\cdot\Big(n\times\text{something}\Big) + b\cdot\Big(n\times \text{something}\Big) \\[8pt] = {} & n\times\text{something.} \end{align}

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