数学的活動の一場面

～整数の性質において～
http://goo.gl/MFRFj

1次不定方程式

倍数判定法というのが，数研出版の教科書にありましたが，
ユークリッドの互除法までは，記数法によらない。
倍数判定法は記数法そのものとかかわりがあります。
1001=7×11×13なんて結構驚きです。

1次不定方程式はまた，記数法によりません。
お分かりのとおり，不定方程式\(ax+by=c\)は
合同式を使えば，\(ax\equiv c\) (mod \(b\))を満たす\(x\)を求めていることにほかなりません。
先ほどの議論により，\(c\)が\(a\), \(b\)の最大公約数の倍数であるとき解が存在します。

特に，\(a\), \(b\)が互いに素であれば，
\(ax\equiv 1\) (mod \(b\))なる\(x\)が存在しますが，
それは，\(a\)倍写像が\(b\)を法とする剰余類の全単射をもたらしているからです。
整数が単項イデアル整域であるといわれる理由ですね。

同じことですが，
\(a\), \(b\)が互いに素であれば，
\(a\)の倍数は\(b\)を法とする\(b\)個の剰余類を，いずれ埋め尽くすのです。
以前，高教研で質問したことの正確な説明です。
表

不定方程式を解くためには，倍数の比較をすることが本質です。
アルゴリズムとして，求め方を記述するなら，互除法の商を利用することになります。

あとは，連分数。
それが出てくると，黄金比と連分数とフィボナッチ数列の話題と尽きません。