数论-孙子定理(中国剩余定理)及应用

x≡b1 (mod m1)

x≡b2 (mod m2)

……

x≡bk (mod mk)

例:

x≡2 (mod 3) ①

x≡3 (mod 5) ②

x≡2 (mod 7) ③

由①,x=3*k+2 ④,代入②中得:

3*k+2 ≡ 3 (mod 5)

3*k≡1 (mod 5)

k≡2 (mod 5)

∴k=5l+2,代入④中得,x=15l+8 ⑥

将⑥代入③中,得

15*l+6≡0 (mod 7)

5*l +2≡0 (mod 7)

l ≡ 1 (mod 7)

∴l = 7n+1代入⑥中,得x=105n+23

∴x最小为23

Th1:孙子定理(实在打不出来了>^

Original: https://www.cnblogs.com/jane315/p/13796621.html
Author: jane_315
Title: 数论-孙子定理(中国剩余定理)及应用

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/583750/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球