PRACTICE WITH POWERS (pre 2nd midterm) -- SOLUTIONS 1. Evaluate 3^2343 (mod 19). Answer: 8. Reduction by Fermat's Theorem ----------------------------- Since 19 is prime, Fermat's Theorem says that 3^18 == 1 (mod 19). Thus we take 2343 = 18x130 + 3. 3^2343 == (3^18)^130 x 3^3 == 1 x 27 == 27 == 8 (mod 19). - 2. Evaluate 2^375961 (mod 59). Answer: 32. Reduction by Fermat's Theorem ----------------------------- Since 59 is prime, Fermat's Theorem says that 2^58 == 1 (mod 59). Thus we take 375961 = 58x6482 + 5. 2^375961 == (2^58)^6482 x 2^5 == 1 x 32 == 32 (mod 59). -- 3. Evaluate 7^352426 (mod 61). Answer: 45. Reduction by Fermat's Theorem ----------------------------- Since 61 is prime, Fermat's Theorem says that 7^60 == 1 (mod 61). Thus we take 352426 = 60x5873 + 46. 7^352426 == (7^60)^5873 x 7^46 == 1 x 7^46 == 7^46 (mod 61). That's as far as Fermat's Theorem will take us, so now we quickly check for short patterns or early 1's (or -1's) in the first few powers of 7: Quick Check for Short Patterns -------------------------------- 7^1 == 7, 7^2 == 49, 7^3 == 38, 7^4 == 22 (mod 61). Nope! No obvious short patterns. Next strategy! Successive Squaring for 7^46 (mod 61) ------------------------------------- 1) Express 46 as a sum of powers of 2: 46 = 32 + 8 + 4 + 2. 2) Calculate 7^(powers of 2) by successive squaring: 7^1 == 7 == 7 (mod 61) 7^2 == 7^2 == 49 == 49 (mod 61) 7^4 == 49^2 == 2401 == 22 (mod 61) 7^8 == 22^2 == 484 == 57 (mod 61) 7^16 == 57^2 == (-4)^2 == 16 (mod 61) 7^32 == 16^2 == 256 == 12 (mod 61) 3) Combine some of these by multiplication to get 7^46: 7^46 == 7^(32 + 8 + 4 + 2) == 7^32 x 7^8 x 7^4 x 7^2 == 12 x 57 x 22 x 49 == 737352 == 45 (mod 61). -- Finished! 4. Evaluate 5^33 (mod 28). Answer: 13. 28 is NOT PRIME, so NO FERMAT! ------------------------------ Quick Check for Short Patterns ------------------------------ 5^1 == 5, 5^2 == 25, 5^3 == 13, 5^4 == 9 (mod 28). Nope! No obvious short patterns. Next strategy! Successive Squaring for 5^33 (mod 28) ------------------------------------- 1) Express 33 as a sum of powers of 2: 33 = 32 + 1. 2) Calculate 5^(powers of 2) by successive squaring: 5^1 == 5 == 5 (mod 28) 5^2 == 5^2 == 25 == 25 (mod 28) 5^4 == 25^2 == 625 == 9 (mod 28) 5^8 == 9^2 == 81 == 25 (mod 28) 5^16 == 25^2 == 625 == 9 (mod 28) 5^32 == 9^2 == 81 == 25 (mod 28) 3) Combine some of these by multiplication to get 5^33: 5^46 == 5^(32 + 1) == 5^32 x 5^1 == 25 x 5 == 125 == 13 (mod 28). -- Finished! 5. Evaluate 9^149 (mod 21). Answer: 18. 21 is NOT PRIME, so NO FERMAT! ------------------------------ Quick Check for Short Patterns ------------------------------ 9^1 == 9, 9^2 == 18, 9^3 == 15, 9^4 == 9 (mod 21). Yippee! A pattern! We have a cycle of length 3 that goes 9, 18, 15, 9, 18, 15, 9, 18, 15. 149 = 49x3 + 2, so we complete 49 full cycles, and then stop at the 2nd number in the cycle. Thus 9^149 == 9^2 == 18 (mod 21). --