如何用同余定理解题

例题：求2001^2003除以13的余数

根据同余性质❹，我们可以得出2001^2003≡12^2003（mod 13）

12^2003还是一个较大的数，很难求出它除以13的余数，这时，我们就要找出12的几次方与1对于模13是同余的。根据试验，可得出12^2≡1（mod 13）

我们把12^2003拆成 (12^2）×1001×12^1，而 (12^2）×1001×12^1≡1×12≡12（mod 13）

这时，我们可以得出 2001^2003除以13的余数为12，我们用计算器计算一下，这个答案是对的。