find the remainder of 7^38 when divided by 660
The Correct Answer and Explanation is:
To find the remainder of 738mod 6607^{38} \mod 660738mod660, we can use the Chinese Remainder Theorem. Since 660=22×3×5×11660 = 2^2 \times 3 \times 5 \times 11660=22×3×5×11, we first need to compute 738mod 47^{38} \mod 4738mod4, 738mod 37^{38} \mod 3738mod3, 738mod 57^{38} \mod 5738mod5, and 738mod 117^{38} \mod 11738mod11, then combine the results to find 738mod 6607^{38} \mod 660738mod660.
Step 1: Calculate 738mod 47^{38} \mod 4738mod4
Since 7≡−1mod 47 \equiv -1 \mod 47≡−1mod4, we have:738≡(−1)38≡1mod 4.7^{38} \equiv (-1)^{38} \equiv 1 \mod 4.738≡(−1)38≡1mod4.
Step 2: Calculate 738mod 37^{38} \mod 3738mod3
Since 7≡1mod 37 \equiv 1 \mod 37≡1mod3, we have:738≡138≡1mod 3.7^{38} \equiv 1^{38} \equiv 1 \mod 3.738≡138≡1mod3.
Step 3: Calculate 738mod 57^{38} \mod 5738mod5
We use Fermat’s Little Theorem: since 555 is prime, 74≡1mod 57^{4} \equiv 1 \mod 574≡1mod5. We can reduce the exponent 38mod 438 \mod 438mod4, which gives:38÷4=9 remainder 2.38 \div 4 = 9 \text{ remainder } 2.38÷4=9 remainder 2.
Thus, 738≡72mod 57^{38} \equiv 7^2 \mod 5738≡72mod5. Now, 72=497^2 = 4972=49, and 49mod 5=449 \mod 5 = 449mod5=4. Therefore:738≡4mod 5.7^{38} \equiv 4 \mod 5.738≡4mod5.
Step 4: Calculate 738mod 117^{38} \mod 11738mod11
Again using Fermat’s Little Theorem for p=11p = 11p=11, we know 710≡1mod 117^{10} \equiv 1 \mod 11710≡1mod11. We reduce 38mod 1038 \mod 1038mod10, which gives:38÷10=3 remainder 8.38 \div 10 = 3 \text{ remainder } 8.38÷10=3 remainder 8.
Thus, 738≡78mod 117^{38} \equiv 7^8 \mod 11738≡78mod11. Now, calculating powers of 777 modulo 111111:72=49≡5mod 11,74=52=25≡3mod 11,78=32=9mod 11.7^2 = 49 \equiv 5 \mod 11, \quad 7^4 = 5^2 = 25 \equiv 3 \mod 11, \quad 7^8 = 3^2 = 9 \mod 11.72=49≡5mod11,74=52=25≡3mod11,78=32=9mod11.
So, 738≡9mod 117^{38} \equiv 9 \mod 11738≡9mod11.
Step 5: Solve using the Chinese Remainder Theorem
We now have the system of congruences:x≡1mod 4,x≡1mod 3,x≡4mod 5,x≡9mod 11.\begin{aligned} x &\equiv 1 \mod 4, \\ x &\equiv 1 \mod 3, \\ x &\equiv 4 \mod 5, \\ x &\equiv 9 \mod 11. \end{aligned}xxxx≡1mod4,≡1mod3,≡4mod5,≡9mod11.
We can start by solving the system for xmod 660x \mod 660xmod660. First, solve x≡1mod 12x \equiv 1 \mod 12x≡1mod12 (since 444 and 333 are relatively prime). Now, the system is:x≡1mod 12,x≡4mod 5,x≡9mod 11.\begin{aligned} x &\equiv 1 \mod 12, \\ x &\equiv 4 \mod 5, \\ x &\equiv 9 \mod 11. \end{aligned}xxx≡1mod12,≡4mod5,≡9mod11.
Next, solve x≡1mod 12x \equiv 1 \mod 12x≡1mod12 and x≡4mod 5x \equiv 4 \mod 5x≡4mod5. Using the method of successive substitution, we find that x≡13mod 60x \equiv 13 \mod 60x≡13mod60. Finally, solve the system:x≡13mod 60,x≡9mod 11.x \equiv 13 \mod 60, \quad x \equiv 9 \mod 11.x≡13mod60,x≡9mod11.
Using the method of successive substitution again, we find:x≡73mod 660.x \equiv 73 \mod 660.x≡73mod660.
Final Answer:
The remainder when 7387^{38}738 is divided by 660 is 73.
