Starke Pseudoprimzahlen

06.11.2006, 20:21	homburger	Auf diesen Beitrag antworten »
Starke Pseudoprimzahlen Hallo. Ich folgenden Internetartikel gefunden und verstehe einen Teil nicht. http://matheplanet.com/default3.html?cal...rt%3D0%26sa%3DN Da steht: Die obige Defintion einer starken Pseudoprimzahl (siehe ref(1.1)) folgt eigentlich direkt aus dem kleinen Fermat: $\begin{eqnarray} a^{n-1}=1 \mod\ n \Longleftrightarrow a^{n-1}-1=0 \mod\ n \end{eqnarray}$ Da $\begin{eqnarray} n \end{eqnarray}$ ungerade ist, kann man $\begin{eqnarray} n-1 \end{eqnarray}$ als $\begin{eqnarray} 2b \end{eqnarray}$ darstellen. $\begin{eqnarray} a^{2b}-1=(a^{b}-1)(a^{b}+1)=0 \mod\ n \end{eqnarray}$ Wobei nicht beide Faktoren gleich 0 sein können, denn sonst würde die Differenz $\begin{eqnarray} (a^{b}+1)-(a^{b}-1)=2 \end{eqnarray}$ von $\begin{eqnarray} n \end{eqnarray}$ geteilt werden, was ein Widerspruch zu $\begin{eqnarray} n \end{eqnarray}$ ungerade ist. Der erste Faktor kann nach dem selben Prinzip aufgespalten werden, wenn $\begin{eqnarray} b \end{eqnarray}$ gerade ist, so dass man am Ende eine Aufspaltung in dieser Form erhält: mit $\begin{eqnarray} r=1 \mod\ 2 \end{eqnarray}$ Hier wird der erste Faktor 0, wenn $\begin{eqnarray} a^{r}=1 \mod\ n \end{eqnarray}$ gilt. Die andern werden 0, wenn $\begin{eqnarray} a^{2^{t}r}=-1 \mod\ n \end{eqnarray}$ gilt mit $\begin{eqnarray} 0\leq t<s \end{eqnarray}$ . Meine Frage nun: Es wird doch hier im Ring $\begin{eqnarray} \mathbb{Z}/ n\mathbb{Z} \end{eqnarray*}$ gerechnet, oder? Dieser ist aber doch nur für n Primzahl Nullteilerfrei, weil dann ein Körper. Kann in dem Produkt nicht sein, dass 2 der Faktoren Nullteiler sind? Dann kann ich doch aber die Bedingungen nicht daraus folgern, oder? gruß, homburger
07.11.2006, 15:48	AD	Auf diesen Beitrag antworten »
Da hast du vollkommen recht. Und wenn du dir den Artikel nochmal sorgfältig durchliest, wird das nämlich auch in den Unterschieden der Definition von "Pseudoprimzahl" und "starke Pseudoprimzahl" berücksichtigt: Jedes starke Pseudoprimzahl ist auch eine Pseudoprimzahl, aber die Umkehrung gilt nicht - eben weil $\begin{eqnarray} \mathbb{Z}/(n\mathbb{Z}) \end{eqnarray}$ für Nichtprimzahlen $\begin{eqnarray} n \end{eqnarray}$ nicht nullteilerfrei ist.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »