Results 1 to 8 of 8

Math Help - Last two digits...

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    20

    Last two digits...

    I have to find the last two digits of 222227^2010.

    So I know that this gets reduced to 27^2010 mod 100

    But I don't know how to solve 27^x = 1(mod 100) to get this process going. Or am I going about it wrong?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by HeadOnAPike View Post
    I have to find the last two digits of 222227^2010.

    So I know that this gets reduced to 27^2010 mod 100

    But I don't know how to solve 27^x = 1(mod 100) to get this process going. Or am I going about it wrong?
     \phi(100)=40 and  (27,100)=1\implies 27^{40}\equiv1\bmod{100}

    Now  2010=50\cdot40+10 \implies 27^{2010}=27^{50\cdot40+10}=\left(27^{40}\right)^{  50}\cdot27^{10}\equiv1\cdot27^{10}=27^{10}\bmod{10  0} .

    Observe  10=8+2=2^3+2

     27^2\equiv 29\bmod{100}
     27^4=\left(27^2\right)^2\equiv 29^2\equiv 41\bmod{100}
     27^8=\left(27^4\right)^2\equiv 41^2\equiv 81\bmod{100}

    Thus  27^{10}=27^{8+2}=27^8\cdot27^2\equiv 81\cdot29=2349\equiv49\bmod{100}

    Therefore the last two digits of  222227^{2010} are  49 .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    20
    Quote Originally Posted by chiph588@ View Post
     \phi(100)=40 and  (27,100)=1\implies 27^{40}\equiv1\bmod{100}
    This is the part I don't get. What does the phi mean, and what does the (27,100) mean? How did you get that 27^40 = 1 so simply?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,567
    Thanks
    1408
    \phi(100) is the "totient function", the number of integers less than 100 and coprime to 100. Chiph588 then uses "Euler's theorem": For any a coprime to n, a^{\phi(n)}\equiv 1 (mod n).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    20
    What's a quick way to figure out the totient function?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jan 2009
    Posts
    715
     27^{2010} = 3^{6030} = 3^{6028+2} = 9 (81^{1507})


     81^{1507} = (80 + 1)^{1507}

     = 80^{1507} + 80^{1506}(1507) + .... + \frac{1507(1506)}{2} 80^2 + 1507(80) + 1

     \equiv 60+1 \bmod{100} \equiv 61 \bmod{100}

    Therefore ,

     27^{2010} \equiv 9(61) \bmod{100} \equiv 549 \equiv 49 \bmod{100}


    Quote Originally Posted by HeadOnAPike View Post
    What's a quick way to figure out the totient function?

    You may show that  f: x \to ax  ~ a,x \in \mathbb{U}(m) is a bijection . Then , obtaining the product :

     \prod_{x \in \mathbb{U}(m)} x   \equiv \prod_{x \in \mathbb{U}(m)} a x

     1 \equiv a^{\phi(m)}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by simplependulum View Post
     = 80^{1507} + 80^{1506}(1507) + .... + \frac{1507(1506)}{2} 80^2 + 1507(80) + 1

     \equiv 60+1 \bmod{100} \equiv 61 \bmod{100}
    What's going on here?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,710
    Thanks
    629
    Hello, HeadOnAPike!

    I used a very primitive approach . . .



    Find the last two digits of: . N \;=\;222227^{2010}

    I know that this gets reduced to: . 27^{2010}\text{ (mod 100)}

    We have: . N \;=\;\left(3^3\right)^{2010} \;=\;3^{6030}


    I found that:

    . . \begin{array}{cc}3^n & \text{ends in} \\ \hline<br />
3^1 & 03 \\ 3^2 & 09 \\ 3^3 & 27 \\ 3^4 & 81 \\ 3^5 & 43 \\ \vdots & \vdots \\<br />
3^{10} & 49 \\ \vdots & \vdots \\ 3^{20} & 01 \end{array}


    Hence: . 3^{20} \:\equiv\:01\text{ (mod 100)}


    We have: . N \;=\;3^{6030} \;=\;3^{20(301) + 10} \;=\;\left(3^{20}\right)^{301}\cdot 3^{10}


    Hence: . N \;\equiv\;(01)^{301}\cdot 3^{10}\text{ (mod 100)}

    . . . . . . . . \equiv\;3^{10}\text{ (mod 100)}

    . . . . . . . . \equiv\;49\text{ (mod 100)}


    Therefore, 222227^{2010} ends in 49.

    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