Results 1 to 4 of 4

Math Help - Congruences

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    53

    Congruences

    Here is the question I am having trouble with:

    Find the remainder when 5^183 is divided by 99.

    Any help is appreciated.
    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 Shapeshift View Post
    Here is the question I am having trouble with:

    Find the remainder when 5^183 is divided by 99.

    Any help is appreciated.
    Hint (5,99)=1,183\text{ mod }\phi(99)=3
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    53
    Hi, I understand that the gcd of those numbers is 1. However, I don't quite understand your hint about the euler phi function, because my teacher hardly taught this. If you could help me understand it that would be great
    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 Shapeshift View Post
    Hi, I understand that the gcd of those numbers is 1. However, I don't quite understand your hint about the euler phi function, because my teacher hardly taught this. If you could help me understand it that would be great
    Euler's theorem states that if (a,n)=1 then a^{\phi(n)}\equiv 1\text{ mod }n. So, since (5,99)=1 we see that 5^{183}=5^{3+3\cdot 60}=5^3\cdot \left(5^{\phi(99)}\right)^3\equiv 5^3\text{ mod }99
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruences
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 11th 2010, 12:52 PM
  2. Congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 7th 2009, 02:26 PM
  3. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 18th 2009, 05:12 AM
  4. More congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 17th 2009, 10:40 PM
  5. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum