Results 1 to 8 of 8

Thread: 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?
    $\displaystyle \phi(100)=40 $ and $\displaystyle (27,100)=1\implies 27^{40}\equiv1\bmod{100} $

    Now $\displaystyle 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 $\displaystyle 10=8+2=2^3+2 $

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

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

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

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    20
    Quote Originally Posted by chiph588@ View Post
    $\displaystyle \phi(100)=40 $ and $\displaystyle (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
    19,728
    Thanks
    3009
    $\displaystyle \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, $\displaystyle 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
    $\displaystyle 27^{2010} = 3^{6030} = 3^{6028+2} = 9 (81^{1507}) $


    $\displaystyle 81^{1507} = (80 + 1)^{1507} $

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

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

    Therefore ,

    $\displaystyle 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 $\displaystyle f: x \to ax ~ a,x \in \mathbb{U}(m)$ is a bijection . Then , obtaining the product :

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

    $\displaystyle 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
    $\displaystyle = 80^{1507} + 80^{1506}(1507) + .... + \frac{1507(1506)}{2} 80^2 + 1507(80) + 1 $

    $\displaystyle \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
    12,028
    Thanks
    848
    Hello, HeadOnAPike!

    I used a very primitive approach . . .



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

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

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


    I found that:

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


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


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


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

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

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


    Therefore, $\displaystyle 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: Apr 19th 2011, 11:51 AM
  2. Replies: 7
    Last Post: Nov 28th 2010, 09:22 PM
  3. Digits
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Mar 23rd 2010, 05:11 AM
  4. Sum of the digits
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Apr 7th 2008, 03:50 AM
  5. Replies: 2
    Last Post: Apr 3rd 2007, 12:31 PM

Search Tags


/mathhelpforum @mathhelpforum