Results 1 to 8 of 8

Math Help - Euler's Theorm - Homework

  1. #1
    Junior Member
    Joined
    May 2006
    Posts
    30

    Question Euler's Theorm - Homework

    Need some help with this problem

    Question:

    Find the remainder when we divide 11^2004 by 45


    Not sure what to do on this problem...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by mathlg View Post
    Need some help with this problem

    Question:

    Find the remainder when we divide 11^2004 by 45


    Not sure what to do on this problem...
    Note,
    45=3^2\cdot 5
    Thus,
    \phi(45)=45\left(1-\frac{1}{3}\right) \left(1-\frac{1}{5}\right)=24
    Thus,
    11^{24}\equiv 1
    Raise both sides to 83th,
    11^{1992}\equiv 1
    Now,
    11^{12}\equiv 1
    Thus, (multiply them through)
    11^{2004}\equiv 1
    Last edited by ThePerfectHacker; December 13th 2006 at 09:00 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,184
    Thanks
    403
    Awards
    1
    Quote Originally Posted by mathlg View Post
    Need some help with this problem

    Question:

    Find the remainder when we divide 11^2004 by 45


    Not sure what to do on this problem...
    Euler's theorem says that a^{\phi (n) } \equiv 1 (mod n). So we need to know \phi (45). Now, I couldn't find this number on the net, but using my calculator I easily found that 11^6 \equiv 1 (mod 45).

    So
    11^{2004} = 11^{6 \cdot 334} = (11^6)^{334} \equiv 1^{334} (mod 45) = 1 (mod 45)

    Thus the remainder is 1.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by topsquark View Post
    Now, I couldn't find this number on the net, but using my calculator I easily found that 11^6 \equiv 1 (mod 45).
    What you found was actually the "order of 11". Euler's theorem says that \phi(n) is always AN exponent that makes the statement true. But not necessarily the smallest (the order of the integer). Whenever the order is \phi(n) that is called a "primitive roots" (in an algebraic way of sense we can think of this a generator of the cyclic group). The number 45 has not primitive roots, as a problem solved by Gauss. It is not one of the standard forms for which primitive roots exists. (primes, power of primes, and doubling power of primes).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,857
    Thanks
    739
    Hello, mathlg!

    Here's a primitive approach . . .


    Find the remainder when we divide 11^{2004} by 45

    Raising 11 to consecutive powers, we find that:
    . . 11^6 \div 45 has a remainder of 1.

    So we have: . 11^{2004} \:=\:(11^6)^{334} \:\equiv\:1^{334}\!\!\!\!\!\pmod{45}\;\equiv\; 1\!\!\!\!\!\pmod{45}


    Therefore: . 11^{2004} \div 45 has remainder 1.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,184
    Thanks
    403
    Awards
    1
    Quote Originally Posted by Soroban View Post
    Hello, mathlg!

    Here's a primitive approach . . .



    Raising 11 to consecutive powers, we find that:
    . . 11^6 \div 45 has a remainder of 1.

    So we have: . 11^6)^{334} \:\equiv\:1^{334}\!\!\!\!\!\pmod{45}\;\equiv\; 1\!\!\!\!\!\pmod{45}" alt="11^{2004} \:=\11^6)^{334} \:\equiv\:1^{334}\!\!\!\!\!\pmod{45}\;\equiv\; 1\!\!\!\!\!\pmod{45}" />


    Therefore: . 11^{2004} \div 45 has remainder 1.

    (Chuckles) Looks familiar somehow...

    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Did you get Soroban's joke, "a primitive approach".
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,184
    Thanks
    403
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    Did you get Soroban's joke, "a primitive approach".
    *groans*

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 09:18 PM
  2. Rolles Theorm
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 25th 2010, 06:06 PM
  3. Replies: 0
    Last Post: February 20th 2010, 09:26 AM
  4. Residue Theorm - Q1
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: October 3rd 2009, 09:35 AM
  5. Replies: 0
    Last Post: September 17th 2009, 07:44 PM

Search Tags


/mathhelpforum @mathhelpforum