Thread: 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.

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.

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?

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.