連立合同方程式 x≡1(mod7) x≡2(mod11) x≡3(mod13) の答えを教えてくださ

連立合同方程式

x≡1(mod7)
x≡2(mod11)
x≡3(mod13)

の答えを教えてください。
x≡○(mod ○)

No.2 回答者： ありものがたり 回答日時： 2020/08/01 20:41

mod なしで書いてみると、

x = 1 + 7a = 2 + 11b = 3 + 13c. (a,b,cは整数)。

1 + 7a = 2 + 11b の部分を取り出してみると、 7a - 11b = 1.
パット見で、a = -3, b = -2 が解であることが見つかるだろう。
上の式と 7(-3) - 11(-2) = 1 を引き算して、7(a+3) = 11(b+2).
この式の両辺は、7 の倍数でもあり、11 の倍数でもあるから
7(a+3) = 11(b+2) = 7・11k (kは整数) と置ける。
よって、 a = -3 + 11k,　b = -2 + 7k,
x = 1 + 7a = -20 +77k.

改めて、問題は x = -20 + 77k = 3 + 13c.
77k - 13c = 23 と整理できる。
さっきはパット見で a = -3, b = -2 を思いついたが、
この式を満たす k,c を組織的に探すには
77 と 13 の最大公約数を互除法で見つける。
77 = 13・5 + 12,
13 = 12・1 + 1.
より
1 = 13 - 12・1 = 13 - (77 - 13・5)・1 = 13・6 - 77・1.
これに 23 を掛けた 77×23 - 13・(6・23) = -1・23 を
原式に足せば、 77(k+23) = 13(c+138).
この式の両辺は 77 と 13 の公倍数だから、
77(k+23) = 13(c+138) = 77・13n (nは整数) と書ける。
よって、c = -138 + 77n,　k = -23 + 13n,
x = 3 + 13c = -1791 + 1001n = 211 + 1001(n-2).

結局、
x ≡ 211 (mod 1001) である。

No.1 回答者： syotao 回答日時： 2020/08/01 15:37

x≡211(mod 1001)