ユークリッドの互除法
世界最古に発見されたアルゴリズムのひとつとして知られるユークリッドの互除法は, 歴史上の価値のみならず, 公約数という素因数が絡む計算を素因数分解せずに効率的に求めることができるという点で非常に有用な手法となっています.
ユークリッドの互除法とは, 2つの0ではない整数a, b に対して, 次の手続を繰り返すことで a と b の最大公約数を求めることができます.
- b=0 ならば a が求めるべき最大公約数である. アルゴリズムはここで終了する.
- c≡a (mod b) を計算し, a に b を代入, b に c を代入する.
- 最初に戻る.
ラメの定理により, アルゴリズムの繰り返し回数は a, b のうち小さい方の 10 進桁数を d とすれば, 高々 5d 回となることが知られており, 5d 回程度の繰り返しが発生する例はフィボナッチ数列(最初の2項を1としたもの)の隣接2項を対象とした場合が知られています.
もしも, これを素因数分解で解決しようとすると, a, b のうち小さい方の正の平方根の数だけ「試しに割り算して割り切れるかを確かめる」作業が必要となります。
つまり, a≥bのもとで割算の回数を比較すると, ユークリッドの互除法ならば 2.2log(b), 素因数分解するなら √b と見積もることができます. b が大きい場合, どちらの方が効率がいいのかは明らかです.
この方法を拡張すると不定方程式 ax+by=gcd(a,b) の整数解を導出することができます. これが拡張されたユークリッドの互除法です. 拡張されたユークリッドの互除法の手順は次のとおりです.
- r0=a, s0=1, t0=0, r1=b, s1=0, t0=1, i=1 とする.
- ri+1=ri-1–qiri を 0≤ri+1≤abs(ri), qi は整数となるように定める.
- si+1=si-1–qisi, ti+1=ti-1–qiti とする.
- ri+1=0 の場合は x=si, y=ti であるので計算を終了する. ri+1≠0 の場合は次の項目に進む.
- i に 1 を加えて 2. の項目へ戻る.
大学入試センター試験平成28年度本試験数学I・数学A
の第4問(1)を例に示します. (文面は桁数が推測できないように穴埋め部分を再編.)
不定方程式 92x+197y=1 を満たす整数 x, y の中で, x の絶対値が最小である x, y の組, および, 不定方程式 92x+197y=10 を満たす整数 x, y の中で, x の絶対値が最小である x, y の組を求めよ.
まず, 92x+197y=1 を満たす整数 x, y の組をひとつ求めます. まず, 解の存在を確かめるため, gcd(92, 197) を計算します. すると, 次の表のように, 最大公約数が 1 であることが確認できたため, この不定方程式を満たす整数解は存在します.
| Index | a | b | c≡a (mod b) |
|---|---|---|---|
| 0 | 92 | 197 | 92 |
| 1 | 197 | 92 | 13 |
| 2 | 92 | 13 | 1 |
| 3 | 13 | 1 | 0 |
| 4 | 1 | 0 | * |
では, 拡張されたユークリッドの互除法を用いて不定方程式の解の一般形を求めましょう. まずは, 解のひとつの組を求めます.
| Index i | 商 qi-1 | 剰余 ri | si | ti | ||||
|---|---|---|---|---|---|---|---|---|
| 0 | * | 92 | 1 | 0 | ||||
| 1 | * | 197 | 0 | 1 | ||||
| 2 | 92÷197= | 0 | 92-0×197= | 92 | 1-0×0= | 1 | 0-0×1= | 0 |
| 3 | 197÷92= | 2 | 197-2×92= | 13 | 0-2×1= | -2 | 1-2×0= | 1 |
| 4 | 92÷13= | 7 | 92-7×13= | 1 | 1-7×(-2)= | 15 | 0-7×1= | -7 |
| 5 | 13÷1= | 13 | 13-13×1= | 0 | -2-13×15= | -197 | 1-13×(-7) | =92 |
これにより x=15, y=-7 は不定方程式の解のひとつであることがわかります. ただし, この x が絶対値を最小とする解であるかどうかは分かりません. なので、次のようにします. 不定方程式 92x+197y=1 と 92×15-197×7=1 について辺々差をとります. すると, 92(x-15)+197(y+7)=0 の関係を得ます. gcd(92, 197)=1 なので, K を整数として x-15=197K という関係になります. つまり, x=197K+15 です. よって, この不定方程式を満たす最小の正の整数 x は 15, 最大の負の整数 x は -182 です. なので, 題意を満たす解の組は x=15, y=-7 となります.
では, 不定方程式 92x+197y=10 はどうでしょうか. これについては 92×15-197×7=1 を 10 倍した 92×150-197×70=10 との差をとることで考えます. つまり, 92(x-150)+197(y+70)=0 の場合です. 先ほどと同様に x=197K+150 という関係を得ます. よって, この不定方程式を満たす最小の正の整数 x は 150, 最大の負の整数 x は -47 です. なので, 題意を満たす解の組は x=-47, y=22 となります.
