証明が出来てもプログラムが書けないことには意味がない。いうことで書いてみる。0としているが、ここは任意の整数でいい。(逆元は一つだけじゃないので。y)を複数個求めてみる。extGcd()を書きかえて、b=0のときのyの値を選べるようにしてやる。(本当は、クロージャみたいなので書くといいのかも。y)の組が10個求まりました。無理数xを、有理数N/Dで近似するというのは、よくあるテーマ。現実的には、適当に有理数の分子、分母に上限を付ける。Dを求める問題を考えることになる。アルゴリズムをやったことがある人なら、Dを全部まわして、Nを二分探索するという方法を思いつくだろう。1,000,000程度でも一瞬で答えが出る。実は二分探索よりも、もっと面白い方法がある。N/(D+1)に移動、そうでなければ探索点を(N+1)/Dに移動。これを逐次繰り返していき、最良点を保持すれば答えが出る。以下、サンプルソース。100007/100009として解いてみる。D);}見事、元の分数の分子、分母を再現できる。Dが求まることが分かる。(ざっくりした証明的なものです。数学得意な人がいたら、厳密な証明方法教えてください。-1)が探索されれば、最適解にたどりつく。