Results 1 to 8 of 8

Math Help - Last two digits...

  1. #1
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1

    Post Last two digits...

    Determine the last two digits of :

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

    thanks a lot for the help....


    Regards,
    Vedic
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2009
    Posts
    11
    Quote Originally Posted by Vedicmaths View Post
    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,
     <br />
2^{20000009} + 6^{20000009} + 7^{20000009} \equiv<br />
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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    591
    That is correct.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1

    Post

    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...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by Vedicmaths View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hi,
    Quote Originally Posted by LegendWayne View Post
    By Fermat's Little Theorem,
     <br />
2^{20000009} + 6^{20000009} + 7^{20000009} \equiv<br />
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.

    Quote Originally Posted by Vedicmaths View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Moo View Post
    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<br />
2^{9} + 6^{9} + 7^{9} \bmod 100.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How many digits?
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 19th 2011, 11:51 AM
  2. Replies: 7
    Last Post: November 28th 2010, 09:22 PM
  3. Digits
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 23rd 2010, 05:11 AM
  4. Sum of the digits
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 7th 2008, 03:50 AM
  5. Replies: 2
    Last Post: April 3rd 2007, 12:31 PM

Search Tags


/mathhelpforum @mathhelpforum