Sei \(N^*\) die Menge der nat. Zahlen \(>0\).
Die Menge \(\{a^r mod \; q:\; r\in N^*\}\) ist endlich, da es \(mod\; q\) nur
endlich viele Restklassen gibt, d.h. es gibt ein Paar \(r,s\in N^*\) mit
\(r>s\) und \(a^r mod \; q=a^s mod\; q\).
Sei \(p=r-s\), dann gilt mit \(n_0 \, :=s\) :
\(a^{n_0+p} \, mod \; q=a^{n_0} \, mod\; q\).
Ist nun \(n\gt n_0\), also \(n=n_0+t\) mit \(t\in N^*\), so ergibt sich
\(a^{n+p}\, mod \;q=a^{n_0+p+t}\, mod \; q=a^{n_0+p}a^t\, mod \; q=a^{n_0}a^t \, mod \;q=\)
\(a^{n_0+t}\, mod \; q=a^n\, mod \; q\).
