Kleiner Fermat

11.11.2008, 01:43

Bjoern1982

Kleiner Fermat

Hallo,

wie zeige ich mit dem kleinen Fermat, dass n²+1 mit n aus IN niemals ein Vielfaches von 11 ist ?

Ich hätte es darüber gezeigt, dass falls n²+1 ein Vielfaches k von 11 sein würde, folgendes gelten müsste:

$\begin{eqnarray*} n^2 \equiv 10\ mod\ 11 \end{eqnarray*}$

Da aber $\begin{eqnarray*} 10^{\frac{11-1}{2}}=10^5 \equiv -1\ mod\ 11 \not\equiv 1\ mod\ 11 \end{eqnarray*}$ gilt, ist 10 kein QR modulo 11 und damit muss das Gegenteil gelten, also dass n²+1 niemals ein Vielfaches von 11 ist.

Desweiteren ist noch gefragt was das Besondere an der Zahl 11 ist und ob man diese Idee verallgemeinern kann um zu sagen für welche Primzahlen p gilt, dass n²+1 ein Vielfaches von p ist.

Kann mir jemand helfen ?

Gruß Björn

11.11.2008, 08:31

Auf diesen Beitrag antworten »

Naja, die von dir genutzte Legendresymbol-Berechnung

$\begin{eqnarray*} \left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \mod p \end{eqnarray*}$

geht ja auf den kleinen Fermat zurück, so ist vielleicht der Hinweis zu verstehen. Und die Verallgemeinerung $\begin{eqnarray*} 11 \dashrightarrow p \end{eqnarray*}$ ist doch dann doch naheliegend:

Tausch doch einfach überall die $\begin{eqnarray*} 11 \end{eqnarray*}$ in deiner Rechnung durch $\begin{eqnarray*} p \end{eqnarray*}$ aus (natürlich auch die $\begin{eqnarray*} 10 \end{eqnarray*}$ durch $\begin{eqnarray*} p-1 \end{eqnarray*}$ bzw. gleich $\begin{eqnarray*} -1 \end{eqnarray*}$ ). Am Rechnungsverlauf sollte erkennbar sein, für welche $\begin{eqnarray*} p \end{eqnarray*}$ das klappt, und für welche nicht.

11.11.2008, 18:43

Bjoern1982

Auf diesen Beitrag antworten »

Stimmt, ist ja gar nicht so schwer:

$\begin{eqnarray*} n^2 \equiv -1\ mod\ 11 \end{eqnarray*}$

Auf beiden Seiten "hoch 5"

$\begin{eqnarray*} (n^2)^5=n^{10} \equiv 1\ mod\ 11 \not\equiv (-1)^5=-1\ mod\ 11 \end{eqnarray*}$

--> Widerspruch wegen kleinem Fermat

Allgemein folgt dann wenn man auf beiden Seiten "hoch $\begin{eqnarray*} \frac{p-1}{2} \end{eqnarray*}$ rechnet:

$\begin{eqnarray*} n^{p-1} \equiv -1^{\frac{p-1}{2}}\ mod\ p \end{eqnarray*}$

Und das gilt nur für gerade $\begin{eqnarray*} \frac{p-1}{2} \end{eqnarray*}$
Also genau dann, wenn $\begin{eqnarray*} \frac{p-1}{2}=2r<=>p=4r+1 \end{eqnarray*}$ mit r aus IN

Passt so oder ?

11.11.2008, 18:59

Auf diesen Beitrag antworten »

Das passt. Freude

Ihr seid wohl gerade beim quadratischen Reziprozitätsgesetz, denn das mit den $\begin{eqnarray*} (-1)^{\frac{p-1}{2}} \end{eqnarray*}$ ist ja eines der Ergänzungssätze.

11.11.2008, 19:53

Bjoern1982

Auf diesen Beitrag antworten »

Wunderbar

Zitat:

Ihr seid wohl gerade beim quadratischen Reziprozitätsgesetz, denn das mit den $\begin{eqnarray*} (-1)^{\frac{p-1}{2}} \end{eqnarray*}$ ist ja eines der Ergänzungssätze.

Genau, das war letzten Mittwoch in der Vorlesung dran Augenzwinkern

Neue Frage »

Antworten »

Kleiner Fermat

Verwandte Themen