Results 1 to 5 of 5

Math Help - Modular Arithmetic with Exponent

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    Modular Arithmetic with Exponent

    Determine n between 0 and 8 such that 1111^2222 equivalent to n mod 9.

    I need to show the steps.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kturf View Post
    Determine n between 0 and 8 such that 1111^2222 equivalent to n mod 9.

    I need to show the steps.

    Thanks!
    Merely note that,

    2222=2220+2=370\cdot6+2=370\phi\left(9\right)+2

    so that

    1111^{2222}\equiv 1111^2\text{ mod }9.

    But,

    1111=11\cdot101\equiv 2\cdot101\text{ mod }9
    .

    So,

    1111^{2222}\equiv 202^2\text{ mod }9.

    But,

    202^2=\left(198+4\right)^2=198^2+2\cdot4\cdot198+4  ^2. But, 198\equiv 0\text{ mod }9
    .

    So, we may finally conclude that

    1111^{2222}\equiv 198^2+2\cdot4\cdot198+4^2\equiv 4^2\equiv 7\text{ mod }9
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello kturf
    Quote Originally Posted by kturf View Post
    Determine n between 0 and 8 such that 1111^2222 equivalent to n mod 9.

    I need to show the steps.

    Thanks!
    Here's an alternative approach.

    1111 = 123\times9+4

    \Rightarrow 1111 \equiv 4 \mod 9

    \Rightarrow 1111^2 \equiv 4^2 \mod 9
    \equiv 7 \mod 9
    \Rightarrow 1111^3 \equiv 4\times7 \mod 9
    \equiv 1 \mod 9
    And 2222 = 740\times 3 +2

    \Rightarrow 1111^{2222} \equiv \Big(1111^{3}\Big)^{740} \times 1111^2 \mod 9
    \equiv 1 \times 7 \mod 9

    \equiv 7\mod 9
    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Grandad View Post
    Hello kturfHere's an alternative approach.

    1111 = 123\times9+4

    \Rightarrow 1111 \equiv 4 \mod 9

    \Rightarrow 1111^2 \equiv 4^2 \mod 9
    \equiv 7 \mod 9
    \Rightarrow 1111^3 \equiv 4\times7 \mod 9
    \equiv 1 \mod 9
    And 2222 = 740\times 3 +2

    \Rightarrow 1111^{2222} \equiv \Big(1111^{3}\Big)^{740} \times 1111^2 \mod 9
    \equiv 1 \times 7 \mod 9

    \equiv 7\mod 9
    Grandad
    One of us started with the base and the other with the exponent! Haha! You solution is probably better though since you didn't need to invoke Euler.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,546
    Thanks
    539
    Hello, kturf!

    Determine n between 0 and 8 such that: . 1111^{2222} \:\equiv\:n\text{ (mod 9)}

    Since 1111 \,\equiv\,4\text{ (mod 9)}, we have: . 4^{2222}\:\equiv\:n\text{ (mod 9)}

    We want the remainder when 4^{2222} is divided by 9.


    We find that:

    . . \begin{array}{ccc}4^1 & \equiv & 4\text{ (mod 9)} \\<br />
4^2 &\equiv& 7\text{ (mod 9)} \\<br />
4^3 &\equiv& 1\text{ (mod 9)} \\<br />
4^4 &\equiv& 4\text{ (mod 9)} \\<br />
\vdots && \vdots \end{array}

    The remainders move through a 3-step cycle.


    Since 2222\,\equiv\,2\text{ (mod 3)}, we have: . 4^2 \,\equiv\,7\text{ (mod 9)}


    Therefore: . 1111^{2222} \:\equiv\:7\text{ (mod 9)}

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 11th 2011, 11:27 AM
  2. Modular arithmetic.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 10th 2011, 05:21 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 15th 2011, 08:51 PM
  4. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 05:08 AM
  5. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 15th 2006, 07:07 PM

Search Tags


/mathhelpforum @mathhelpforum