ユークリッドの互除法「ＡとＢ（但しＡ≧Ｂ）の最大公約数は、Ｂとｒ（Ａ÷Ｂの余り）の最大公約数に等しい」

オンライン家庭教師はじめました。
ご興味がおありでしたら、
①以下のホームページへアクセス、
https://man2man.jp/service/ワンセンテンス算数の算数（マンツーマン）/
②ユーザー登録（ユーザー登録はこちらから）ののち、
③上記ホームページの下の方に私宛のメッセージ機能（STEP１として「ワンセンテンス算数さんにメッセージを送る」というボタン）がありますので、そちらからお問い合わせください。

前回、文章題において、消去算かいもづる算かを事前に判別することの有用性を説きました。

いもづる算「まずは、消去算（ｎ個の未知数ｎ個の式）かいもづる算（条件不足）かを判別する。」

問題文を定式化して、ｎ個の未知数で、ｎ個の式がたてられれば、以降、１組の解が出ることをわかったうえで、いわゆる一般の方程式（消去算）の問題として安心して演算すればよいことがわかります。

また、ｎ個の未知数があるのに、ｎ個の式がたてられない場合は、その段階では１組だけの答えがでないと知ることができます。そして、改めて、正の整数解をみつけるための、より簡単な方法（※）はないかな、と別の視点で考えていくことができるのです。

（※）　ａｘ＋ｂｙ＝ｃ　（ａ、ｂ、ｃは整数）　の整数解は面倒ではあっても機械的に解くことができます。

ところで、この注意書きした機械的に解く方法は、この方法を利用すれば上記の式を必ず解くことはできるものの、面倒な計算になってしまいがちです。従って、試験では、別の簡単な方法を見つけて解くことが多く、この方法を使うことはほとんどありません。また、この方法を説明するには少々時間がかかるうえ、理解するには、代数やマイナスの概念が必要なため、ここでの説明はやめておこうかと考えていました。

ただ、必ず解くことができるという安心感が、やみくもに信じるところからきているのか、実際にそこそこ納得した上でのものなのかで、全然違うため、小学生には少々難しいかもしれませんが、今回から数回にわけて、これを説明することにします。

そして、一度納得したら、小学生の間にこの話にもどる必要はありません。あとは上記のように、”安心して”　正の整数解をみつけるための、より簡単な方法をみつけることに集中すればよいのです。

ということで、今回はその説明をするために必要な材料、ユークリッドの互除法について、説明します。