Results 1 to 4 of 4

Math Help - how do i find 5^2003 (mod1001) by using Chinese Remainder theorem?

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    16

    how do i find 5^2003 (mod1001) by using Chinese Remainder theorem?

    Yeah i know these:

    5^2003=3 mod7
    5^2003=4 mod11
    5^2003=8 mod13

    and 1001=7x11x13

    but i couldnt find that 5^2003=y(mod1001)

    can anyone express clearly how to conclude this problem by using chinese remainder theorem?

    thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2009
    Posts
    12
    Quote Originally Posted by eyke View Post
    Yeah i know these:

    5^2003=3 mod7
    5^2003=4 mod11
    5^2003=8 mod13

    and 1001=7x11x13

    but i couldnt find that 5^2003=y(mod1001)

    can anyone express clearly how to conclude this problem by using chinese remainder theorem?

    thanks in advance.
    I get answer 125 by Euler's Theorem.
    5^2003 = 5^(1000*2+3) = [5^(1000*2)][5^3]
    5 and 1001 are relative primes
    by Euler's Theorem, we know 5^1000 = 1 (mod 1001)
    [5^(1000*2)][5^3] (mod 1001) = 1 * 5^3 (mod 1001) =125

    hope this is helpful
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by eyke View Post
    Yeah i know these:

    5^2003=3 mod7
    5^2003=4 mod11
    5^2003=8 mod13
    You have: x\equiv 3(\bmod 7),x\equiv 4(\bmod 11),x\equiv 8(\bmod 13). The congruences can be written as x\equiv 3 - 7\cdot 3(\bmod 7), x\equiv 4 - 2\cdot 11 (\bmod 11). This gives x\equiv -18(\bmod 7) and x\equiv -18(\bmod 11), this combines into x\equiv -18(\bmod 77). We can write, x\equiv - 18 - (77)(26) (\bmod 77) and x\equiv 8 - (13)(156)(\bmod 13). Therefore, x\equiv -2020 \equiv 983(\bmod 1001)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    Posts
    16
    Quote Originally Posted by ThePerfectHacker View Post
    You have: x\equiv 3(\bmod 7),x\equiv 4(\bmod 11),x\equiv 8(\bmod 13). The congruences can be written as x\equiv 3 - 7\cdot 3(\bmod 7), x\equiv 4 - 2\cdot 11 (\bmod 11). This gives x\equiv -18(\bmod 7) and x\equiv -18(\bmod 11), this combines into x\equiv -18(\bmod 77). We can write, x\equiv - 18 - (77)(26) (\bmod 77) and x\equiv 8 - (13)(156)(\bmod 13). Therefore, x\equiv -2020 \equiv 983(\bmod 1001)
    that's the answer i needed.
    thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 10:20 PM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2010, 08:56 PM
  3. Chinese remainder theorem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 20th 2009, 01:57 PM
  4. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 31st 2009, 08:34 AM
  5. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 15th 2008, 07:12 PM

Search Tags


/mathhelpforum @mathhelpforum