1st some general exponent rules background If x and y are integers: Modular arithmetic rules We can write any integer as x = k * z + r
x^y says: take x and multiply it by itself y times
i.e. x^4=x * x * x * x
(x^y)^z says: take x and multiply it by itself y times then multiply that result by itself z times. But this is the same as multiplying x by itself y * z times, which is the same as multiplying x by itself z * y times.
i.e. (x^4)^3=(x * x * x * x) * (x * x * x * x) * (x * x * x * x)
= (x * x * x) * (x * x * x) * (x * x * x)*(x * x * x) = (x^3)^4
So (x^y)^z = x^(y * z) = (x^z)^y
This comes from long division. We divide x by z, we get some quotient k, and a remainder r (our modulus).
So when we look for x mod z , we get r and we don't care what the value of k is, as long as it is an integer.
So now we'll show that (x * y) mod z = (x mod z) * (y mod z) mod z
We write x as x = k1 * z + r1. We can see x mod z = r1
We write y as y= k2* z + r2. We can see y mod z= r2
The left hand side of the equation
x * y = ( k1 * z + r1 ) * ( k2* z + r2 )
= k1 * k2 * z * z + k1 * z * r2 + r1 * k2 * z + r1 * r2
Group all the terms multiplied by z
= ( k1 * k2 * z + k1 * r2 + r1 * k2 ) * z + r1 * r2
= (A bunch of integers ) * z + (r1 * r2)
So if r1 * r2 < z it should be clear that if we divide this by z our remainder (modulus) will be r1 * r2. Note that, if we take the r1 * r2 mod z in this case we still get r1 * r2.
If r1 * r2 >= z we can write r1 * r2 as:
( r1 * r2 ) = k3 * z + r3, Here if we divide r1 * r2 by z we clearly get r3.
So we can write x * y as
x * y = (A bunch of integers ) * z + (r1 * r2)
=(A bunch of integers ) * z + (k3 * z + r3)
=(A bunch of integers + k3 ) * z + (r3)
The mod of x * y is r3, but that is the same as the mod of r1 * r2 !
So in both case (x * y) mod z = (r1 * r2) mod z
(x * y) mod z = r1 * r2 mod z
Right hand side of the equation
we already showed x mod z = r1 and y mod z= r2
(x mod z) * ( y mod z) mod z = r1 * r2 mod z
So the left hand side and the right hand side of the equations agree. They are equal !
So when we have something like:
(3^b mod 17)^a mod 17 = 3^b^a mod 17
The left hand side is the same as taking (3^b mod 17) multiplied by itself a times
then taking the result modulo 17.
But we now know that (x * y) mod z = (x mod z) * (y mod z) mod z
so:
we can flip the left and right side of our equation (3^b mod 17)^a mod 17 = 3^b^a mod 17
to become 3^b^a mod 17 = (3^b mod 17)^a mod 17
(3^b^a) mod 17 = (3^b mod 17) * (3^b mod 17) * .... (3^b mod 17) mod 17
(the right hand side has (3^b mod 17) multiplied by itself a times )
So we see that we can apply the rule (x * y) mod z = (x mod z) * (y mod z) mod z here.
If it is not obvious why we can use the rule here, then imagine how we could break the problem down:
(3^b^a ) mod 17 = 3^b^a mod 17
break down the largest term on the right
(3^b^a ) mod 17 = (3^b^(a-1) * 3^b ) mod 17
apply our rule
(3^b^a ) mod 17 = (3^b^(a-1) mod 17) * (3^b mod 17) mod 17
break down the largest term on the right
(3^b^a ) mod 17 = (3^b^(a-2) * 3^b mod 17) * (3^b mod 17) mod 17
apply our rule
(3^b^a ) mod 17 = (3^b^(a-2) mod 17) * (3^b mod 17) * (3^b mod 17) mod 17
....
repeat this process until we have
(3^b^a) mod 17 = (3^b mod 17) * (3^b mod 17) * .... (3^b mod 17) mod 17
We have also proven before that 3^b^a=3^a^b
So that should just about do it.
Hope this makes sense
