最大公約数

　自然数a, b に対して， a の正の約数の集合をA, b の正の約数の集合をB とします。 A にも B にも属する数をa と b の(正の)公約数といいます。 公約数の集合は A ∩ B (A と B の共通部分)です。 約数の集合は有限集合です。公約数の集合も有限集合です。 その中で，最大の数を 最大公約数 と呼んでいます。

　a = 360, b = 100 とします。
a = 2³・3²・5,   b = 2²・5²
と分解されます。このように，自然数の積に分けられない形まで分解する， （n = 1・n は除きます） 言い換えると，素数だけの積に分解することを素因数分解するといいます。 g = 2²・5 とおくと， a = 18g, b = 5g となるので，g は a, b の最大公約数です。
最小公倍数は l = 2³・3²・5²です。

　次のように共通因数で割っていく， すだれ算といえるような方法があります。

2	)	360	100
2	)	180	50
5	)	90	25
		18	5

g = 2²・5
実際には素数で割らなくてもいいのではと思います。

　最大公約数を求める方法をもうひとつ紹介しましょう。
横の長さ360, 縦の長さ100 の長方形から同じ大きさの正方形を無駄なく切り取ります。 一辺の長さが1 であれば問題ありませんが，できるだけ大きい正方形を切り取るには， 一辺の長さをいくらにすればよいでしょうか。
この長方形から一辺の長さが100 の正方形を切り取ると，3つできて，横60, 縦100 の長方形が余ります。
さらに，この長方形から一辺の長さが60 の正方形を切り取ると，1つできて，横60, 縦40の長方形が余ります。
さらに，この長方形から一辺の長さが40 の正方形を切り取ると，1つできて，横20, 縦40の長方形が余ります。
この長方形からは一辺の長さが20 の正方形が2つ切りとることができて，余りはありません。
40 = 20 × 2, 60 = 20 × 3, 100 = 20 × 5 ですから， 答えは一辺の長さが20 の正方形です。 20 は 360 と 100 の最大公約数です。
このような求め方をユークリッドの互除法といいます。