Results 1 to 4 of 4

Math Help - Phi(n)

  1. #1
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169

    Phi(n)

    I am having trouble with the following problem: Find the last three digits of 7^732. I know that I need to find the least residue of 7^732(mod 1000), so I calculate Phi(1000)=Phi(2^3)*Phi(5^3)=4*100=400, which means that 7^400==1(mod 1000)==1+7^332(mod 1000). And that's where I get stuck. I cannot seem to find a way to reduce this problem. Help! Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    993
    Thanks
    244
    You've got the right approach. One slight problem with your equations: 7^732 == 7^400 * 7^332 == 1 * 7^332 == 7^332 (mod 1000) (you had addition instead of multiplication).

    It's easy enough to calculate from here. Since 332 = 256+64+8+4, just calculate those powers by repeated squaring:
    7^2 = 49
    7^4 = 49^2 = 2401 == 401
    7^8 == 401^2 = 160801 == 801
    7^16 == 801^2 = 641601 == 601
    etc.

    It's easy enough to drive to the finish from here, which would be a reasonable approach.

    You might notice the "01" pattern and figure out that 7^20 = 7^16 * 7^4 == 601 * 401 = 1 (mod 1000). Then you would calculate 7^332 = 7^320 * 7^12 = (7^20)^16 * 7^12 == 1^16 * 7^12 = 7^12 == 201 (mod 1000).

    Since you know 7^400 == 1, you might try dividing out the prime factors of 400 and calculate 7^200 == 1, then 7^100 == 1, then 7^50 is not 1, so going back to 100 and try dividing out 5, so 7^20 == 1, and then 7^4 is not 1. That's a lot more work than the original problem, though.

    Post again if you still have trouble.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    Thank you for the correction; I should have used multiplication! I still don't quite see where you are going with the 7^332, however. I do see that 332=256+64+8+4 but I don't know how to use that information. And how did you know to look for those numbers?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2010
    Posts
    993
    Thanks
    244
    Those are the powers of two (256=2^8, 64=2^6, 8=2^3, and 4=2^2), which you get when you do the repeated squaring:

    7^2 == 49 (mod 1000)
    7^4 == 49^2 = 401 (mod 1000)
    7^8 == 401^2 == 801 (mod 1000)
    7^16 == 801^2 == 601 (mod 1000)
    7^32 == 601^2 == 201 (mod 1000)
    7^64 == 201^2 == 401 (mod 1000)
    7^128 == 401^2 == 801 (mod 1000)
    and 7^256 == 801^2 == 601 (mod 1000)

    So now that you've done all those calculations, you can calculate

    7^332 = 7^256 * 7^64 * 7^8 * 7^4

    There are other methods, but the secret is to do the intermediate calculations (mod 1000) so you don't have to deal with really big numbers like 7^332.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum