Posted by Blank on Monday, August 27, 2007 at 1:14am.
Use arithmetic Modulo 100. The Mod operator is defined as follows:
x Mod y is, by definition, the remainder you get when you divide x by y. This is the same as subtracting from x that multiple of y that makes the resulting number smaller than y.
Example
12 mod 5 = 2
If you divide 12 by 5 then the remainder is 2.
12 - 2*5 = 2
If we take Mod 100 a number, then we obtain the last two digits. Of course, in case of this problem we don't want to calculate the number first and then take Mod 100. Fortunately this is not necessary as the Mod of a product is the Mod of the product of the Mods.
To avoid awkward notations with the Mod symbol, it is customary to simply use the equals sign when doing calculations Mod some fixed number. So, let's calculate 5^347 Mod 100 and let's write a = b whenever a Mod 100 = b Mod 100.
We have:
5^3 = 125 = 25 = 5^2
This implies that 5^n = 25 for any
n > 1. If n = 2 or 3 then we already know that this is true. If n is larger, then:
5^n = 5^3 5^(n-3) = 5^2 5^(n-3) =
5^(n-1)
So, you can just subtract 1 from the exponent and eventually the exponent will become 3 in which case the number is 25.