# Math Help - Last two digits...

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,
$
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,
$
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 $a^{\varphi(n)} \equiv 1 (\bmod n)$
where $\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 $a^{\varphi(n)} \equiv 1 (\bmod n)$
where $\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 $\varphi(25)=20$ and $\gcd(25,2)=1$, we have $2^{20}\equiv 1\!\!\!\pmod {25}$, hence $2^{20000000}\equiv 1\!\!\!\pmod{25}$ (simply by raising the previous equality to some power) and $2^{200000009}\equiv 2^9\!\!\!\pmod{25}$.

This modular equivalence means that $25$ divides $2^{200000009}-2^9$. On the other hand, it is clear that $4$ divides this number as well. Since additionally $\gcd(4,25)=1$, Gauss theorem shows that $100(=4\times 25)$ divides $2^{200000009}-2^9$. Which means $2^{200000009}\equiv 2^9\!\!\!\pmod{100}$. And all this works the same with 6 instead of 2.

Finally, we get again the formula $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

$-4\ \equiv\ 1\pmod5$
$-3\ \equiv2\ \pmod5$

$\therefore\ -3(-4)^k\ \equiv\ 2\pmod5$ for all $k\geqslant0$

Multiplying through by 5 gives

$-15(-4)^k\ \equiv\ 10\pmod{25}\quad\ldots\ \fbox1$

Next I’ll show that $4(-9)^k-3(-4)^k\equiv1\pmod{25}$ for all $k\geqslant0.$

The congruence is obviously true for $k=0$. If it holds for some $k\geqslant0$ then

$4(-9)^{k+1}-3(-4)^{k+1}\ =\ -36(-9)^k+12(-4)^k$

___________________. $=\ -9\left[4(-9)^k-3(-4)^k\right]-15(-4)^k$

___________________. $\equiv\ -9+10=1\pmod{25}$ by inductive hypothesis and $\fbox1.$

Hence, by induction, we $4(-9)^k-3(-4)^k\equiv1\pmod{25}$ for all $k\geqslant0,$ i.e.

$8(-9)^k-6(-4)^k\equiv2\pmod{25}\quad\ldots\ \fbox2$

Now

$2^4=16\equiv-9\pmod{25}$ $\Rightarrow$ $2^{4n-1}=2^{4(n-1)+3}\equiv8(-9)^{n-1}\pmod{25}$

$6^4=1296\equiv-4\pmod{25}$ $\Rightarrow$ $6^{4n-1}=6^{4(n-1)+3}\equiv216(-4)^{n-1}\pmod{25}\equiv-9(-4)^{n-1}\pmod{25}$

Hence

$2^{4n-1}+9\cdot6^{4n-1}\ \equiv\ 8(-9)^{n-1}-81(-4)^{n-1}\pmod{25}$

_______________... $\equiv\ 8(-9)^{n-1}-6(-4)^{n-1}$

_______________... $\equiv\ 2\pmod{25}$ by $\fbox2$

Multiplying through by 4 gives

$4\cdot2^{4n-1}+36\cdot6^{4n-1}\ \equiv\ 8\pmod{100}$

i.e.

$2^{4n+1}+6^{4n+1}\ \equiv\ 8\pmod{100}$

Finally, note that $7^{4n+1}\equiv7\pmod{100}$ since $7^4=2401.$

Hence

$\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.