Question

同余定理解2001的2003次方除以13的余数，第3步没懂

例题：求2001^2003除以13的余数
1、根据同余性质❹，我们可以得出2001^2003≡12^2003（mod 13）
2、12^2003还是一个较大的数，很难求出它除以13的余数，这时，我们就要找出12的几次方与1对于模13是同余的。根据试验，可得出12^2≡1（mod 13）
3、我们把12^2003拆成 (12^2）×1001×12^1，而 (12^2）×1001×12^1≡1×12≡12（mod 13）
4、这时，我们可以得出2001^2003除以13的余数为12，我们用计算器计算一下，这个答案是对的。
它第三步我知道好像是写错了，应该是
12^2003=（12^2）^1001×12^1≡1×12≡12（mod13)=12
我的理解是根据第二步得到
12^2003=(12^2)^1001×12^1≡1^1001(mod13)×12^1=1(mod13)×12^1≡1×12≡12(mod13)
但是不理解的同余式的两边还能同时乘以一个数吗，同余不是一个等式啊，两边同乘以一个数后变成什么意思了，比如5≡7（mod2) 那5×2≡7（mod2) ×2吗。

Answer 1

2001^2003
=(13*153+12)^2003

2001^2003 mod 13
=12^2003 mod 13
=12*(144^1001) mod 13
=12*[(13*11+1)^1001] mod 13
=12x1^1001 mod 13
=12 mod 13
=12

7 mod 2 = 1 不等于5