Results 1 to 2 of 2

Math Help - Remainders mod x

  1. #1
    Senior Member I-Think's Avatar
    Joined
    Apr 2009
    Posts
    288

    Remainders mod x

    Question
    Compute the remainder modulo 7 of 2222^5555

    My notes do not make this explicit so I ask here. Is this question asking for a number x such that x\equiv{2222^{5555}} (mod{ }n)

    If so, then this question is equivalent to solving the diophantine equation
    x-7k=2222^{55555}
    ?
    And I need to find the least positive integer x that satisfies this equation?
    How shall I proceed to do this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by I-Think View Post
    Question
    Compute the remainder modulo 7 of 2222^5555

    My notes do not make this explicit so I ask here. Is this question asking for a number x such that x\equiv{2222^{5555}} (mod{ }n)

    If so, then this question is equivalent to solving the diophantine equation
    x-7k=2222^{55555}
    ?
    And I need to find the least positive integer x that satisfies this equation?
    How shall I proceed to do this?

    Reduce the base modulo 7: 2222=3\!\!\pmod 7 , so 2222^{5555}=3^{5555}\!\!\pmod 7

    Now divide the power by 7 with remainder: 5555=7\cdot 793+4 , so 3^{5555}=\left(3^{793}\right)^7\cdot 3^4.

    Use now Fermat's Little Theorem: \forall n\in\mathbb{Z}\,,\,z^p=z\!\!\pmod p\,,\,\,p a prime , so that

    \left(3^{793}\right)^7=3^{793}\!\!\pmod 7 . Repeat the above with 793 instead of 5555...(of course, keep track of 3^4 and all the small powers you'll get!)

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Remainders
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 9th 2010, 06:27 PM
  2. Remainders
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 18th 2010, 05:04 AM
  3. Remainders
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 18th 2010, 02:27 PM
  4. Remainders again
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 27th 2010, 09:35 AM
  5. Remainders
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 31st 2006, 08:34 AM

Search Tags


/mathhelpforum @mathhelpforum