Kleiner Satz von Fermat

01.04.2007, 22:52

josef

Kleiner Satz von Fermat

hallo forum,

hat jemand eine verständliche herleitung für den kleinen fermat. also eine herleitung, damit es einleuchtet wird, dass der fermat für primzahlen stimmt.

der fermat will nicht so richtig in den kopf.

danke und gruß,
josef krueger

01.04.2007, 23:13

bil

Auf diesen Beitrag antworten »

hi..
ich hab mir jetzt den beweis nicht genauer angeschaut deshalb weiss ich nicht wie verständlich er ist. aber vll hilft er ja...
http://de.wikibooks.org/wiki/ Beweisarch...n_Fe<br /> rmat

gruss bil

01.04.2007, 23:31

josef

Auf diesen Beitrag antworten »

vielleicht habe ich mich zu undeutlich ausgedrückt.

ich brauche keinen mathematischen beweis. ich hätte gerne eine einfach erklärung, die es glaubhaft macht, dass dieser satz korrekt ist

vielleicht ist das jedoch beim fermat gar nicht so einfach möglich, sonst wäre er wohl nicht so berühmt geworden wenn er direkt ersichtlich ist.

gruß,
josef

02.04.2007, 02:14

Lazarus

Auf diesen Beitrag antworten »

Mal schauen wie wir das veranschaulichen können...
Kennst du den Binomischen Lehrsatz ?

$\begin{eqnarray*} \left(a+b\right)^p=\sum_{i=0}^p~{n\choose i}~ a^p ~ b^{p-i} \end{eqnarray*}$

[edit: Das " $\begin{eqnarray*} n \end{eqnarray*}$ " im den Binomialkoeffizient müsste " $\begin{eqnarray*} p \end{eqnarray*}$ " heissen.]

Betrachtet man das ganze $\begin{eqnarray*} \mod p \end{eqnarray*}$ fällt sofort auf das wg den Binomialkoeffizienten alle Summenglieder "innendrinn" wegfallen und nurnoch die Kongruenz $\begin{eqnarray*} \left(a+b\right)^p \equiv a^p+b^p \mod p \end{eqnarray*}$ übirgbleibt. Mit $\begin{eqnarray*} b=1 \end{eqnarray*}$ ergibt sich $\begin{eqnarray*} \left(a+1\right)^p \equiv a^p+1 \mod p \end{eqnarray*}$ . Das liefert nun den Ansatz für ne Induktion mit dem man das beweisen könnte, das daraus dann im weiteren $\begin{eqnarray*} x^p\equiv x \mod p \end{eqnarray*}$ folgt. Geteilt durch $\begin{eqnarray*} x \end{eqnarray*}$ ergibt sich dann eben das $\begin{eqnarray*} x^{p-1}\equiv 1 \mod p \end{eqnarray*}$ .

02.04.2007, 09:08

Auf diesen Beitrag antworten »

Zitat:

Original von josef
ich brauche keinen mathematischen beweis. ich hätte gerne eine einfach erklärung, die es glaubhaft macht, dass dieser satz korrekt ist

Du scheinst zu glauben, dass Beweise unnötig künstlich lang gemacht werden, damit viele sie nicht verstehen. Kann sein, dass manche so vorgehen - in der Regel allerdings nicht!

Und der Beweis vom kleinen Fermat ist ja auch wirklich sehr kurz, selbst wenn man nur wenig Grundkenntnisse in Modulo-Rechnung hat.

02.04.2007, 11:19

Tobias

Auf diesen Beitrag antworten »

Kleiner Hinweis: Der Binomialkoeffizient bei Lazarus ist natürlich nicht "n über i" sondern "p über i".

02.04.2007, 12:23

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von josef
ich brauche keinen mathematischen beweis. ich hätte gerne eine einfach erklärung, die es glaubhaft macht, dass dieser satz korrekt ist

Genau das ist aber ein Beweis.

02.04.2007, 15:05

Lazarus

Auf diesen Beitrag antworten »

Zitat:

Original von Tobias
Kleiner Hinweis: Der Binomialkoeffizient bei Lazarus ist natürlich nicht "n über i" sondern "p über i".

Ja, Tippfehler. Ich lass es aber mal stehn und edditier nur einen Hinweis rein.

02.04.2007, 16:36

Auf diesen Beitrag antworten »

Ich liefere mal noch den Beweis, den ich dazu kenne: Wir betrachten alle $\begin{eqnarray*} (p-1) \end{eqnarray*}$ Reste modulo $\begin{eqnarray*} p \end{eqnarray*}$ außer 0:

$\begin{eqnarray*} 1, 2, \ldots, (p-1)\qquad (*) \end{eqnarray*}$

deren Produkt sei $\begin{eqnarray*} u \end{eqnarray*}$ genannt. Jetzt multiplizieren wir jeden dieser Reste mit einer nicht durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbaren Zahl $\begin{eqnarray*} a \end{eqnarray*}$ :

$\begin{eqnarray*} 1a, 2a, \ldots, (p-1)a\qquad (**) \end{eqnarray*}$

diesmal mit Produkt $\begin{eqnarray*} v \end{eqnarray*}$ , offenbar ist $\begin{eqnarray*} v=u\cdot a^{p-1} \end{eqnarray*}$ . Die Werte in (**) entsprechen modulo $\begin{eqnarray*} p \end{eqnarray*}$ gerade wieder den Resten $\begin{eqnarray*} 1,\ldots,p-1 \end{eqnarray*}$ , also jeder Rest taucht wieder genau einmal auf, nur hier in anderer Reihenfolge als in (*) - die Begründung dafür überlege man sich bitte selbst. Augenzwinkern

Also gilt für das Produkt $\begin{eqnarray*} u\equiv v\mod p \end{eqnarray*}$ , was dann unmittelbar zu $\begin{eqnarray*} a^{p-1}\equiv 1\mod p \end{eqnarray*}$ führt.

P.S.: Dieser Beweis lässt sich ohne Probleme auch auf den Satz von Fermat-Euler $\begin{eqnarray*} a^{\varphi(m)} \equiv 1\mod m \end{eqnarray*}$ übertragen - dort betrachtet man halt das Produkt der $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ teilerfremden Restklassen.

Neue Frage »

Antworten »

Kleiner Satz von Fermat

Verwandte Themen