erweiterter kl. Fermat

05.10.2004, 01:46	Soap	Auf diesen Beitrag antworten »
erweiterter kl. Fermat Man zeige, dass für $\begin{eqnarray} n=pq \end{eqnarray}$ mit $\begin{eqnarray} p,q\in \mathbb P \end{eqnarray}$ der kleine Fermat in der Form $\begin{eqnarray} a^{\phi(n)+1}\equiv a\mod{n}\ \ \forall a\in \mathbb Z \end{eqnarray}$ ist. Für $\begin{eqnarray} n\|a \end{eqnarray}$ teilt $\begin{eqnarray} n \end{eqnarray}$ auch $\begin{eqnarray} a^{\phi(n)} \end{eqnarray}$ und es gilt die Behauptung, aber sonst? Zwei Fälle müssen wohl betrachtet werden: a) OBdA $\begin{eqnarray} p \end{eqnarray}$ teilt $\begin{eqnarray} a \end{eqnarray}$ und $\begin{eqnarray} q \end{eqnarray}$ teilt nicht $\begin{eqnarray} a \end{eqnarray}$ . b) Weder $\begin{eqnarray} p \end{eqnarray}$ noch $\begin{eqnarray} q \end{eqnarray}$ teilen $\begin{eqnarray} a \end{eqnarray}$ .
05.10.2004, 15:22	eule	Auf diesen Beitrag antworten »
RE: erweiterter kl. Fermat b) geht mit dem Satz von Euler. Findest du mit Beweis auf Seit 71 in: http://random.mat.sbg.ac.at/ %7Epeter/students/unterlagen/zth_skriptum15.pdf
06.10.2004, 20:07	Frak Furt	Auf diesen Beitrag antworten »
Ja, du kannst den b-Teil mit dem Satz von Euler erschlagen. Du kannst aber auch alle drei Fälle gemeinsam erledigen, wenn du den Chinesischen Restsatz verwendest. (Sofern du ihn bereits verwenden darfst.) Dazu zeigst du, dass die Kongruenzen $\begin{eqnarray} a^{\phi(n)+1}\equiv a \pmod p \end{eqnarray}$ $\begin{eqnarray} a^{\phi(n)+1}\equiv a \pmod q \end{eqnarray}$ gelten. Diese wiederum gelten, weil folgende Folgerung aus dem kleinen Fermatschen Satz für beliebige ganze a, natürliche Zahlen k>=1 und Primzahlen r gilt: $\begin{eqnarray} a^{k(r-1)+1}\equiv a \pmod r \end{eqnarray}$ Das zeigt man wiederum durch Fallunterscheidung, je nachdem, ob a teilerfremd zu r ist oder nicht. So, das war jetzt der Fahrplan rückwärts. g Und den Satz von Euler bräuchtest du dafür gar nicht, nur den von Fermat.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »