Fügt man nun n zusammen zu
1n,
2n,
3n
etc. so sieht man, daß gegenüber
einem Vielfachen von m solange ein Rest bleibt,
bis man
zu m ∙ n kommt, wo immer der
Euklidische
Algorit
hmus endet (d.h.
welche der Formeln immer für m anwendbar ist).
Im ersten Fall z.B. wenn
m =
a
1a
2 + 1 :
1n =
a
0m + a
2
2n =
2a
0m + 2a
2 …
vn =
va
0m + va
2 der Rest
va
2 bleibt jedenfalls
solange kleiner als m, bis v = a
1 wird; dann
ist
77
a
1n = a
1a
0m
+ a
1a
2.
Noch immer ist der Rest kleiner als m; aber nun wird
(a
1 + 1).n =
(a
1 + 1)a
0m +
(a
1 + 1).a
2 =
… + a
1a
2 + a
2
=
… + a
1a
2 + 1 + a
2 ‒ 1
a
2 ‒ 1 ist jedenfalls
kleiner als m und der Rest verschwindet nur, wenn
a
2 =
1 ist.
Dann aber ist m
= a
1 + 1, also der Faktor
a
1 + 1
= m.
Ist aber a
2 größer als
1, so geht die Sache weiter und es folgen nun
(a
1 + 2).n =
… + 2a
2 ‒ 1
…
(a
1 + v).n
= … + va
2 ‒ 1.
Dieser Rest ist gewiß kleiner als
m,
bis
(2a
1).n =
… + a
1a
2 ‒ 1 und auch hier
noch.
Aber
(2a
1 + 1).n =
… + (a
1 + 1)a
2 ‒ 1 =
a
1a
2 + a
2 ‒ 1 =
a
1ma
2 + 1 + (a
2 ‒ 2) und hier
geht
der
Prozeß wieder nur dann auf, wenn
a
2 =
2, dann aber ist m = 2a
1 + 1, also
wieder gleich dem Faktor von n. –
Ebenso geht es weiter bis
(3a
1).n =
… + a
1a
2 ‒ 2 und
(3a
1 + 1).n =
… + m + (a
2 ‒ 3) so lang bis
(a
2a
1 + 1).n =
… + (a
2 ‒ a
2) =
m.n.
Ähnlich geht es, wenn
m =
a
1a
2a
3 + a
3 ist,
etc. etc..