Ich benutze im Weiteren für den ggT zweier ganzer Zahlen \(a,b\) die Schreibweise
\((a,b)\)
Selbstverständlich kannst du ohne Beschränkung der Allgemeinheit festlegen, dass
\(m\leq n\)
Andernfalls benennen wir die Zahlen einfach um.
Die gegebene Gleichung ist eine Trivialität, die einfach nur eine anders geschrieben Version der folgenden allgemein bekannten Beziehung ist:
\(g^{n+1}-1 = (g-1)(g^n+\cdots + g + 1)\)
Mit ihr kann man schnell zeigen:
\(a^{(n,m)}\) ist ein Teiler von \(a^n-1\) und \(a^m-1\)
Man kommt auch ohne obige Gleichung aus. Zum Beispiel mit folgender Induktion:
Zu zeigen ist, für jedes \(n\in\mathbb N\) gilt:
\(1\leq m \leq n \Rightarrow (a^n-1, a^m-1)=a^{(n,m)}-1\)
\(n=1\): Trivial
\(n\rightarrow n+1\):
Sei die Aussage für alle natürlichen Zahlen bis \(n\) richtig.
Sei nun \(1\leq m\leq n+1\). Für \(m=n+1\) gibt es übrigens nichts zu zeigen. Sei also \(1\leq m \leq n\).
Nun gilt per Standard-Schritt im Euklidischen Algorithmus:
\(a^{n+1}-1 = a^{n+1-m}(a^{m}-1) + a^{n+1-m}-1\)
D.h.,
\((a^{n+1}-1,a^{m}-1) = (a^{m}-1,a^{n+1-m}-1)\)
Auf die rechte Seite wenden wir die Induktionsvoraussetzung an:
\((a^{m}-1,a^{n+1-m}-1) = a^{(m,n+1-m)}-1\)
Nun ist aber wegen \(n+1 = m + (n+1-m)\)
\((m,n+1-m) = (n+1,m)\)
Damit sind wir fertig.
