求3999的123次方除以39所得的余数

题目

求3999的123次方除以39所得的余数

答案

3999 除以39余数为21
21 = 3*7
39 = 3*13
7^6 除以13余数为(-1)
3^3 除以13余数为1
则
①
(3*7) ^123 除以3余0
②
(3*7) ^123 除以13余
= 3^123 * 7^123 | 13
= (3^3)^41 * (7^6)^20 * 7^3 | 13
= 1^41 * (-1)^20 *7^3 | 13
= 7^3 | 13
= 5
被3除余0、被13除余5的数,【即如18】,被39除余18
综上,3999的123次方除以39余18