Fermat

30.12.2007, 20:37

Bjoern1982

Fermat

Hallo

Ich komme im Moment nicht auf Lösung zu folgender Frage:

Warum gilt für gerades $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ mit $\begin{eqnarray*} ggT(\varphi(n),n-1)=1 \end{eqnarray*}$ (Phi-Funktion=Eulerfunktion) die Äquivalenz $\begin{eqnarray*} a^{n-1}\not\equiv 1 \ mod \ n \end{eqnarray*}$ für alle $\begin{eqnarray*} 1<a\leq n-1 \end{eqnarray*}$ ?

Meine Gedanken bis jetzt:

1) der Exponent n-1 ist immer ungerade und zusammengesetzt, n ist nicht prim

2) Es muss $\begin{eqnarray*} a^{n-1} \neq k \cdot n+1 \end{eqnarray*}$ gelten

3) Fall n eine Primzahl ist gilt ja gerade $\begin{eqnarray*} a^{n-1} \equiv 1 \ mod \ n \end{eqnarray*}$ , fragt sich was für zusammengesetzte, ungerade n oder für gerade n gilt...

Hatte auch schon an eine Begründung durch Widerspruch gedacht...komme da aber auch nicht weiter verwirrt

Wäre schön wenn mir jemand helfen könnte smile

Gruß Björn

30.12.2007, 20:55

Auf diesen Beitrag antworten »

RE: Fermat

Zitat:

Original von Bjoern1982
1) der Exponent n-1 ist immer ungerade und zusammengesetzt

Ungerade ja, aber wieso zusammengesetzt? verwirrt

-------------------------------------

Bei diesem Problem hilft ein indirekter Beweis: Angenommen, es gibt doch ein $\begin{eqnarray*} a \end{eqnarray*}$ mit $\begin{eqnarray*} 1<a\leq n-1 \end{eqnarray*}$ und $\begin{eqnarray*} a^{n-1}\equiv 1\mod n \end{eqnarray*}$ .

Das kann allenfalls für $\begin{eqnarray*} \operatorname{ggT}(a,n)=1 \end{eqnarray*}$ passieren, denn im Fall $\begin{eqnarray*} \operatorname{ggT}(a,n)=:t > 1 \end{eqnarray*}$ gilt ja $\begin{eqnarray*} t|a^{n-1} \end{eqnarray*}$ und damit automatisch auch $\begin{eqnarray*} a^{n-1}\not\equiv 1\mod n \end{eqnarray*}$ . Gemäß Fermat-Euler gilt für $\begin{eqnarray*} a \end{eqnarray*}$ mit $\begin{eqnarray*} \operatorname{ggT}(a,n)=1 \end{eqnarray*}$ aber auch $\begin{eqnarray*} a^{\varphi(n)}\equiv 1\mod n \end{eqnarray*}$ . Also für beliebige ganze Zahlen $\begin{eqnarray*} u,v \end{eqnarray*}$

$\begin{eqnarray*} a^{u(n-1)+v\varphi(n)} = \left(a^{n-1}\right)^u \cdot \left(a^{\varphi(n)}\right)^v \equiv 1^u\cdot 1^v = 1\mod n \end{eqnarray*}$ .

Und dann hast du ja noch die Voraussetzung $\begin{eqnarray*} \operatorname{ggT}(\varphi(n),n-1)=1 \end{eqnarray*}$ , die sollte man jetzt noch vorteilhaft einsetzen können - Stichwort EEA ... smile

Neue Frage »

Antworten »

Fermat

Verwandte Themen