「ブロック機能」のリニューアルについて

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

問)
31x ≡ 5 mod 42

教えて!goo グレード

A 回答 (1件)

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 倍します。

x₀, n₀ の方程式は、係数の最大公約数を求める
ユークリッドの互除法から、
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).
    • good
    • 3
この回答へのお礼

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

教えて!goo グレード

人気Q&Aランキング