いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

互いに素な2数に互除法を実行すると、最後に余りが1になる

www.omoshiro-suugaku.com

 ↑この記事の中で、「互いに素な2数に互除法を実行すると、最後に余りが1になる」という事実を使っています。一応、理屈を明らかにしておきましょう。

 記事では互いに素な2数a,bに対して互除法を実行して次のようになったとしています。

f:id:Inuosann:20211229120727p:plain

このとき、例えばf:id:Inuosann:20211229120838p:plainとなるのです。もちろん互除法の手続きは何回続くか、場合によっていろいろですが、証明の理屈は変わりません。(x,y)でxとyの最大公約数を表すとき、例えば

(15,8)=(8,7)=(7,1)

(20,7)=(7,3)=(3,1)

などとなりますから、どうやら主張は正しそうです。

 

 (a,b)=1である2数に対して互除法を実行して、途中の行が z=wq+r となったとしましょう。qが商、rが余りです。割り算の実行のたびに余りは小さくなります。だから、もちろん本当の最後には必ず余りは0になるはずです。その直前の行はどなっているでしょうか。もし、●=▲×■+2だとすると、最大公約数が2ということになって矛盾です(次の行では余りが0なのだから!)。●=▲×■+3なら、最大公約数が3で矛盾です。結局、ちょうど割り切れる(余りが0になる)直前の行では●=▲×■+1とならざるを得ないのです。

 ……ということで、タイトルにある事実は示せました。

 

 ここ何年か、2元1次不定方程式の特殊解を求める方法を数学Aで勉強させています。ユークリッド互除法を使うのですが、(教科書の説明そのままだと)分かりにくいところだと思います。ぼくは次のように説明しています。他の先生がどうやっているのか知りません。多分これとは違う方法だと思いますが、今度聞いてみます。

www.omoshiro-suugaku.com