Results 1 to 3 of 3

Math Help - Remainders

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    32

    Remainders

    Question: What are the last three digits of x=673^(2802) when it is written base 10? (Hint: This is the same as asking for the remainder when x is divded by 1000)

    I figured it out, just wanted to make sure this was right...

    1000=2^3 x 5^3
    ϕ(1000)=2^2(2-1) x 5^2(5-1)
    =4 x 1 x 25 x 4 = 400
    ϕ(1000)=400

    Using Euler's Theorem
    gcd(673, 1000) = 1 so 673^400≡1(mod 1000)

    2802=400 x 7 + 2 so, the original x can be written x=(673^400)^7 x 673^2.

    Since we know that 673^400≡1 we can write x=1^7 x 673^2.

    We have 1^7 x 673^2 ≡ 673^2 (mod 1000) ≡ 452929 ≡ 929(mod 1000)

    The remainder when x=673^2902 is divided by 1000 is 929, so the last three digits of x when it is written in base 10 is 929.
    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 kiddopop View Post
    Question: What are the last three digits of x=673^(2802) when it is written base 10? (Hint: This is the same as asking for the remainder when x is divded by 1000)

    I figured it out, just wanted to make sure this was right...

    1000=2^3 x 5^3
    ϕ(1000)=2^2(2-1) x 5^2(5-1)
    =4 x 1 x 25 x 4 = 400
    ϕ(1000)=400

    Using Euler's Theorem
    gcd(673, 1000) = 1 so 673^400≡1(mod 1000)

    2802=400 x 7 + 2 so, the original x can be written x=(673^400)^7 x 673^2.

    Since we know that 673^400≡1 we can write x=1^7 x 673^2.

    We have 1^7 x 673^2 ≡ 673^2 (mod 1000) ≡ 452929 ≡ 929(mod 1000)

    The remainder when x=673^2902 is divided by 1000 is 929, so the last three digits of x when it is written in base 10 is 929.
    You're methodology looks correct but wolfram gives a different result.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    32
    I wrote my last line wrong...I meant to say:

    The remainder when x=673^2802 is divided by 1000 is 929, so the last three digits of x when it is written in base 10 is 929.

    What does wolfram say is the answer?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Remainders
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 18th 2010, 05:04 AM
  2. Remainders mod x
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 15th 2010, 09:57 PM
  3. Remainders
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 18th 2010, 02:27 PM
  4. Remainders again
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 27th 2010, 09:35 AM
  5. Remainders
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 31st 2006, 08:34 AM

Search Tags


/mathhelpforum @mathhelpforum