Antwort mit KI erzeugt
AKS-Primalitätstestskriterium basiert auf \((X + a)^n \equiv X^n + a \mod n \Leftrightarrow n \) ist prim
Um zu zeigen, dass wenn \(n\) nicht prim ist, die Kongruenz \((X + a)^n \not\equiv X^n + a \mod n\) gilt, können wir allgemeine Eigenschaften von Primzahlen und den binomischen Lehrsatz verwenden.
Zunächst erinnern wir uns an den binomischen Lehrsatz, der besagt:
\(
(X + a)^n = \sum_{k=0}^{n} \binom{n}{k} X^{n-k} a^k
\)
Wenn \(n\) eine Primzahl ist, dann wissen wir durch den kleinen Satz von Fermat, dass für jedes \(a\) nicht durch \(n\) teilbar:
\(
a^n \equiv a \mod n
\)
Auch ist in dem Fall von \(n\) prim jede der Binomialkoeffizienten \(\binom{n}{k}\) für \(0 < k < n\) durch \(n\) teilbar, weil \(n\) im Zähler der Definition von \(\binom{n}{k}\) steht und \(n\) eine Primzahl ist (also keine Zahlen außer 1 und \(n\) selber \(n\) teilen). Das bedeutet, dass alle Terme \(\binom{n}{k} X^{n-k} a^k\) für \(0 < k < n\) ein Vielfaches von \(n\) sind und somit modulo \(n\) gleich 0 werden. Diese Tatsache lässt \((X + a)^n \) reduziert auf \(X^n + a\) modulo \(n\).
Doch wenn \(n\) nicht prim ist, scheitert diese Argumentation:
1.
Binomialkoeffizienten: Nicht alle Binomialkoeffizienten \(\binom{n}{k}\) für \(0 < k < n\) müssen durch \(n\) teilbar sein, wenn \(n\) nicht prim ist. Dies bedeutet, dass einige Terme \(\binom{n}{k} X^{n-k} a^k\) nicht modulo \(n\) gleich 0 sind, und somit tragen diese Terme zu dem Ergebnis von \((X + a)^n \mod n\) bei.
2.
Fall \(n\) zusammengesetzt: Für zusammengesetztes \(n\), können Fälle auftreten, wo \(a^n \not\equiv a \mod n\) für einige \(a\), was bedeutet, dass die Kongruenz \((X + a)^n \equiv X^n + a \mod n\) verletzt wird, da die Struktur von \((X + a)^n\) und \(X^n + a\) nicht gleich behandelt werden kann im Kontext der Modulararithmetik mit einem nicht-primen Modulus \(n\).
Um die Behauptung zu zeigen, betrachten wir ein spezifisches Beispiel, bei dem \(n\) nicht prim ist. Nehmen wir \(n = pq\) für zwei Primzahlen \(p\) und \(q\) und ein \(a\), das teilerfremd zu \(n\) ist. Ohne Verlust der Allgemeinheit könnte bei einigen \(a\) und bestimmten Werten von \(X\) die Kongruenz \((X + a)^n \equiv X^n + a \mod n\) verletzt sein, weil die Verteilung der Faktoren und Binomialkoeffizienten in \((X + a)^n\) nicht mehr sauber durch \(n\) kürzbar sind, um es auf die Form \(X^n + a\) zu bringen.
Dies verdeutlicht, warum die Originalaussage \((X + a)^n \equiv X^n + a \mod n \Leftrightarrow n\) ist prim eine notwendige und hinreichende Bedingung darstellt, da ihre Umkehrung das Versagen dieser sauberen Reduktion aufzeigt, wenn \(n\) nicht prim ist.
