約数？ 因数？
0でない整数aとbがあるとする。
「数字と数式の種類」数学の基礎の基礎。
ここでaがbを割りきれるとする。
つまり適当な整数kがあるとして、b = akの形を作れるとする。
aはようするにbの約数というやつである。
aが1かbしか成り立たないなら、bは素数ということになる。
「素数とゼータ関数」リーマン予想に晒された架空の実領域
そうではないとする。
例えばaが1と6以外に2と3なら、bは6であろう。
6の約数は1、2、3、6である。
そういうのはまた「因数（factor）」と呼ばれる。
約数と因数は 基本的に同じ意味なのだが、因数の方がやや抽象的な感じがする。
gcd。最大公約数の示し方
それではまた、2つの整数a、bをあらためて用意する。
それらのどちらの約数の中にもkがある場合、kはaとbの「共通因数（Common factor）」とか「公約数（Common divisor）」などと言う。
例えば4は12と20の共通因数（公約数）である。
またこの場合の4は12と20の共通因数の中で最大の数、いわゆる「最大公約数（greatest common divisor）」となる。
ある数と数の最大公約数の書き方として、以下のようなものがある。
gcd(a、b)
例えば gcd(12、20) = 4 みたいな感じである。
gcd（greatest common divisor）でなく、gcm（greatest common measure）が使われる場合もある。
また、もし gcd(a、b) = 1 なら、「aとbは互いに素である（a and b are relatively prime）」とかいうふうに表現される。
X＋XがYで割れるなら、X＋X＋XもYで割りきれる
例えばxで割りきれる数yがあるとする。
この場合y = x + x + x……も同然であろう（ここではこれは詳しく定義はしない。時には直感が大事である）。
x + x + x……というのは有限の数とする。
しかしx + x + x……の形なら、xで割りきれる数だから、明らかにx + x + x……+ xも、xで割りきれる数である。
「無限量」無限の大きさの証明、比較、カントールの集合論的方法
やはりこういうのは、ちゃんと数字をあてた方がわかりやすいという人もいるだろう。
45は5で割りきれるわけだが、45というのは5×9でもある。
5×9+5は、つまり5×10であり、やはり5で割りきれる50である。
つまり何が言いたいかというと、xで割りきれる数yがあるなら、y + xもまたxで割りきれるということである。
このことを理解しておくことは、以下の話を理解するのに役立つ。
ユークリッド・アルゴリズム
aとbの最大公約数を求めたいとする。
力押しでもいいし、コンピューターの助けを借りてもいいが、なるべく早くすませたく、コンピューターも使えない状況なら、「ユークリッドの互除法（Euclidean Algorithm）」というのが便利である。
おそらくaとbの数が大きければ大きいほど、その威力を実感できる。
場合によっては、ごく簡単である。
例えばaとbがあってaがbで割りきれる数なら、それすなわちbがaとbの最大公約数である。
例えば100は10で割りきれるわけだが、 gcd(100、10) = 10 なわけである。
しかし例えば1000と562ならばどうか。
この場合1000を562で割ると明らかに438余ってしまう。
それと、そんな計算はわざわざするまでもなく、1000の約数に562が入ってないのは明らかすぎる。
つまりこの時、562が公約数はありえない。
こういう場合に、わざわざ1000と562の約数を全て算出し、照らし合わせていかなくても、これらの最大公約数を見つけることができる術がユークリッドの互除法である。
なぜ数学を学ぶのか？「エウクレイデスと原論の謎」
余りを余りで割っていく
以下の話において、aとb以外は定数でないことには注意（エッセー1）。
aとbを割ると、余りがsでてくるとする。
この場合に商（割り算の答）がqだとすると、以下の形を用意できる。
a = q × b + s（1）
ここからちょっとしたアルゴリズムを作る（仮にYアルゴリズムと呼ぶことにする）。
（1）におけるaとqのことはもう忘れ、次にbをsで割る。
するとまた、そこで新たな商qと余りsが発生するだろう。
つまり（1）のsを区別のためs_とすると、また以下のような形が現れる。
b = q × s_ + s（2）
以降、（2）の式の場合のbをs_に、s_をsに置き換える作業を、式のsが0になるまで繰り返していく。
言葉で説明するならこのYアルゴリズムは、ある数xをyで割り、出てきた余りでyを割る。
さらにそうして出てきた余りで、前の式の余りを割るというのを、余りが0になるまで繰り返すというものである。
（エッセー1）ワタシはツカイマワスノがスキ
今は数学よりもコンピューターのプログラミングに慣れてる人の方が多いだろうし、多くなっていくと思う。
プログラミングでは、ある変数を使い回したりすることもある。
だから数学の思考などにおいても、使い回せるものは使いまわすのがよいと思う（ある程度慣れてる人が多いだろうし）。
個人的には、p1、p2、p3……とか、pn-1、pn、pn+1……みたいなのは、むしろわかりにくいと思います。
やがては必ず0になる
Yアルゴリズムに終わりがない可能性はあるだろうか。
そんなものはおそらくない。
このアルゴリズムの肝は、あるふたつの数a、bの商qと余りsを求める形の式 a = q × b + s である。
これの余りsだが、それがbより大きい数であることはありえないだろう。
大きい数だとしたら、qをしかるべき数だけ倍化して、また小さくなるだけだ。
そしてYアルゴリズムでは、次式のbのポジションに現在のsが入ることになる。
つまり次式の余りは、現在の余りよりさらに小さくなるのは必然。
Yアルゴリズムにおいて、余りsは小さくなっていくわけだが、そうなると、やがては0になるのも必然というわけである。
「ゼロとは何か」位取りの記号、インド人の発見
そしてこのYアルゴリズムこそが、そもそもユークリッドの互除法の肝なのである。
アルゴリズムが止まった時
ある数aとbに対し、Yアルゴリズムを適用させてみる（数字は掛け算とかでないことに注意）。
a = q × b + s（1）
↓
b = q2 × s + s2（2）
↓
s = q3 × s2 + s3（3）
↓
s2 = q4 × s3 + s4（4）
↓
s3 = q5 × s4 + s5（5）
……みたいな感じで繰り返されるわけだが、仮に（5）における余り（s5）が0になったとする。
つまり s3 = q5 × s4 + 0（5） になり、アルゴリズムが止まったとする。
肝心なのはここからだ。
つまり公約数
まず（5）から、s3がs4で割りきれる数なのは明らかであろう。
割りきれないなら余りは0でないはずだから。
ここで、xで割りきれる数yがあるなら、y + xもまたxで割りきれるということを思いだそう。
（4）の式からs2は、s4で割りきれる数であるs3 + s4である。
つまりs2はs4で割りきれる。
同じように考えていけばs2もsも、そしてbとaもs4で割りきれるということになる。
つまりs4は、aとbの公約数である。
その中で最大の数でもある
次にs4とは別に、aとbの別の公約数zがあるとしよう。
アルゴリズムの最初の式 a = q × b + s（1） を用意する。
zは、aとbのどちらも割りきれるわけだから、（1）が成り立つならsも割れなければおかしい。
続いて次の b = q2 × s + s2（2） はどうか。
zはbとsのどちらも割りきれるわけだから、s2も割りきれなければおかしい。
やはり同じように考えていけば、zはs4を割りきれることになるが、だとするとzがs4より大きいはずはない。
というわけで、いよいよ結論が出てくる。
つまりYアルゴリズムの最後の式の前の式の余りsN（今回の上記例の場合はs4）こそが、aとbの最大公約数である。
なぜならそれは公約数でかつ、他のどの公約数zよりも大きいから。
そしてこのYアルゴリズムの性質を利用して、2つの数a、bの最大公約数を見つける手法こそが、ユークリッドの互除法というものである。
具体例。例えば1000と562の場合
実際にユークリッドの互除法で、1000と562の最大公約数を求めてみる。
1000 = 1 × 562 + 438（1）
↓
562 = 1 × 438 + 124（2）
↓
438 = 3 × 124 + 66（3）
↓
124 = 1 × 66 + 58（4）
↓
66 = 1 × 58 + 8（5）
↓
58 = 7 × 8 + 2（6）
↓
8 = 4 × 2 + 0（end）
つまり、1000と562の最大公約数は（6）の式の余り、すなわち2なわけである。
それと、最低限の機能の電卓でa = q × b + sの形を比較的簡単に求めるためには、まずa÷bを普通に行う。
電卓なら余りがいくつとかはでないで、普通に答は小数になるはず。
その答の小数の小数点以降の数を全て切り捨てる。
切り捨てた後の答えが、式のqにあたる。
sに関しては a – b × q で求めれる。
