Results 1 to 2 of 2

Math Help - Find remainder with congruence theorem

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    Find remainder with congruence theorem

    This is a problem we ran over in class, but I don't fully understand it.

    Find remainder when 3^{1000000} is divided by 26.

    Solution:

     1000000 = (3)(333333)+1, therefore 3^{1000000} = 3^{(333333)(3)+1} = 3^{333333}(3)

    By using the congruence theorem, we know that if a congruence b, mod n, then a and b would have the same remainder upon being divided by n.

    Then it goes that the remainder is 3, but how do you get that?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tttcomrader View Post
    This is a problem we ran over in class, but I don't fully understand it.

    Find remainder when 3^{1000000} is divided by 26.

    Solution:

     1000000 = (3)(333333)+1, therefore 3^{1000000} = 3^{(333333)(3)+1} = 3^{333333}(3)

    By using the congruence theorem, we know that if a congruence b, mod n, then a and b would have the same remainder upon being divided by n.

    Then it goes that the remainder is 3, but how do you get that?
    Note that 3^3 = 27 this means that 3^3 \equiv 27 \equiv 1(\bmod 26).
    Thus, (3^3)^{333333} \equiv 1^{333333} (\bmod 26).
    Thus, 3^{999999}\equiv 1(\bmod 26)
    Multiply both sides by 3 to get your answer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding remainder in non-prime congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 4th 2009, 06:38 PM
  2. Congruence, finding remainder
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 7th 2009, 03:42 PM
  3. Find x in the congruence using Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 24th 2009, 10:15 AM
  4. Replies: 3
    Last Post: March 18th 2009, 05:19 PM
  5. Factor Theorem and Remainder Theorem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 8th 2007, 11:50 AM

Search Tags


/mathhelpforum @mathhelpforum