連立一次合同式について教えて下さい！

連立一次合同式について教えてください！

問題文）
x ≡ 1 mod 7 , x ≡ 2 mod 11 の解を求めると x ≡ (1) mod 77
になる。

という (1) に最終的な答えを入力する問題なのですが、
自分で解いてみると、x ≡ 1 mod 7 , x ≡ 2 mod 11の解が、
x=15 という間違った値が出てしまったので教えてほしいです…

No.2 ベストアンサー 回答者： ありものがたり 回答日時： 2021/05/29 19:17

x ≡ 1 (mod 7) は x = 1 + 7m となる整数 m があること、

x ≡ 2 (mod 11) は x = 2 + 11n となる整数 n があることだから、
今回の問題は x = 1 + 7m = 2 + 11n を解くことである。
x は一旦脇に置いて、1 + 7m = 2 + 11n を解く。
これは基本的な一次不定方程式であって、やり方はいつもどおり。

7m ‐ 11ｎ = 1 を解くには、 7 と 11 の最大公約数を
ユークリッドの互除法で求めて、
11 = 7・1 + 4,
7 = 4・1 + 3,
4 = 3・1 + 1
を
1 = 4 - 3・1
　= 4 - (7 - 4・1)・1 = 4・2 - 7
　= (11 - 7・1)・2 - 7 = 11・2 - 7・3
と変形する。
7m ‐ 11ｎ = 1 と
7・(-3) + 11・2 = 1 を辺々引き算すると、
7(m+3) = 11(n+2) と変形できる。
これの両辺は 7 と 11 の公倍数だから
7(m+3) = 11(n+2) = (7・11)k　； kは整数
と置くと、解は m = -3 + 11k, n = -2 + 7k であり、
x = 1 + 7m = 2 + 11n = -20 + 77k となる。
合同式で書けば、
x ≡ -20 ≡ 57 (mod 77) である。

x ≡ １ (mod 77) も
x = 15 も、どちらも間違いだが、
どこをどう間違ってそうなったのかは
計算過程を書いてくれないと指摘しようがない。

この回答へのお礼

お二方ご回答ありがとうございます。
これらの回答を参考に自分でも解いてみたいと思います！

お礼日時：2021/05/29 19:38

No.1 回答者： syotao 回答日時： 2021/05/29 16:00

７と１１は互いに素だから

7ｘ＋11ｙ＝1になるような整数回ｘ、ｙがある。
実際今の場合ｘ＝-3、ｙ＝2が解になっている。だから
x ≡ 1 mod 7の両辺を11×2倍して
（11×2)ｘ≡22mod77
x ≡ 2 mod 11の両辺を3×7倍して
(3×7)ｘ≡42mod77
この辺々ひけば
ｘ≡-20≡57mod77
つまり
ｘ≡57mod77　が答。