ggT(n!+1,(n+1)!+1)=1 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es ein n [mm] \in \IN. [/mm] Zeige:
a) ggT(n!+1,(n+1)!+1)=1
b) [mm] ggT(2^{n^{2}}+1,2^n-1)=1 [/mm] |
Hi,
zum ersten Teil habe ich folgenden Beweis, den ich aber nicht so ganz verstehe.
a)
Angenommen es gibt einen gemeinsamen Primteiler p von n!+1 und (n+1)!+1, dann gilt
n!=pk-1 und
pr=(n+1)!+1=(n+1)n!+1=(pk-1)(n+1)+1=pk(n+1)-n, d.h. n=pk(n+1)-pr, also gilt p|n und somit auch p|n!.
Das aber ergibt zusammen mit p|(n!+1) den Widerspruch p|1
Also. Den Anfang verstehe ich ja noch bis
> Angenommen es gibt einen gemeinsamen Primteiler p von n!+1 und (n+1)!+1, dann gilt n!=pk+1 und
> pr=(n+1)!+1=(n+1)n!+1=pk(n+1)-n, d.h. n=pk(n+1)-pr
aber was dann folgt nicht. Wieso gilt
> p|n und somit auch p|n!.
Also warum folgt aus n=pk(n+1)-pr, das p sowohl n als auch n! teilt?
und warum ergibt
> Das aber ergibt zusammen mit p|(n!+1) den Widerspruch p|1
den Widerspruch, sodass daraus als Lösung folgen muss??
Danke schon mal für Hilfe.
Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:34 Di 10.05.2011 | | Autor: | abakus |
> Es ein n [mm]\in \IN.[/mm] Zeige:
>
> a) ggT(n!+1,(n+1)!+1)=1
>
> b) [mm]ggT(2^{n^{2}}+1,2^n-1)=1[/mm]
> Hi,
>
> zum ersten Teil habe ich folgenden Beweis, den ich aber
> nicht so ganz verstehe.
>
> a)
>
> Angenommen es gibt einen gemeinsamen Primteiler p von n!+1
> und (n+1)!+1, dann gilt
>
> n!=pk-1 und
>
> pr=(n+1)!+1=(n+1)n!+1=(pk-1)(n+1)+1=pk(n+1)-n, d.h.
> n=pk(n+1)-pr, also gilt p|n und somit auch p|n!.
>
> Das aber ergibt zusammen mit p|(n!+1) den Widerspruch p|1
>
>
> Also. Den Anfang verstehe ich ja noch bis
>
> > Angenommen es gibt einen gemeinsamen Primteiler p von n!+1
> und (n+1)!+1, dann gilt n!=pk+1 und
> > pr=(n+1)!+1=(n+1)n!+1=pk(n+1)-n, d.h. n=pk(n+1)-pr
>
>
> aber was dann folgt nicht. Wieso gilt
>
> > p|n und somit auch p|n!.
>
> Also warum folgt aus n=pk(n+1)-pr, das p sowohl n als auch
> n! teilt?
Hallo,
aus n=pk(n+1)-pr folgt durch Ausklammern von p
n=p(k(n+1)-r).
Da sich der Faktor p ausklammern lässt UND der zweite Faktor k(n+1)-r offensichtlich eine ganze Zahl ist...
Ich persönlich würde den Beweis aber lieber über den Euklidischen Algorithmus führen.
Gruß Abakus
>
> und warum ergibt
>
> > Das aber ergibt zusammen mit p|(n!+1) den Widerspruch p|1
>
>
> den Widerspruch, sodass daraus als Lösung folgen muss??
>
>
> Danke schon mal für Hilfe.
>
> Grüße
|
|
|
| |
|
Hi,
ja mit dem E.A. wollte ich es auch probieren. Nur ich habe dann diesen Beweis gesehen, habe ihn aber nicht ganz verstanden.
Ok, dann haben wir n=p(k(n+1)-r) und somit teilt p die Zahl n. Und weil es n teilt, teilt es automatisch auch n!, richtig??
Wo steckt aber jetzt mit p|(n!+1) und p|1 der Widerspruch?
|
|
|
| |
|
Hallo steve.joke,
vielleicht steckst Du zu tief in Formeln vergraben. Es ist doch recht offensichtlich...
> Ok, dann haben wir n=p(k(n+1)-r) und somit teilt p die Zahl
> n. Und weil es n teilt, teilt es automatisch auch n!,
> richtig??
Genau. ![[ok]](/images/smileys/ok.gif "[ok]")
> Wo steckt aber jetzt mit p|(n!+1) und p|1 der Widerspruch?
Sei t=n!
Für alle t ist ggT(t,t+1)=1
Daher folgt [mm]p|t\ \wedge\ p|t+1\ \Rightarrow p|1[/mm]
Das ist auch schon alles. 
Grüße
reverend
|
|
|
| |
|
hi nochmal,
Daher folgt $ p|t\ [mm] \wedge\ [/mm] p|t+1\ [mm] \Rightarrow [/mm] p|1 $
Also aus p|1 folgt dass dass p=1 sein muss, oder???
Aber das ist doch dann eigentlich gar kein Widerspruch oder? Ich habe so vielmehr p=1 bestimmt???
|
|
|
| |
|
Hallo nochmal,
>> Daher folgt [mm]p|t\ \wedge\ p|t+1\ \Rightarrow p|1[/mm]
>
> Also aus p|1 folgt dass dass p=1 sein muss, oder???
>
> Aber das ist doch dann eigentlich gar kein Widerspruch
> oder? Ich habe so vielmehr p=1 bestimmt???
Ja, schon. Aber die Voraussetzung war:
"Angenommen es gibt einen gemeinsamen Primteiler p von n!+1 und (n+1)!+1"
Aufgrund dieser Voraussetzung hast Du also festgestellt, dass p=1 sein muss. Und 1 ist kein Primteiler. Widerspruch.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:39 Di 10.05.2011 | | Autor: | steve.joke |
ok, danke dir erstmal.
mit b) und dem E.A. befassen wir uns mal morgen .
Grüße
|
|
|
| |
|
Hi,
also ich habe versucht die a) auch nochmal mit dem E.A. zu lösen, so ganz klappt es aber nicht.
> a) ggT(n!+1,(n+1)!+1)=1
Ich fange so an: ggT(n!+1,(n+1)!+1)=ggT((n+1)!+1,n!+1)
[mm] (n+1)!+1=(n+1)\*n!+1=n!n+n!+1 [/mm] So jetzt mit dem E.A
n!n+n!+1 [mm] =(n!+1)\*(n+1)-n
[/mm]
(n!+1)=-n...
Da komme ich jetzt auch schon nicht weiter... Könnt ihr mir da vielleicht weiterhelfen??
Und habt ihr vielleicht paar Tipps für die b)??
Grüße
|
|
|
| |
|
Hallo nochmal,
> also ich habe versucht die a) auch nochmal mit dem E.A. zu
> lösen, so ganz klappt es aber nicht.
>
> > a) ggT(n!+1,(n+1)!+1)=1
>
> Ich fange so an: ggT(n!+1,(n+1)!+1)=ggT((n+1)!+1,n!+1)
>
> [mm](n+1)!+1=(n+1)\*n!+1=n!n+n!+1[/mm] So jetzt mit dem E.A
>
> n!n+n!+1 [mm]=(n!+1)\*(n+1)-n[/mm]
> (n!+1)=-n...
Bis hierhin ok, wenn Dir klar ist, dass und warum der E.A. auch mit negativem Rest funktioniert.
Dies hier ist allerdings die Stelle, wo man eigentlich schon aufhören kann. Du hast bis hier nämlich gezeigt:
ggT(n!+1,(n+1)!+1)=ggT(n!+1,-n)=ggT(n!+1,n)
...und letzterer ist offensichtlich.
Wenn nicht, geht der E.A. (nach Vorzeichenumkehr) so weiter:
n!+1=n*(n-1)!+1
[mm] n=\blue{1}*n+0
[/mm]
Da leuchtet einem ja schnell die blaue 1 entgegen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:23 Mi 11.05.2011 | | Autor: | steve.joke |
stimmt.
danke dir.
grüße
|
|
|
| |
|
Hallo nochmal,
> Es ein n [mm]\in \IN.[/mm] Zeige:
>
> a) ggT(n!+1,(n+1)!+1)=1
>
> b) [mm]ggT(2^{n^{2}}+1,2^n-1)=1[/mm]
Bei Aufgabe b) zeige
[mm] 2^{n-1}(2^{n^2}+1)\equiv 1\mod{(2^n-1)}
[/mm]
Grüße
reverend
|
|
|
| |
|
Hi,
also ich glaube bei b) mit Kongruenzen haben wir noch gar nichts gemacht.
Eigentlich sollen wir auch beide Aufgaben mit dem E.A. lösen, nur wie gesagt, bei der a) hatte ich diesen Beweis dort gesehen und wollte ihn verstehen.
Über den E.A. habe ich die a) ja auch noch nicht hinbekommen....
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:49 Mi 11.05.2011 | | Autor: | reverend |
Hallo nochmal,
der gleiche Ansatz geht natürlich auch ohne Kongruenzen...
Mit dem Euklidischen Algorithmus sieht das dagegen eher mühsam aus.
Dürft Ihr denn wenigstens das ![[]](/images/popup.gif) Lemma von Bézout verwenden?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:55 Mi 11.05.2011 | | Autor: | steve.joke |
Ja,
dieses Lemma kennen wir auch.
Grüße
|
|
|
| |
|
Hallo steve.joke,
na dann hier mal ein Lösungsweg mit dem Lemma von Bézout.
Behauptung: [mm] \exists a\in\IN, [/mm] so dass [mm] 2^{n-1}\blue{(2^{n^2}+1)}-a*\blue{(2^{n-1}-1)}=1 [/mm] (woraus die Behauptung aus der Aufgabe folgt)
Nun kannst Du ja mal sehen, wie Du das a bestimmst. Das ist eigentlich ziemlich einfach, mit wenigen Umformungen.
Man müsste vielleicht noch wissen, was [mm] (b^n-1):(b-1) [/mm] ergibt.
Dein Weg sollte Dich zu diesem Ergebnis führen:
[mm] a=1+2^{n-1}\summe_{k=0}^{n-1}2^{kn}=1+\summe_{k=1}^{n}2^{kn-1}
[/mm]
Grüße
reverend
|
|
|
|
