有关CRT的小学奥数题

利用中国剩余定理(CRT)和欧拉定理求解模指数运算问题

留意 ’ = ’ 和 ’ ≡ ’ 的转换时机


前置知识请看:中国剩余定理指北 | M0D1.TOP

(1) 手动计算 20002019(mod 221)2000^{2019} (mod\ 221)


解:

221 = 17*13

由中国剩余定理得

20002019mod 221([112019mod 17],[112019mod 13])2000^{2019} mod\ 221 \cong ([11^{2019} mod\ 17],[11^{2019}mod\ 13])

由欧拉定理:

11ϕ(17)=11161 mod 1711^{\phi (17)} = 11^{16} ≡ 1\ mod\ 17

112019=1116126+31135 (mod 17)∴ 11^{2019} = 11^{16*126+3} ≡ 11^{3} ≡ 5\ (mod\ 17)

11ϕ(13)=11121 mod 1311^{\phi (13)} = 11^{12}≡ 1\ mod\ 13

112019=1112168+31135 (mod 13)∴ 11^{2019} = 11^{12*168+3} ≡ 11^{3} ≡ 5\ (mod\ 13)


x5 (mod 17)x ≡ 5\ (mod\ 17)

x5 (mod 13)x ≡ 5\ (mod\ 13)

再次运用中国剩余定理得:

(由于式子很特殊这一步多此一举,但是为了鲁棒性我还是写了)

x5 mod 1713x ≡ 5\ mod\ 17*13

20002019(mod 221)=5\therefore 2000^{2019} (mod\ 221) = 5


以上计算全程笔算可轻松完成,且与sage算出来的结果一致:


(2) 7^{1919}的最后三位是多少?


解:

1000 = 125*8

由中国剩余定理得:

71919mod 1000([71919mod 125],[71919mod 8])7^{1919} mod\ 1000 \cong ([7^{1919} mod\ 125],[7^{1919} mod\ 8])

由欧拉定理

7ϕ(125)=75352=71001 mod 1257^{\phi(125)} = 7^{5^3 - 5^2} = 7^{100} ≡ 1\ mod\ 125

71919mod 125=719mod 125∴ 7^{1919} mod\ 125 = 7^{19} mod\ 125

注意到 73=34332 (mod 125)7^3 = 343 ≡ -32\ (mod\ 125)

719=7(3436)7((32)6)7(10243)724318 (mod 125)∴7^{19} = 7*(343^{6}) ≡ 7*((-32)^6) ≡ 7*(1024^3) ≡ 7*24^3 ≡ 18\ (mod\ 125)

71919(1)19191 (mod 8)7^{1919} ≡ (-1)^{1919} ≡ -1\ (mod\ 8)


x1 mod 8x ≡ -1\ mod\ 8

x18 mod 125x ≡ 18\ mod\ 125

再次运用中国剩余定理得:

x143 (mod 1258)x ≡ 143\ (mod\ 125*8)

71919mod 1000=143∴7^{1919} mod\ 1000 = 143


以上计算全程笔算可完成,且与sage算出来的结果一致:

文章作者: 莫折眉
文章链接: https://m0d1.top/2021/05/14/crt-1/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 M0D1.TOP