求一次同余式组x≡7（mod15）,x≡4（mod6）的解法.初等数论

Question

求一次同余式组x≡7（mod15）,x≡4（mod6）的解法.
初等数论

Answer 1

∵（15,6）=3 （（15,6）表示15与6的最大公约数）
而7≡4 （mod3）
∴同余式组有解
∵x≡7（mod15）==>x=15y+7 (y是整数)
代入x≡4（mod6）
得15y+7≡4（mod6）==>15y≡-3 (mod6)
==>5y≡-1 (mod2)
==>y≡1(mod2)
取其中一个解y=1
∴原同余式组的一个解是x=15*1+7=22
∵[15,6]=30 ([15,6]表示15与6的最小公倍数)
∴原同余式组的所有解是x≡22 （mod30）