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 $\displaystyle a^{\varphi(n)} \equiv 1 (\bmod n)$
where $\displaystyle \varphi$ 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 $\displaystyle \varphi(25)=20$ and $\displaystyle \gcd(25,2)=1$, we have $\displaystyle 2^{20}\equiv 1\!\!\!\pmod {25}$, hence $\displaystyle 2^{20000000}\equiv 1\!\!\!\pmod{25}$ (simply by raising the previous equality to some power) and $\displaystyle 2^{200000009}\equiv 2^9\!\!\!\pmod{25}$.
This modular equivalence means that $\displaystyle 25 $ divides $\displaystyle 2^{200000009}-2^9$. On the other hand, it is clear that $\displaystyle 4$ divides this number as well. Since additionally $\displaystyle \gcd(4,25)=1$, Gauss theorem shows that $\displaystyle 100(=4\times 25)$ divides $\displaystyle 2^{200000009}-2^9$. Which means $\displaystyle 2^{200000009}\equiv 2^9\!\!\!\pmod{100}$. And all this works the same with 6 instead of 2.
Finally, we get again the formula $\displaystyle 2^{20000009} + 6^{20000009} + 7^{20000009} \equiv
2^{9} + 6^{9} + 7^{9} \bmod 100$.
I’ll do it this way. Start by noting that
$\displaystyle -4\ \equiv\ 1\pmod5$
$\displaystyle -3\ \equiv2\ \pmod5$
$\displaystyle \therefore\ -3(-4)^k\ \equiv\ 2\pmod5$ for all $\displaystyle k\geqslant0$
Multiplying through by 5 gives
$\displaystyle -15(-4)^k\ \equiv\ 10\pmod{25}\quad\ldots\ \fbox1$
Next I’ll show that $\displaystyle 4(-9)^k-3(-4)^k\equiv1\pmod{25}$ for all $\displaystyle k\geqslant0.$
The congruence is obviously true for $\displaystyle k=0$. If it holds for some $\displaystyle k\geqslant0$ then
$\displaystyle 4(-9)^{k+1}-3(-4)^{k+1}\ =\ -36(-9)^k+12(-4)^k$
___________________.$\displaystyle =\ -9\left[4(-9)^k-3(-4)^k\right]-15(-4)^k$
___________________.$\displaystyle \equiv\ -9+10=1\pmod{25}$ by inductive hypothesis and $\displaystyle \fbox1.$
Hence, by induction, we $\displaystyle 4(-9)^k-3(-4)^k\equiv1\pmod{25}$ for all $\displaystyle k\geqslant0,$ i.e.
$\displaystyle 8(-9)^k-6(-4)^k\equiv2\pmod{25}\quad\ldots\ \fbox2$
Now
$\displaystyle 2^4=16\equiv-9\pmod{25}$ $\displaystyle \Rightarrow$ $\displaystyle 2^{4n-1}=2^{4(n-1)+3}\equiv8(-9)^{n-1}\pmod{25}$
$\displaystyle 6^4=1296\equiv-4\pmod{25}$ $\displaystyle \Rightarrow$ $\displaystyle 6^{4n-1}=6^{4(n-1)+3}\equiv216(-4)^{n-1}\pmod{25}\equiv-9(-4)^{n-1}\pmod{25}$
Hence
$\displaystyle 2^{4n-1}+9\cdot6^{4n-1}\ \equiv\ 8(-9)^{n-1}-81(-4)^{n-1}\pmod{25}$
_______________...$\displaystyle \equiv\ 8(-9)^{n-1}-6(-4)^{n-1}$
_______________...$\displaystyle \equiv\ 2\pmod{25}$ by $\displaystyle \fbox2$
Multiplying through by 4 gives
$\displaystyle 4\cdot2^{4n-1}+36\cdot6^{4n-1}\ \equiv\ 8\pmod{100}$
i.e.
$\displaystyle 2^{4n+1}+6^{4n+1}\ \equiv\ 8\pmod{100}$
Finally, note that $\displaystyle 7^{4n+1}\equiv7\pmod{100}$ since $\displaystyle 7^4=2401.$
Hence
$\displaystyle \fbox{$2^{4n+1}+6^{4n+1}+7^{4n+1}\ \equiv\ 15\pmod{100}\ \mbox{for all}\ n\in\mathbb Z^+$}$
which is the result you want.