割り算の式
10を3で割ると、商が3で余りが1ですね。
これを式で表すと、次のように表すことができます。
これは何も10と3に限った話ではありません。
ある整数（割り算なので整数を考えます）aをある正の整数（負の数とすると余りがややこしくなりますので負の数としましょう）bで割ることを考えます。
商がqで余りがr（ただし）としましょう。
このときやはり、
と表すことができます。
割り算と最大公約数
実は割り算と最大公約数にはある関係があります。
整数aを正の整数bで割った商をq、余りをrとし、以下のように表す事ができました。
･･･①
（ただし）
aとbの最大公約数をqとするとある整数があって、と掛けます。
これを①に代入すると、
となります。
等式なので左辺と右辺は等しい数なわけですから、当然最大公約数も等しくgになるはずです。
という事は右辺はgで割り切れるので、rがgで割り切れる事になります。
つまり、aとbの公約数はbとrの公約数というわけですね。
逆にbとrの公約数g’があるとすれば、当然右辺もg’で割り切れるはずです。
つまり、つまりbとrの公約数はaとbの公約数にもなるという事です。
以上の事から、aとbの最大公約数はbとrの最大公約数という事になります。
ユークリッドの互除法
に対し更にbをrで割るという事を考えます。
するとbとrの最大公約数はrとr’の最大公約数になります。
更に余りは割る数よりも小さくならなければなりません。
5で割ってあまりが5以上は正しく割り算の計算ができていないですからね。
という事はでになります。
これはあわせて書くとになります。
つまり余りはどんどん小さくなるわけです。
一方でaとbの最大公約数がbとrの最大公約数でした。
同じようにbとrの最大公約数がrとr’の最大公約数になります。
さて、この操作を繰り返していくと、余りがどんどん小さくなるわけですから、やがて余りが0、つまり割り切れます。
例えばもう一回やって割り切れたとしましょう。
これはrとr’の最大公約数がr’だったという事ですね。
なお、最大公約数が1だった場合、最終的に
みたいなことになります。
例題はユークリッドの互除法の問題の解法をご参照ください。
素因数分解の一意性
ある整数を素数の積で表すことを素因数分解と言います。
※素数は1とその数の他に約数が無い正の整数の事です。2,3,5,7,11,…無限個あります。
この素数の積で表すとき、その素数の「組み合わせ」は1つだけです。
15であれば3が1つ、5が1つ以外の表し方はありません。
45であれば3が2つ、5が1つ以外の表し方はありません。
一次不定方程式
のような形の方程式を2元一次不定方程式と言います。
単に一次不定方程式と呼ぶことにします。
この方程式を満たすの組を一次不定方程式の解と言います。
また解の内ともに整数になるような解を整数解と言います。
一次不定方程式の解き方は一次不定方程式の問題の解法をご参照ください。
