Fermatscher Primzahltest auf 561

Question

Aufgabe:

Ich soll mithilfe von Fermat zeigen, dass 561 keine Prinzahl ist.

Problem/Ansatz:

Ich muss also eine Zahl a finden, so dass gilt: a^560 mod 561 != 1

Aber wie finde ich diese Zahl und Vorallem wie rechne ich das dann aus.

Answer 1

561 ist die kleinste Carmichel-Zahl, also eine Zahl, die den Fermat-Test zu jeder zu 561 teilerfremden Basis besteht, aber dennoch nicht prim ist. 561=3·11·17

Comments

Also muss ich für mein a 3, 7 oder 17 wählen?

---

genau so ist es.

Answer 2

Hallo wecker,

und vor allem wie rechne ich das dann aus.

Betrachte den Term \(x \cdot b^n\). In Abhängigkeit davon, ob \(n\) eine gerade oder ungerade Zahl ist, kann man dafür schreiben: $$x \cdot b^n = \left\{ \begin{array}{ll} n \equiv 0 \mod 2 & \to x \cdot (b^2)^{n/2}\\ n \equiv 1 \mod 2 & \to xb \cdot (b^2)^{\lfloor n/2 \rfloor}\end{array}\right.$$ Wichtig - der Wert des Terms ändert sich dadurch nicht! Ich starte mit \(1 \cdot 3^{560}\) und schreibe es in eine Tabelle. Dabei schreibe ich nach einer Multiplikation \(x \cdot b\) oder \(b^2\) nur noch den Rest nach der Division durch 561 hin: $$\begin{array}{ccc} x & b & n & \mod 561 \\ \hline 1 & 3 & 560 \\ 1 & 9 & 280 \\ 1 & 81 & 140 \\ 1 & 390 & 70 \\ 1 & 69 & 35 \\ 69&273& 17 \\ 324&477& 8\\ 324&324& 4 \\ 324&69& 2 \\ 324& 273& 1 \\ 375&477& 0\end{array}$$ in der letzten Zeile steht nun $$\dots \equiv 375 \cdot 477^0 \mod 561 $$ und dies ist 375 und ungleich 1. Zur Kontrolle frage Wolfram Alpha.

Gruß Werner