ユークリッドの互除法

ひとつめの図は，横に○が26個並んでいて，左上から30個ごとに●と塗りつぶされている。
ふたつめの図は，横に○が30個並んでいて，左上から26個ごとに●と塗りつぶされている。
みっつめの図は，横に○が26個並んでいて，左上から4個ごとに●と塗りつぶされている。

n	1	2	3	4	5	6	7	8	9	10	11	12	13
30n (mod 26)	4	8	12	16	20	24	2	6	10	14	18	22	0
4n (mod 26)	4	8	12	16	20	24	2	6	10	14	18	22	0

いつものように数学を構成してみる。
繰り返しがテーマである。逐次的に数列を生成しているイメージも大切である。

整数a, b, cにおいて， c = am = bn なる整数 m, n があるとき，
c は a と b の公倍数であるという。

整数a, b, cにおいて， cm = a かつ cn = bなる整数 m, n があるとき，
c は a と b の公約数であるという。

整数 a , b とその最小公倍数 l と最大公約数 g における関係式 ab=lg が成り立つ。

この3つの図をみて感じるものがあるだろうか。
右端が●と塗りつぶされるのは公倍数である。
30 と 26 の最小公倍数は 30 × 26 ではなくて， 30 × 13 = 26 × 15 である。
(図1では15行目の右端が，13個めの●, 図2では13行目の右端が，15個めの●)
30 と 26 の最大公約数は 2 である。

表のように，30n と 4n は　26 を法として等しい。
図1と図3を比べると○が少なくなっているが， ●の配置は変わっていない。
4 と 26 の最小公倍数は 4 × 26 ではなくて，4 × 13 である。
(図3では2行目の右端が，13個めの●)
4 と 26 の最大公約数は 2 である。

倍数と約数が本来表裏一体であるように，
公倍数と公約数も切り離すことは意味がない。
それが関係式 ab=lg である。
この図は公倍数を求めているようでいて，公約数を求めている。
30と26の最小公倍数は 30× 26 ÷ 2である。
4と26の最小公倍数は 4× 26 ÷ 2である。
最小公倍数は等しくはないが，最大公約数は等しい。

a と b の最大公約数と，
b と a-bq の最大公約数は，等しいようである。

実際, d を a と b の最大公約数とすると，
a = a′d, b = b′d, a′と b′は互いに素であるが，
a-bq = d(a′- b′q) より，d は b と a-bq の公約数である。
a′とb′は互いに素であるから， a′- b′q と b′も互いに素である。
したがって，d は公約数の中で最大である。

整数 4