Results 1 to 5 of 5

Math Help - Congruence, finding remainder

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    9

    Congruence, finding remainder

    I'm fairily new to this discrete maths thing and I'm stuck on a problem that seems quite simple:





    The first problem I think can be solved by Fermat's little theorem. Since 41 is a prime, (2004^41)-2004 would probably be divisible by 41? But r1 should lie between 0 and 40, and I can't figure that part out. 2004 gives a remainder 36 when divided by 41, but then there was the power part.

    I'm pretty lost on the second one, but 61 is also a prime, but the power and the divider is not the same so that rules out Fermat?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by knarQ View Post
    I'm fairily new to this discrete maths thing and I'm stuck on a problem that seems quite simple:





    The first problem I think can be solved by Fermat's little theorem. Since 41 is a prime, (2004^41)-2004 would probably be divisible by 41? But r1 should lie between 0 and 40, and I can't figure that part out. 2004 gives a remainder 36 when divided by 41, but then there was the power part.

    I'm pretty lost on the second one, but 61 is also a prime, but the power and the divider is not the same so that rules out Fermat?
    Fermat little theorem says

    a^{p} \equiv a \mod(p)
    so in your case you get

    2004^{41}=2004\mod(41)


    From here jut divide 2004 by 41 to find the remainder.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539
    In the second, Fermat gives 2004^{60}\equiv 1\bmod 61. How can you use this to rewrite or break down that large exponent?
    Hint: Use the rule (a^{b})^{c}=a^{bc}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2009
    Posts
    9
    It feels good that I was on the right track.

     2004^{6000}=(2004^{100})^{60}

    By Fermat any number that is coprime with 61 and raised to 60 leaves remainder 1 when divided by 61, so my r2 probably is just... 1. Does this make sense?

     (2004^{100})^{60}\equiv 1\bmod 61
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by knarQ View Post
    Does this make sense?

     (2004^{100})^{60}\equiv 1\bmod 61
    Hi knarQ.

    Almost. Write it as \left(2004^{60}\right)^{100}\equiv1\pmod{61} instead.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding the remainder
    Posted in the Number Theory Forum
    Replies: 12
    Last Post: July 16th 2010, 04:34 AM
  2. finding remainder
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 7th 2009, 11:57 AM
  3. Finding remainder in non-prime congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 4th 2009, 06:38 PM
  4. finding the remainder by mod
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 2nd 2008, 08:31 AM
  5. Find remainder with congruence theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 6th 2008, 03:51 PM

Search Tags


/mathhelpforum @mathhelpforum