Results 1 to 2 of 2

Thread: 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 $\displaystyle 2222^5555$

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

    If so, then this question is equivalent to solving the diophantine equation
    $\displaystyle 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
    Thanks
    3
    Quote Originally Posted by I-Think View Post
    Question
    Compute the remainder modulo 7 of $\displaystyle 2222^5555$

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

    If so, then this question is equivalent to solving the diophantine equation
    $\displaystyle 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: $\displaystyle 2222=3\!\!\pmod 7$ , so $\displaystyle 2222^{5555}=3^{5555}\!\!\pmod 7$

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

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

    $\displaystyle \left(3^{793}\right)^7=3^{793}\!\!\pmod 7$ . Repeat the above with 793 instead of 5555...(of course, keep track of $\displaystyle 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: Nov 9th 2010, 06:27 PM
  2. Remainders
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Oct 18th 2010, 05:04 AM
  3. Remainders
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Apr 18th 2010, 02:27 PM
  4. Remainders again
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Mar 27th 2010, 09:35 AM
  5. Remainders
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Mar 31st 2006, 08:34 AM

Search Tags


/mathhelpforum @mathhelpforum