1. ## Last two digits...

Determine the last two digits of :

2^(20000009) + 6^(20000009) + 7^(20000009)...

thanks a lot for the help....

Regards,
Vedic

2. Originally Posted by Vedicmaths
Determine the last two digits of :

2^(20000009) + 6^(20000009) + 7^(20000009)...

thanks a lot for the help....

Regards,
Vedic
By Fermat's Little Theorem,
$\displaystyle 2^{20000009} + 6^{20000009} + 7^{20000009} \equiv 2^{9} + 6^{9} + 7^{9} \bmod 100$

I would use brute force from here, since it's just cubing the last 2 digits 3 times.

3. That is correct.

4. 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...

5. Originally Posted by Vedicmaths
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.

6. Hi,
Originally Posted by LegendWayne
By Fermat's Little Theorem,
$\displaystyle 2^{20000009} + 6^{20000009} + 7^{20000009} \equiv 2^{9} + 6^{9} + 7^{9} \bmod 100$

I would use brute force from here, since it's just cubing the last 2 digits 3 times.

Originally Posted by Vedicmaths
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...
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.

7. Originally Posted by Moo
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$.

8. 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.