Satz von Wilson < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:01 Mi 18.06.2008 | | Autor: | grenife |
| Aufgabe | Beweisen Sie: Genügt die Zahl [mm] $n\in\mathbb{N}$, [/mm] $n>1$ der Kongruenz
[mm] $(n-1)!+1\equiv [/mm] 0(n)$,
so ist $n$ eine Primzahl. |
Hallo zusammen,
wäre sehr dankbar, wenn jemand meinen Beweis überprüfen könnte. Mir scheint die Aufgabe zu leicht zu sein, bzw. mein Beweis klappt zu gut, so dass ich mal annehme, dass ich etwas übersehen habe.
Wegen $n>1$ gilt [mm] $1\equiv [/mm] 1(n)$ und laut Voraussetzung [mm] $(n-1)!+1\equiv [/mm] 0(n)$. Mit den Rechenregeln für Kongruenzen kann ich die erste Kongruenz von der zweiten abziehen und es folgt:
[mm] $(n-1)!+1-1\equiv 0-1(n)\Leftrightarrow (n-1)!\equiv [/mm] -1(n)$. Mit dem Satz von Wilson folgt nun, dass $n$ eine Primzahl ist.
Vielen Dank für Eure Hilfe und viele Grüße
Gregor
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:18 Mi 18.06.2008 | | Autor: | Kyrill |
Hallo,
ja, ich denke du hast recht du hast es dir zu etwas zu einfach gemacht. Denn eigentlich hast du nichts bewiesen.
Denn das was du zeigen sollst, ist der Satz von Wilson
> [mm](n-1)!+1\equiv 0(n)[/mm],
> so ist [mm]n[/mm] eine Primzahl.
Das ist eine äquivalente beziehung, dass heißt du muss 2 Richtungen zeigen:
1. " [mm] \rightarrow [/mm] " Wenn [mm] (n-1)!+1\equiv [/mm] (n) [mm] \richtarrow [/mm] n ist Primzahl
und
2. [mm] "\leftarrow " Wenn n Primzahl \rightarrow (n-1)!+1\equiv [/mm] (n)
Gruß
Kyrill
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:40 Mi 18.06.2008 | | Autor: | grenife |
Hi,
gut, ich bin davon ausgegangen, dass ich den Satz von Wilson ohne Beweis verwenden kann. Die Zusammenfassung mit [mm] $1\equiv [/mm] 1(n)$ ist aber richtig oder?
Viele Grüße
Gregor
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:45 Mi 18.06.2008 | | Autor: | Kyrill |
Hi
> gut, ich bin davon ausgegangen, dass ich den Satz von
> Wilson ohne Beweis verwenden kann.
Hattet ihr denn den Satz von Wilson schon in eurer Vorlesung? Und habt ihr ihn da schon bewiesen?
> Die Zusammenfassung mit
> [mm]1\equiv 1(n)[/mm] ist aber richtig oder?
Ja, das darfst du schreiben.
Gruß
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:58 Mi 18.06.2008 | | Autor: | grenife |
Hi,
diese Richtung des Satzes noch nicht, die wurde ohne Beweis erwähnt.
Es gelte also
[mm] $(n-1)!\equiv [/mm] -1 (n)$.
Angenommen $n$ sei keine Primzahl. Dann besitzt $n$ eine Faktorisierung [mm] $n=s\cdot [/mm] t$, mit natürlichen Zahlen $s$ und $t$ (o.B.d.A. sei [mm] $s\leq [/mm] t$ angenommen) die zwischen $n$ und $1$ liegen, für die also $1<s,t<n$ gilt. Dann ist aber [mm] $(n-1)!=1\cdot 2\cdot \ldots \cdot [/mm] s [mm] \cdot \ldots \cdot [/mm] t [mm] \cdot\ldots \cdot [/mm] (n-1)$ durch $n$ teilbar. Folglich kann $(n-1)!+1$ nicht durch $n$ teilbar sein. Widerspruch.
Viele Grüße
Gregor
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:18 Mi 18.06.2008 | | Autor: | Kyrill |
Hi,
jetzt habe ich mal eine Frage.
Wie habt ihr denn den Satz von Wilson kennen gelernt?
Das würde mich jetzt schon interessieren. Bevor ich dich hier noch weiter in was hineinreite.
Gruß
P.S. So geht deine Lösung aber denke ich in Ordnung!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:33 Mi 18.06.2008 | | Autor: | Kyrill |
Hi,
ja meiner Meinung nach kannst du das dann so schreiben!
Gruß
Kyrill
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:01 Mi 18.06.2008 | | Autor: | felixf |
Hallo Gregor
> Es gelte also
>
> [mm](n-1)!\equiv -1 (n)[/mm].
>
> Angenommen [mm]n[/mm] sei keine Primzahl. Dann besitzt [mm]n[/mm] eine
> Faktorisierung [mm]n=s\cdot t[/mm], mit natürlichen Zahlen [mm]s[/mm] und [mm]t[/mm]
> (o.B.d.A. sei [mm]s\leq t[/mm] angenommen) die zwischen [mm]n[/mm] und [mm]1[/mm]
> liegen, für die also [mm]1
> [mm](n-1)!=1\cdot 2\cdot \ldots \cdot s \cdot \ldots \cdot t \cdot\ldots \cdot (n-1)[/mm]
> durch [mm]n[/mm] teilbar. Folglich kann [mm](n-1)!+1[/mm] nicht durch [mm]n[/mm]
> teilbar sein. Widerspruch.
Vorsicht, dies klappt nicht ganz. Es kann naemlich sein, dass $s = t$ ist. In dem Fall funktioniert das Argument zwar meistens trotzdem, aber z.B. nicht fuer $n = 4$! Es ist naemlich $(n - 1)! = 2 [mm] \cdot [/mm] 3$ nicht durch 4 teilbar.
Aber es reicht ja schon, einen Primfaktor von $n$ zu nehmen, sagen wir mal $p$. Wenn $n$ nicht prim ist, dann ist ja $p < n$, und es gilt $p [mm] \mid [/mm] (n - 1)!$ und somit teilt $p$ nicht $(n - 1)! + 1$. Und damit...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:53 Mi 18.06.2008 | | Autor: | grenife |
Hallo Felix,
hier der neue Versuch:
Die Zahl $n$ sei nicht prim. Dann besitzt $n$ einen Teiler $d$, der zwischen $1$ und $n$ liegt und der $(n-1)!$ teilt. Demnach kann $d$ nicht $(n-1)!+1$ teilen. Laut der Voraussetzung gilt jedoch [mm] $(n-1)!+1\equiv [/mm] 0(n)$, also dass $(n-1)!+1$ durch $n$ teilbar ist. Dann wäre jedoch $(n-1)!+1$ auch durch jeden Primfaktor von $n$, also insbesondere durch $d$ teilbar. Widerspruch.
So besser?
Viele Grüße
Gregor
> Hallo Gregor
>
> > Es gelte also
> >
> > [mm](n-1)!\equiv -1 (n)[/mm].
> >
> > Angenommen [mm]n[/mm] sei keine Primzahl. Dann besitzt [mm]n[/mm] eine
> > Faktorisierung [mm]n=s\cdot t[/mm], mit natürlichen Zahlen [mm]s[/mm] und [mm]t[/mm]
> > (o.B.d.A. sei [mm]s\leq t[/mm] angenommen) die zwischen [mm]n[/mm] und [mm]1[/mm]
> > liegen, für die also [mm]1
> > [mm](n-1)!=1\cdot 2\cdot \ldots \cdot s \cdot \ldots \cdot t \cdot\ldots \cdot (n-1)[/mm]
> > durch [mm]n[/mm] teilbar. Folglich kann [mm](n-1)!+1[/mm] nicht durch [mm]n[/mm]
> > teilbar sein. Widerspruch.
>
> Vorsicht, dies klappt nicht ganz. Es kann naemlich sein,
> dass [mm]s = t[/mm] ist. In dem Fall funktioniert das Argument zwar
> meistens trotzdem, aber z.B. nicht fuer [mm]n = 4[/mm]! Es ist
> naemlich [mm](n - 1)! = 2 \cdot 3[/mm] nicht durch 4 teilbar.
>
> Aber es reicht ja schon, einen Primfaktor von [mm]n[/mm] zu nehmen,
> sagen wir mal [mm]p[/mm]. Wenn [mm]n[/mm] nicht prim ist, dann ist ja [mm]p < n[/mm],
> und es gilt [mm]p \mid (n - 1)![/mm] und somit teilt [mm]p[/mm] nicht [mm](n - 1)! + 1[/mm].
> Und damit...
>
> LG Felix
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:20 Do 19.06.2008 | | Autor: | felixf |
Hallo Gregor,
> Die Zahl [mm]n[/mm] sei nicht prim. Dann besitzt [mm]n[/mm] einen Teiler [mm]d[/mm],
> der zwischen [mm]1[/mm] und [mm]n[/mm] liegt und der [mm](n-1)![/mm] teilt. Demnach
hier meinst du, dass $d$ echt zwischen $1$ und $n$ liegt, also dass $1 < d < n$ gilt. Fuer $d = 1$ oder $d = n$ ist's witzlos :)
> kann [mm]d[/mm] nicht [mm](n-1)!+1[/mm] teilen. Laut der Voraussetzung gilt
> jedoch [mm](n-1)!+1\equiv 0(n)[/mm], also dass [mm](n-1)!+1[/mm] durch [mm]n[/mm]
> teilbar ist. Dann wäre jedoch [mm](n-1)!+1[/mm] auch durch jeden
> Primfaktor von [mm]n[/mm], also insbesondere durch [mm]d[/mm] teilbar.
Hier meinst du nicht Primfaktor, sondern einfach nur Faktor (du hast oben nicht vorausgesetzt, dass $d$ ein Primfaktor ist).
> So besser?
Abgesehen von den beiden Details ja :)
LG Felix
|
|
|
|
