Marokko IV

 Die vierte Aufgabe aus dem Abitur in Marokko 2021 behandelt die Zahlentheorie:

Sei \(a \ge 2\) eine natürliche Zahl und \(A = 1 + a + a^2 + a^3 + a^4 + a^5 + a^6\). Sei \(p\) eine ungerade Primzahl, welche \(A\) teilt.

• 1.a)  Zeige, dass \(a^7 \equiv 1 \bmod p\) ist, und folgere, dass \(a^{7n} \equiv 1 \bmod p\) für alle \(n \in \mathbb N\) ist.
• b) Zeige, dass \(a\) und \(p\) teilerfremd sind, und folgere, dass für alle \(m \in \mathbb N\) gilt: \(a^{(p-1)m} \equiv 1 \bmod p\).
• 2.a) Wir nehmen jetzt an, dass 7 kein Teiler von \(p-1\) ist. Zeige, dass \(a \equiv 1 \bmod p\) gilt.
• b) Folgere, dass \(p = 7\) ist.
• 3. Zeige: Ist \(p\) eine ungerade Primzahl, welche \(A\) teilt, dann ist \(p = 7\) oder \(p \equiv 1 \bmod 7\)

Fangen wir an. Um etwas über \(a^7\) herauszubekommen, multiplizieren wir \(A\) mit \(a\) und finden \(Aa = a + a^2 + a^3 + a^4 + a^5 + a^6 + a^7 = A + a^7-1\). Also ist \(a^7-1 = Aa - A\) durch \(p\) teilbar, weil \(A\) durch \(p\) teilbar ist. Wenn \(a\) und \(p\) nicht teilerfremd sind, dann ist \(p\) ein Teiler von \(a\), weil \(p\) prim ist. Dann folgt aber \(A = 1 + a + a^2 + \ldots + a^6 \equiv 1 \bmod p\) im Gegensatz dazu, dass \(p\) ein Teiler von \(A\) ist. Damit ist 1. erledigt.

Sei nun \(p-1\) nicht durch 7 teilbar. Nach dem kleinen Fermatschen Satz ist \(a^{p-1} \equiv 1 \bmod p\); außerdem ist \(a^7 \equiv 1 \bmod p\). Nach dem Satz von Bezout gibt es Zahlen \(r\) und \(s\) mit \(7r + (p-1)s = 1\). Dann ist aber \[a = a^1 = a^{ 7r + (p-1)s} = a^{7r} a^{(p-1)s} \equiv 1 \bmod p\]. Aus \(A = 1 + a + a^2 + \ldots + a^6 \equiv 1 + 1 + 1 + \ldots + 1 = 7 \bmod p\) und weil \(p\) ein Teiler von \(A\) ist, muss also \(p = 7\) sein.

Damit ist die Arbeit getan: Falls \(7\) kein Teiler von \(p-1\) ist, ist \(p = 7\); andernfalls ist \(7\) ein Teiler von \(p-1\). Wenn also \(A\) durch eine ungerade Primzahl \(p\) teilbar ist, dann ist entweder \(p = 7\) oder \(p \equiv 1 \bmod 7\).

Mehr Mathematik braucht man nicht, um das RSA-Verfahren zu verstehen - eine der Grundlagen für sichere online-Kommunikation und damit aus der Lebenswelt eines jeden, der online banking benutzt oder mit seinem Handy bezahlt. Aber wer möchte schon bestreiten, dass die Kompetenz des Kästchenzählens wichtiger ist.