Last two digits...

**Vedicmaths** · April 13th 2009, 07:42 PM

Determine the last two digits of :

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

thanks a lot for the help....

Regards,
Vedic

**LegendWayne** · April 14th 2009, 05:45 AM

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.

**aidan** · April 14th 2009, 06:46 AM

That is correct.

**Vedicmaths** · April 16th 2009, 12:23 PM

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

**aidan** · April 16th 2009, 12:46 PM

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.

**Moo** · April 16th 2009, 12:51 PM

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.

**Laurent** · April 16th 2009, 01:52 PM

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

**JaneBennet** · April 16th 2009, 07:57 PM

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.

Thread: Last two digits...

LinkBack

Thread Tools

Display

Last two digits...

Similar Math Help Forum Discussions

How many digits?

Sum of squares of digits dividing the number with those digits

Digits

Sum of the digits

[SOLVED] How many numbers of n digits exist if the sum of all digits is s?

Search Tags