Lemma von Euklid < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:30 Fr 12.10.2007 | | Autor: | quest |
| Aufgabe | Lemma von Euklid
Eine Zahl p ist Primzahl genau dann, wenn für alle a,b [mm] \in \IN: [/mm] p | ab [mm] \Rightarrow [/mm] p|a [mm] \vee [/mm] p|b. |
Hallo an alle,
sorry das ich schon wieder eine Frage habe. Aber ich komm bei dem Beweis einfach nicht klar.
Die Rückrichtung kann ich noch einigermaßen aufschreiben:
[mm] "\Leftarrow [/mm] ": Angenommen die Aussage "für alle a,b [mm] \in \IN: [/mm] p | ab [mm] \Rightarrow [/mm] p|a [mm] \vee [/mm] p|b" gilt und angenommen p ist keine Primzahl, d.h. es gäbe einen echten Teiler a > 1 und ein b derart, dass p = ab. Nach Voraussetzung ist aber p auch Teiler von b d.h. es gibt ein q aus [mm] \IN [/mm] so dass b = pq.
Damit ist aber p = a pq, d.h. aq = 1, d.h. a = 1, und das steht im Widerspruch dazu, das a echter Teiler von p ist.
Ich hab das Gefühl, dass das soweit passt. Aber die andere Richtung, da komm ich nicht weiter. Ich hab schon geschaut, aber unser "Material" an Hilfssätzen ist relativ schmal. Wir haben lediglich den Unendlichkeitsbeweis von Euklid geführt und die Primzahlen eben definiert, als Zahlen, die nur (-1,1,p,-p) als Teiler haben.
Da das Ding "Lemma von Euklid" heißt, dachte ich mir, dass es evtl. direkt aus dem Unendlichkeitsbeweis folgt, aber ich seh das nicht direkt :-/
Hat mir jemand einen Tipp, wie ich mit unseren "Hilfsmitteln" bei dem Beweis weiterkomme, oder muss ich den "Überbau" noch vergrößern damit das klappt?
Viele grüße und vielen dank für eure Hilfe
quest
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Lemma von Euklid
> Eine Zahl p ist Primzahl genau dann, wenn für alle a,b [mm]\in \IN:[/mm]
> p | ab [mm]\Rightarrow[/mm] p|a [mm]\vee[/mm] p|b.
> Aber die andere
> Richtung, da komm ich nicht weiter. Ich hab schon geschaut,
> aber unser "Material" an Hilfssätzen ist relativ schmal.
Hallo,
ich bin schon fast fort, aber noch ein Tip auf die Schnelle.
Schau Dich mal um bei den Dingen, die Ihr im Zusammenhang mit Teilerfremdheit gezeigt habt.
Davon wirst du was verwenden müssen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:59 Fr 12.10.2007 | | Autor: | quest |
Hallo Angela,
danke schon mal für den Hinweis. Ich schau gerade mal nach, wir haben noch etwas, nämlich das der Modulo auf [mm] \IZ [/mm] eine Äquivalenzrelation und auf [mm] \IN [/mm] eine Halbordnung ist.
Ich weiß aber nicht, ob mir das hier "weiterhilft".
Andererseits hab ich mir den Beweis von Euklid nochmal angeschaut, da hatten wir einen Hilfssatz, der besagt: ist n [mm] \in \IN [/mm] (n > 1), dann exisitiert eine Primzahl p, so dass n = pz mit z [mm] \in \IZ. [/mm] D.h. p | n.
Habe ich jetzt natürliche Zahlen a,b [mm] \in \IN, [/mm] dann heißt das, dass es eine Primzahl p gibt, mit p | a, aber dann teil p sicher auch ab, d.h. p| ab und andersherum.
Aber wenn ich das richtig verstehe, ist das hier "umgekehrt", da ich ja aus p | ab [mm] \Rightarrow [/mm] p|a [mm] \vee [/mm] p|b schließen soll.
Vielen dank schon mal,
grüße
quest
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:59 Fr 12.10.2007 | | Autor: | leduart |
Hallo
mit deinem Beweis in der einen Richtung komm ich nicht zurecht.
> Lemma von Euklid
> Eine Zahl p ist Primzahl genau dann, wenn für alle a,b [mm]\in \IN:[/mm]
> p | ab [mm]\Rightarrow[/mm] p|a [mm]\vee[/mm] p|b.
> Hallo an alle,
>
> sorry das ich schon wieder eine Frage habe. Aber ich komm
> bei dem Beweis einfach nicht klar.
>
> Die Rückrichtung kann ich noch einigermaßen aufschreiben:
>
> [mm]"\Leftarrow[/mm] ": Angenommen die Aussage "für alle a,b [mm]\in \IN:[/mm]
> p | ab [mm]\Rightarrow[/mm] p|a [mm]\vee[/mm] p|b" gilt und angenommen p ist
> keine Primzahl, d.h. es gäbe einen echten Teiler a > 1 und
> ein b derart, dass p = ab. Nach Voraussetzung ist aber p
> auch Teiler von b d.h. es gibt ein q aus [mm]\IN[/mm] so dass b =
> pq.
>
> Damit ist aber p = a pq, d.h. aq = 1, d.h. a = 1, und das
> steht im Widerspruch dazu, das a echter Teiler von p ist.
du verwendest hier a und b anscheinend in 2 Bedeutungen:
einmal a in ab, einmal als Faktor. sonst wäre doch p=ab sinnlos.
p|ab heisst doch ab=k*p p|a heisst a=l*p p teilt b heisst p=m*b
Die vors heisst doch in Worten: für alle natürlichen Zahlen a*b wenn p a*b teilt, dann teilt es entweder a oder b oder beide.
Beispiele p=3 p teilt 6*5 p teilt 6 p Teilt 15*6 p teilt 15 und 6.
Entweder du musst genauer formulieren, oder deine Idee ist falsch.
dürft ihr die eindeutige Primzahlzerlegung verwenden?
Gruss leduart
> Ich hab das Gefühl, dass das soweit passt. Aber die andere
> Richtung, da komm ich nicht weiter. Ich hab schon geschaut,
> aber unser "Material" an Hilfssätzen ist relativ schmal.
> Wir haben lediglich den Unendlichkeitsbeweis von Euklid
> geführt und die Primzahlen eben definiert, als Zahlen, die
> nur (-1,1,p,-p) als Teiler haben.
>
> Da das Ding "Lemma von Euklid" heißt, dachte ich mir, dass
> es evtl. direkt aus dem Unendlichkeitsbeweis folgt, aber
> ich seh das nicht direkt :-/
>
> Hat mir jemand einen Tipp, wie ich mit unseren
> "Hilfsmitteln" bei dem Beweis weiterkomme, oder muss ich
> den "Überbau" noch vergrößern damit das klappt?
>
> Viele grüße und vielen dank für eure Hilfe
> quest
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:04 Fr 12.10.2007 | | Autor: | quest |
Hallo nochmal.
Danke leduart für den Hinweis. Ich seh was du meinst. Ich dachte, ich könnte sagen, dass wenn p|a, das es dann ein b gibt, sodass p = ab und damit p|ab.
Aber p|ab heißt ja wiederum, dass es ein k gibt, sodass pk = ab.
Das ist wohl nen gedanklicher Fehler...mist jetzt steh ich wieder am Anfang :-/
Grüße
quest
|
|
|
| |
|
> Das ist wohl nen gedanklicher Fehler...mist jetzt steh ich
> wieder am Anfang :-/
Nein, nein, ganz so schlimm ist das nicht!
Du hast es nur etwas ungeschickt eingefädelt, weil Du die Buchstaben a,b in der Voraussetzung verwendest und gleichzeitig bei der Zerlegung von p.
Ich korrigiere das unten im Zitat mal dahingehend, daß p in p=rs zerlegt wird.
>>> $ [mm] "\Leftarrow [/mm] $ ": Angenommen die Aussage "für alle a,b $ [mm] \in \IN: [/mm] $ p | ab $ [mm] \Rightarrow [/mm] $ p|a $ [mm] \vee [/mm] $ p|b" gilt
>>> und angenommen p ist keine Primzahl,
>>> d.h. es gäbe einen echten Teiler r > 1 und ein s derart, dass p = rs.
Es teilt also s die Primzahl p.
>>> Nach Voraussetzung ist aber p auch Teiler von s d.h. es gibt ein q aus $ [mm] \IN [/mm] $ so dass s=pq.
>>> Damit ist aber p = r pq, d.h. rq = 1, d.h. r = 1, und das steht im Widerspruch dazu, das a echter Teiler von p ist.
Die Annahme, daß p keine Primzahl ist, führt zum Widerspruch, also ist p eine Primzahl.
Gruß v. Angela
|
|
|
| |
|
Zur "Hinrichtung":
schau mal nach, ob Ihr folgendes gezeigt habt - wenn nicht, zeig es:
Wenn r das Produkt st teilt und wenn gleichzeitig r und s teilerfremd sind, so teilt r die Zahl t.
Damit kommst Du beim Beweis hin.
Nimm eine Primzahl p, welche ab teilt und für welche [mm] p\not [/mm] a gilt, und zeig daß p damm b teilt.
(Überlege Dir hierfür zunächst, welche gemeinsamen Teiler p und a haben.)
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:12 Fr 12.10.2007 | | Autor: | quest |
Hallo Angela,
ich bin mir jetzt nich 100%ig sicher ob ich die Rückrichtung komplett verstanden habe, ich versuch mir gerade die Logik mit diesen Quantoren Zeichen aufzuschreiben:
Die Rückrichtung wäre ja, ich hab erstmal ein p [mm] \in \IN
[/mm]
[mm] "\Leftarrow": \forall [/mm] a,b [mm] \in \IN: [/mm] p|ab => p|a [mm] \vee [/mm] p|b [mm] \Rightarrow [/mm] p ist Primzahl
Da wir ja per Widerspruch verfahren, zeigen wir äquivalent:
p nicht Primzahl [mm] \Rightarrow \neg [/mm] ( [mm] \forall [/mm] a,b [mm] \in \IN: [/mm] p|ab [mm] \Rightarrow [/mm] p|a [mm] \vee [/mm] p|b)
Angenommen also p ist nicht Primzahl, d.h. es gäbe einen echten Teiler [mm] \IN \ni [/mm] r > 1 und ein s derart, dass p = rs.
Es ist also s | p.
Nach Voraussetzung gilt aber auch: "p | rs [mm] \Rightarrow [/mm] p|s [mm] \vee [/mm] p|r", d.h. wir können o.E. annehmen dass p auch Teiler von s ist. D.h. es gibt ein q aus $ [mm] \IN [/mm] $ so dass s=pq.
Damit ist aber p = r pq, d.h. rq = 1, d.h. r = 1, und das steht im Widerspruch dazu, das s echter Teiler von p ist.
D.h. p ist Primzahl.
Ich hoff ich schnall die Logik ein wenig...
Zwecks der Hinrichtung stehen uns wie gesagt keine anderen Hilfssätze zur Verfügung, ich hab mir aber gerade darüber was du gesagt hast Gedanken gemacht:
Die Aussage von dem Hilffssatz ist also:
r | st und ggT(r,s) = 1, dann gilt r|t.
Das müsste ich noch beweisen, aber ich glaub ich seh wie die Hinrichtung dann funktionieren kann:
Ich habe also p ist Primzahl [mm] \Rightarrow \forall [/mm] a,b [mm] \in \IN: [/mm] p|ab => p|a [mm] \vee [/mm] p|b
äquivalent dazu:
[mm] \gdw
[/mm]
[mm] \neg (\forall [/mm] a,b [mm] \in \IN: [/mm] p|ab => p|a [mm] \vee [/mm] p|b ) => p nicht Primzahl
Also [mm] "\Rightarrow":
[/mm]
Angenommen p ist Primzahl und teilt ab, aber p teilt nicht a, d.h. p [mm] \not| [/mm] a. D.h. aber, dass der größte gemeinsame Teiler ggT(a,p) = 1 ist und dieser Satz von oben sagt mir jetzt, dass p | b.
Und genau so zeigt man das für b.
Was meinst du? Jetzt muss ich noch diesen anderen Satz zeigen...den Begriff ggT kenn ich noch halbwegs aus der Schule, aber das ist nun auch schon lang her.
Ich find das ein wenig krass, wie sehr man da in der "Luft" hängen gelassen wird. Ich mein der Prof hätte uns ja wenigstens ein bisschen ein Grundgerüst an Hilfsmitteln zur Verfügung stellen können :-/
Vielen dank schon mal, viele Grüße
quest
|
|
|
| |
|
> Angenommen also p ist nicht Primzahl, d.h. es gäbe einen
> echten Teiler [mm]\IN \ni[/mm] r > 1 und ein s derart, dass p = rs.
> Es ist also s | p.
>
> Nach Voraussetzung gilt aber auch: "p | rs [mm]\Rightarrow[/mm] p|s
> [mm]\vee[/mm] p|r", d.h. wir können o.E. annehmen
p kann r nicht teilen, denn r ist ein echter Teiler von p, also ist 1<r<p.
Also muß nach Voraussetzung p die Zahl s teilen.
>dass p auch Teiler
> von s ist. D.h. es gibt ein q aus [mm]\IN[/mm] so dass s=pq.
>
> Damit ist aber p = r pq, d.h. rq = 1, d.h. r = 1, und das
> steht im Widerspruch dazu, das s echter Teiler von p ist.
Die Annahme, daß p keine Primzahl ist, führt zum Widerspruch,
>
> D.h. p ist Primzahl.
Um die andere Richtung können wir uns morgen kümmern, es ist mir zu spät jetzt.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:34 Sa 13.10.2007 | | Autor: | koepper |
Hallo,
> Die Rückrichtung wäre ja, ich hab erstmal ein p [mm]\in \IN[/mm]
>
> [mm]"\Leftarrow": \forall[/mm] a,b [mm]\in \IN:[/mm] p|ab => p|a [mm]\vee[/mm] p|b
> [mm]\Rightarrow[/mm] p ist Primzahl
>
> Da wir ja per Widerspruch verfahren, zeigen wir äquivalent:
> p nicht Primzahl [mm]\Rightarrow \neg[/mm] ( [mm]\forall[/mm] a,b [mm]\in \IN:[/mm]
> p|ab [mm]\Rightarrow[/mm] p|a [mm]\vee[/mm] p|b)
>
> Angenommen also p ist nicht Primzahl, d.h. es gäbe einen
> echten Teiler [mm]\IN \ni[/mm] r > 1 und ein s derart, dass p = rs.
Vorsicht: Du mußt r >1 UND s > 1 fordern, nur r > 1 reicht nicht, denn sonst könnte ja r = p und s = 1 sein.
Damit folgt dann auch r < p und s < p.
> Es ist also s | p.
das ist wohl keiner besonderen Erwähnung wert
> Nach Voraussetzung gilt aber auch: "p | rs [mm]\Rightarrow[/mm] p|s
> [mm]\vee[/mm] p|r"
bis hier ganz fein. Und jetzt haben wir den Widerspruch doch schon. Denn p > r und p > s. Also kann p weder r noch s teilen.
Liebe Grüße
Will
|
|
|
| |
|
> Zwecks der Hinrichtung stehen uns wie gesagt keine anderen
> Hilfssätze zur Verfügung,
Hallo,
irgendwetwas müßt Ihr aber doch gemacht haben...
Ich nehme doch schon ein, daß Ihr Euch etwas mit Teilbarkeit beschäftigt habt?
> Die Aussage von dem Hilffssatz ist also:
> r | st und ggT(r,s) = 1, dann gilt r|t.
>
> Das müsste ich noch beweisen,
Ja. Falls Ihr hattet, daß man für teilerfremde Zahlen r,s ganze Zahlen [mm] \lambda, \mu [/mm] finden kann mit [mm] 1=\lambda [/mm] r + [mm] \mu [/mm] s (lief bei uns unter Lemma v. Bezout), geht das recht einfach und schnell.
> aber ich glaub ich seh wie
> die Hinrichtung dann funktionieren kann:
> Also [mm]"\Rightarrow":[/mm]
> Angenommen p ist Primzahl und teilt ab, aber p teilt nicht
> a, d.h. p [mm]\not|[/mm] a. D.h. aber, dass der größte gemeinsame
> Teiler ggT(a,p) = 1 ist
(weil ja p nur die (pos.) Teiler 1 und p hat)
> und dieser Satz von oben sagt mir
> jetzt, dass p | b.
Ja. Damit bist Du fertig.
>
> Und genau so zeigt man das für b.
Für b brauchst Du das nicht mehr zu zeigen, die Sache ist ja völlig symmetrisch.
Wenn Du Dich sicherer fühlst damit, kannst Du oben schreiben: gelte o.B.d.A p teilt nicht a.
Natürlich ist es nicht verboten, das Ganze auch noch für b durchzuführen...
> Ich find das ein wenig krass, wie sehr man da in der "Luft"
> hängen gelassen wird. Ich mein der Prof hätte uns ja
> wenigstens ein bisschen ein Grundgerüst an Hilfsmitteln zur
> Verfügung stellen können :-/
Ich weiß natürlich nicht, was Dein Prof. tut, aber ich weiß, daß ich die Hilfsmittel, die uns unser Prof. an die Hand gegeben hat, nicht immer (bzw. oftmals nicht...) erkannt habe. Daher könnte ich mir vorstellen, daß es in Deiner Mitschrift doch etwas Passendes gibt.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:12 Sa 13.10.2007 | | Autor: | quest |
Hallo Angela und Willi,
naja...wir haben echt nicht viel behandelt. Dieses Lemma kenne ich auch nicht, und ich hab nen wenig gegoogelt, dass man das Lemma mit dem "erweiterten euklidschen Algorithmus" beweisen kann...
das sind aber alles begriffe, die mir persönlich nicht viel sagen. vielleicht hat sich der aufgabensteller auch einfach vertan und wollte nur, das wir eine richtung, die rückrichtung, zeigen. denn die müssten wir mit unseren "hilfsmitteln" beweisen können.
wie gesagt, das einzige was wir gemacht haben, war definiert was ne primzahl ist und die unendlichkeit der primzahlen bewiesen, sowie die kongruenzrelation [mm] \equiv [/mm] eingeführt, wobei n [mm] \in \IN [/mm] und a,b [mm] \in \IZ [/mm] und man schreibt: a [mm] \equiv [/mm] b mod n, wenn n | a-b und wir haben bewiesen, das das eine äquivalenzrelation auf [mm] \IZ [/mm] ist.
aber das war es auch schon alles... vielleicht erwartet der prof auch, das wir das alles schon kennen...naja, ich werd den beweis nun so halbwegs aufschreiben, und dann werden wir ja sehen...
ich hoff aber mal, das geht nicht so weiter :-(
grüße und dank für eure hilfe,
quest
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:28 So 14.10.2007 | | Autor: | quest |
Hallo Angela und Willi nochmal.
Ich brüte immer noch an einer "einfacheren" Lösung, bei welcher ich nicht all die Hilfssätze beweisen muss.
Angenommen mir stünde der Satz zur Verfügung, das jede natürliche Zahl eine Primfaktorzerlegung besitzt -- könnte ich damit was anfangen, gerade bei der "Hin" Richtung?
Sei p eine Primzahl
Ich hab a,b [mm] \in \IN [/mm] beliebig aber fest.
a und b haben eine Primfaktorzerlegung
a = [mm] p_1 \cdot \ldots p_n
[/mm]
b = [mm] q_1 \cdot \ldots q_k,
[/mm]
dann wäre eine Primfaktorzerlegung von ab doch
ab = [mm] p_1 \cdot \ldots p_n \cdot q_1 \cdot \ldots q_k,
[/mm]
wenn jetzt p|ab, dann ist doch klar, dass p|a oder p|b, da ja der Teiler p entweder in der Primfaktorzerlegung von a oder von b vorkam.
Was sagt ihr dazu?
Vielen dank für das Feedback,
quest
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:03 Mo 15.10.2007 | | Autor: | leduart |
Hallo
ja das geht, aber du brauchst die Eindeutigkeit der Primzahlzerlegung! und die muss man erst beweisen!
Gruss leduart
|
|
|
|
