Determine the last two digits of :
2^(20000009) + 6^(20000009) + 7^(20000009)...
thanks a lot for the help....
Regards,
Vedic
Sir, thank you very much for the kind help but I dont know what is this Brute force...I have learned a little bit about Fermet's Theorem but have no idea how you ended up getting 2^9 + 6^9 + 7^9....
so how do I apply the mod 100 here??
thanks a lot for the help...
"brute force" is the act of doing all of the calculations:
2*2*2*2*2*2*2*2*2 + 6*6*6*6*6*6*6*6*6 + 7*7*7*7*7*7*7*7*7
that will yield some number
however, a little smarter way:
7*7 = 49
49*7 = 343 . if you take the last two digits: 43 then you have
7^3 mod 100 .
43 * 43 = 1849. 1849 mod 100 = 49
that means 7^3 * 7^3 mod 100 = 49
thus,
7^3 mod 100 = 43
7^6 mod 100 = 49
7^9 mod 100 = 43*49 = 2107 mod 100 = 7
brute force is merely doing all of the calculations without doing the mental work to take some smart short cuts.
BTW: 7*7*7*7*7*7*7*7*7 = 40353607
If you divide that number by 100, then the last two digits will be your remainder; the last two digits is that number mod 100.
Hi,
The above is not correct...
It's not even Fermat's little theorem LegendWayne used, because 100 is not a prime number !
Euler's theorem would be more appropriate.
If gcd(a,n)=1, then
where stands for Euler's totient function.
BUT gcd(2,100) and gcd(6,100) are not 1 ! So you can't apply directly Euler's theorem for 2 and 6.
Good point. The computation will turn out to be correct, but the justification was not.
What Euler's theorem tells: since and , we have , hence (simply by raising the previous equality to some power) and .
This modular equivalence means that divides . On the other hand, it is clear that divides this number as well. Since additionally , Gauss theorem shows that divides . Which means . And all this works the same with 6 instead of 2.
Finally, we get again the formula .
I’ll do it this way. Start by noting that
for all
Multiplying through by 5 gives
Next I’ll show that for all
The congruence is obviously true for . If it holds for some then
___________________.
___________________. by inductive hypothesis and
Hence, by induction, we for all i.e.
Now
Hence
_______________...
_______________... by
Multiplying through by 4 gives
i.e.
Finally, note that since
Hence
which is the result you want.