合同式について 以下の問題のように最大公約数が1で法が大きい場合、どのようにして答えを導出すれば良い

合同式について
以下の問題のように最大公約数が1で法が大きい場合、どのようにして答えを導出すれば良いのでしょうか？
14x≡5(mod45)

質問者からの補足コメント

• 14×10=140≡5(mod45)より
  10と答えは分かりますが、それ以外の方法でお願いします。

    補足日時：2022/06/17 16:16

No.4 ベストアンサー 回答者： ありものがたり 回答日時： 2022/06/17 19:03

あ、しもた。

14x≡5 か。

14x = 5 + 45y を解くには、　←[1]
まず 14x - 45y = 1 を解く。
14 と 45 で互除法を行うと
45 = 14・3 + 3,
14 = 3・4 + 2,
3 = 2・１ + 1
で、これを使って
1 = 3 - 2・1
　= 3 - (14 - 3・4)・1 = 3・5 - 14
　= (45 - 14・3)・5 - 14 = 45・5 - 14・16　←[2]
が見つかる。
[2] の両辺を 5 倍すると、14・(-80) + 45・25 = 5.　←[3]
[1][3] を辺々引き算すると
14(x + 80) = 45(y + 25) となる。
この式の両辺は 14 でも 45 でも割り切れるから、
14(x + 55) = 45(y + 25) = (14・45)k　{kは整数}
と置くことができて、変形すれば
x = -80 + 45k,　y = -25 + 14k.
x ≡ -80 (mod 45) という答えが出たが、これは
x ≡ 10 (mod 45) と書いても同じこと。

この回答へのお礼

ユークリッドのやり方理解できました。これなら出来そうです！

お礼日時：2022/06/17 19:07

No.3 回答者： ありものがたり 回答日時： 2022/06/17 18:49

4x≡5(mod45) を解くには、普通

4x=5+45y を解く。それには、　←[1]
まず 4x-45y=1 を解くことから始める。
4 と 45 で互除法を行うと、
45 = 4・11 + 1 で
すぐ 4・(-11) + 45・1 = 1 が見つかる。
この式を 5 倍すると、4・(-55) + 45・5 = 5.　←[2]
[1][2] を辺々引き算すると
4(x + 55) = 45(y - 5) となる。
この式の両辺は 4 でも 45 でも割り切れるから、
4(x + 55) = 45(y - 5) = (4・45)k　{kは整数}
と置くことができて、変形すれば
x = -55 + 45k, y = 5 + 4k.
x ≡ -55 (mod 45) という答えが出たが、これは
x ≡ 35 (mod 45) と書いても同じこと。

この回答へのお礼

なるほど。理解できました

お礼日時：2022/06/17 19:06

No.2 回答者： Tacosan 回答日時： 2022/06/17 18:23

「ユークリッドの互除法」ってのがある.

No.1 回答者： t_fumiaki 回答日時： 2022/06/17 17:59

14x=45n±1となる様なx,nを求めます。

14･16=224=45･5-1

14･16≡-1
両辺に-5を掛けて、
14･(-80)≡5

x=-80=-90+10≡10

この回答へのお礼

シンプルで分かりやすいですね

お礼日時：2022/06/17 19:06