Carmichael-Zahlen

23.05.2007, 16:50

Shadow86

Carmichael-Zahlen

Es gibt Zahlen, für die gilt:
$\begin{eqnarray*} a^{n} \equiv a mod (n) \end{eqnarray*}$
Diese Zahlen heißen Carmichael-Zahlen.

Nun sollen wir beweisen:
Sind für $\begin{eqnarray*} m \in \mathbb N \end{eqnarray*}$ die Zahlen 6m+1, 12m+1 und 18m+1 Primzahlen so ist $\begin{eqnarray*} n=(6m+1)(12m+1)(18m+1) \end{eqnarray*}$ eine Carmichael-Zahl.

Ich habe erst einmal ausmultipliziert und so $\begin{eqnarray*} n=1296m^3+396m^2+36m+1 \end{eqnarray*}$ erhalten. Das habe ich dann eingesetzt und

$\begin{eqnarray*} a^{1296m^3+396m^2+36m+1} \equiv a mod (1296m^3+396m^2+36m+1) \end{eqnarray*}$ erhalten

$\begin{eqnarray*} =>a^{1296m^3}* a^{396m^2}* a^{36m}* a^{1} \equiv a mod (1296m^3+396m^2+36m+^1) \end{eqnarray*}$

Ich könnte a jetzt rauskürzen, aber dann komme ich trotzdem nicht weiter. Wer kann mir hier weiter helfen? Oder bin ich das ganz falsch angegagen?

23.05.2007, 17:46

tigerbine

Auf diesen Beitrag antworten »

RE: Carmichael-Zahlen
In deiner Definition fehlt etwas. Was ist denn nun eine Carmicheal Zahl:

$\begin{eqnarray*} a,~n,~a^n \end{eqnarray*}$ ?

Carmicheal Zahlen

Ergänze damit doch mal deine Definition.

23.05.2007, 17:52

Auf diesen Beitrag antworten »

Betrachte die Einzelkongruenzen nach den Primzahlmodulen, also

$\begin{eqnarray*} a^n \mod (6m+1) \end{eqnarray*}$
$\begin{eqnarray*} a^n \mod (12m+1) \end{eqnarray*}$
$\begin{eqnarray*} a^n \mod (18m+1) \end{eqnarray*}$

Beim "Vereinfachen" kannst du jeweils den kleinen Satz von Fermat verwenden, und dabei

$\begin{eqnarray*} n-1 = 1296m^3+396m^2+36m = (36m^2+11m+1)\cdot 36m \end{eqnarray*}$

nutzen!!! Zum Schluss alles wieder auf das Produktmodul zurückführen, mit chinesischem Restsatz. Die Anwendung des letzteren ist hier lediglich formal, echt zu rechnen gibt's da nix.

23.05.2007, 18:14

Shadow86

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Betrachte die Einzelkongruenzen nach den Primzahlmodulen, also

$\begin{eqnarray*} a^n \mod (6m+1) \end{eqnarray*}$
$\begin{eqnarray*} a^n \mod (12m+1) \end{eqnarray*}$
$\begin{eqnarray*} a^n \mod (18m+1) \end{eqnarray*}$

Beim "Vereinfachen" kannst du jeweils den kleinen Satz von Fermat verwenden, und dabei

$\begin{eqnarray*} n-1 = 1296m^3+396m^2+36m = (36m^2+11m+1)\cdot 36m \end{eqnarray*}$

nutzen!!! Zum Schluss alles wieder auf das Produktmodul zurückführen, mit chinesischem Restsatz. Die Anwendung des letzteren ist hier lediglich formal, echt zu rechnen gibt's da nix.

Wie soll ich denn bei
$\begin{eqnarray*} a^n \mod (6m+1) \end{eqnarray*}$
$\begin{eqnarray*} a^n \mod (12m+1) \end{eqnarray*}$
$\begin{eqnarray*} a^n \mod (18m+1) \end{eqnarray*}$
chin. Restsatz machen?
Und welches Produktmodul meinst du?

@Tigerbine: Ja, du hast Recht: Ich sollte dazuschreiben, dass ggT(a,n)=1 sein muss, damit die Kongruenz $\begin{eqnarray*} a^{n} \equiv a mod(n) \end{eqnarray*}$ gilt.

23.05.2007, 20:00

Auf diesen Beitrag antworten »

Zitat:

Original von Shadow86
Wie soll ich denn bei
$\begin{eqnarray*} a^n \mod (6m+1) \end{eqnarray*}$
$\begin{eqnarray*} a^n \mod (12m+1) \end{eqnarray*}$
$\begin{eqnarray*} a^n \mod (18m+1) \end{eqnarray*}$
chin. Restsatz machen?
Und welches Produktmodul meinst du?

Mit Produktmodul meine ich schlicht $\begin{eqnarray*} n \end{eqnarray*}$ als Produkt der drei genannten Primzahlen.

Und dann hast du den wichtigsten Satz unterschlagen:

Zitat:

Original von Arthur Dent
Beim "Vereinfachen" kannst du jeweils den kleinen Satz von Fermat verwenden

Vielleicht bringt dich das hier

fermat kongruenz

auf die richtige Spur.

Neue Frage »

Antworten »

Carmichael-Zahlen

Verwandte Themen