合同式について教えてください！

下記の合同式の、互いに合同でない解ｘを求める問題なのですが、
なかなか答えを導き出すことが出来ないです…

問）
31x ≡ 5 mod 42

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

31 と 42 は素数なので、 mod 42 の世界では

31 で割り算ができます。
x ≡ 5/31 (mod 42) なのですが...

ではこの /31 がどんな計算かというと、
1/31 ≡ r (mod 42) となる自然数 r を探すしかないですね。
法 42 がそんなに大きくないので、1,2,3,...,41 と順に試しても
たいしたことありませんが、
組織的に探す手段があったほうがいいかな。

31x ≡ 5 (mod 42) というのは、整数 n があって
31x = 5 + 42n が成り立つという意味です。
この式は、よく見かける一次不定方程式ですね。
これを解くには、まず定数項を 1 にした
31x₀ - 42n₀ = 1 を解いて、両辺を 5 倍します。

ｘ₀， ｎ₀ の方程式は、係数の最大公約数を求める
ユークリッドの互除法から、
42 = 31・1 + 11,
31 = 11・2 + 9,
11 = 9・1 + 2,
9 = 2・4 + 1.
を変形して
1 = 9 - 2・4
　= 9 - (11 - 9・1)・4 = 9・5 - 11・4
　= (31 - 11・2)・5 - 11・4 = 31・5 - 11・14
　= 31・5 - (42 - 31・1)・14 = 31・19 - 42・14
これで 31・19 - 42・14 = 1 が判ったから、
31x₀ - 42n₀ = 1 と辺々引き算すると
31(x₀ - 19) = 42(n₀ - 14) と変形できる。
両辺は 31 と 42 の公倍数だから、
31(x₀ - 19) = 42(n₀ - 14) = (31・42)k　； kは整数
と置いて x₀ = 19 + 42k.
よって、x = 5x₀ = 5(19 + 42k) = 11 + 42(2 + 5k).
すなわち x ≡ 11 (mod 42).

この回答へのお礼

ご回答ありがとうございます！
むずかしいですね…
この回答を参考に自分でも問題を解いてみたいと思います！

お礼日時：2021/05/29 15:12