a*x + b*y = gcd(a,b) を解く のヒント。
例として $28x + 13y = gcd(28,13)$ で考えてみる。
- もちろん他のやり方もあると思う
- 以下では説明上、未知数を $x_{1}, x_{0}$ とする
ヒント１
元の式を「ある規則」で変形していくだけ。何か気づかない？
$28x_{1} + 13x_{0}$
$= ....$
$= ....$
- なおよく覚えていないが、わたしは 5分ほどかかってやっとひらめいた
「ある規則」とは、もちろん「最大公約数」を求たときの有名なアルゴリズム。
- というより、この問題のほうがそのアルゴリズムがよく分かる
ヒント２
少しやってみよう。
$28x_{1} + 13x_{0}$
$= (2\times13+2)x_{1} + 13x_{0}$
$= 13(2x_{1}+x_{0}) + 2x_{1}$
$= 13x_{2} + 2x_{1}$
- ここで $(2x_{1}+x_{0})=x_{2}$ と置いた (この関係は忘れてかまわない）
- 不思議なことに（もちろん当たり前なんだけど）、係数が小さくなっちゃた！
- これを続けていくと‥‥
ヒント３
$28x_{1} + 13x_{0}$
$= 13x_{2} + 2x_{1}$
$= 2x_{3} + x_{2}$
$= 1x_{4} + 0x_{3}$
$= gcd(28,13) $ ～ 元の式の右辺
右の係数が 0 になったときの左の係数が、元の係数の最大公約数なので、
$gcd(28,13) =1$ が求まったことになる。
- 従って $x_{4}=1$、$x_{3}$ は何でもよいので例えば $x_{3}=0$ とする
- すると3行目 $2x_{3} + x_{2}=1$ から $x_{2}$ が分かり、2行目から $x_{1}$、 1行目から $x_{0}$ が求まる
- 要するに $gcd$ が求まったら、今度は下から上へバックトラックしていけばよい
- なお $x_{3}$ の値を変えると別の解が得られる
プログラム作成
では実際にプログラムを作ってみてください。
以下の３通りでやってみるとよい練習になるかも？
- 表計算 ～ Excel, Google spreadsheet など
- 再帰呼び出しを使う ～ 普通に書いて8ステップ、ワンライナーも可能
- 再帰呼び出しを使わない
蛇足
これは算数の問題。
$28 \times \bigcirc - 13 \times \bigtriangleup = 1$ なら小学生でも分かる。（3/10 負の数を使わなくても解けるようにマイナスにした）
ガウス少年なら一瞬で解いたであろうが、日本の小・中学生にも解ける子がいるはず。
参考
bezout.js
// returns [x,y,g]
function bezout(a,b,yn, depth) {
var res;
if(b == 0) {
res = [1, yn, a];
} else {
var rres = bezout(b, a%b, yn, depth+1);
var y = (rres[2] - a * rres[1])/b;
res = [rres[1], y, rres[2]];
}
return res;
}
// 実行は a, b と yn に整数を与えて depth=0 で呼び出すだけ
// yn は複数解のうちから１つだけ選択するため。とりあえず 0 でよい
var res = bezout(a,b,yn, 0);