最大公約数

質問

整数a=2020,b=1022の最大公約数dを求めよ。また、d=ax+yb となるx,y€Zを1組求めたいです。

回答No.2

tmppassenger · ベストアンサー

ユークリッドの互助法を使い、その逆算を行う

2020 + 1022 * (-2) = -24
1022 + 24 * (-42) = 14
24 + 14 * (-2) = -4
14 + 4 * (-3) = 2
4 + 2 * (-2) = 0

となるから最大公約数は 2。ここから逆算を行う

2
= 14 + 4 * (-3)
= 14 + (14 * 2 - 24) * (-3) = 14 * (-5) + 24 * 3
= (1022 + 24 * (-42) ) * (-5) + 24 * 3 = 1022 * (-5) + 24 * 213
= 1022 * (-5) + (1022 * 2 - 2020) * 213 = 1022 * 421 + 2020 * (-213)

となって、2 = 1022 * 421 + 2020 * (-213)　が一つの答えとなる

回答No.1

notnot

＞整数a=2020,b=1022の最大公約数dを求めよ。

最大公約数を求めるには、
方法1：それぞれ素因数分解して、共通部分を見る
方法2：ユークリッドの互除法を使う

普通は方法2ですが、2020 1022はどちらも簡単に素因数分解出来るので方法1も簡単です。

＞また、d=ax+yb となるx,y€Zを1組求めたいです。

これは難しいですね。
プログラムを書いて探すと、x=-213 y=421
しかし、問題になっている以上、プログラムを書かないでも求められる方法はあるはずです。