Primzahl, echte Teiler < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:55 Mo 20.10.2014 | | Autor: | sissile |
| Aufgabe | | Sei m =pq mit Primzahlen p und q. Sei c ein echter Teiler von m. Zeigen Sie, dass c=p oder c=q gilt. |
Hallo,
Die Aussage ist mir völlig klar aber ich krieg keine ordentliche Form des Beweises hin!! Manchmal sind doch die einfachsten Sachen schwierig formal aufzuschreiben.
c|m das heißt [mm] \exists [/mm] d [mm] \in \IZ: [/mm] c * d=m
Wenn c=p fertig. Angenommen c [mm] \not= [/mm] p
cd=m=p*q
Primfaktorzerlegung von p*q ist p*q, d.h. c muss Primfaktor p oder q enthalten und c < p*q da c echte Teiler von m.
O.B.d.A. sei p Primfaktor von c
D.h. c hast die Gestalt: c= [mm] \prod_{i=1}^M p_i [/mm] * p wobei [mm] p_i [/mm] Primzahlen sind
Da c [mm] \not= [/mm] p ist das Produkt nicht leer.
LG,
sissi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:07 Mo 20.10.2014 | | Autor: | Marcel |
Hallo Sissile,
> Sei m =pq mit Primzahlen p und q. Sei c ein echter Teiler
> von m. Zeigen Sie, dass c=p oder c=q gilt.
das stimmt aber nur, wenn $c [mm] \in \IN\,.$ [/mm] Ansonsten kann man nur sagen,
dass [mm] $c\,$ [/mm] assoziiert zu [mm] $p\,$ [/mm] oder [mm] $q\,$ [/mm] ist.
> Hallo,
> Die Aussage ist mir völlig klar aber ich krieg keine
> ordentliche Form des Beweises hin!! Manchmal sind doch die
> einfachsten Sachen schwierig formal aufzuschreiben.
>
> c|m das heißt [mm]\exists[/mm] d [mm]\in \IZ:[/mm] c * d=m
> Wenn c=p fertig. Angenommen c [mm]\not=[/mm] p
> cd=m=p*q
> Primfaktorzerlegung von p*q ist p*q, d.h. c muss
> Primfaktor p oder q enthalten und c < p*q da c echte Teiler
> von m.
> O.B.d.A. sei p Primfaktor von c
> D.h. c hast die Gestalt: c= [mm]\prod_{i=1}^M p_i[/mm] * p
Das kapier ich nicht - wieso steht da [mm] $*p\,$ [/mm] am Ende? (Ich sehe auch
nicht, wieso Du o.B.d.A. annimmst, dass $p [mm] \mid [/mm] c$ gelten soll?)
Ich sehe gerade, dass ich vorhin wohl einfach Deine Begründung überlesen
hatte. Aber im Folgenden brauchen wir das gar nicht...
> wobei
> [mm]p_i[/mm] Primzahlen sind
> Da c [mm]\not=[/mm] p ist das Produkt nicht leer.
Was hast Du denn alles zur Verfügung? Ich kann den Beweis nur mit dem
durchführen, was ich so kenne:
Sei
[mm] $m=pq\,$ [/mm] mit $p,q [mm] \in \IP\,.$
[/mm]
Es gelte
$c [mm] \mid [/mm] m$
für $1 < c < [mm] m\,.$
[/mm]
Ist [mm] $c=p\,,$ [/mm] so ist nichts mehr zu zeigen - also bleibt im Falle $c [mm] \not=p$ [/mm] nachzuweisen,
dass dann nur $c [mm] \mid [/mm] q$ gelten kann (wegen $c > [mm] 1\,$ [/mm] folgte dann [mm] $c=q\,$):
[/mm]
Sei
[mm] $c=\produkt_{k=1}^M p_i$
[/mm]
die (hier eindeutig bestimmte) Primfaktorzerlegung mit [mm] $p_i \in \IP\,,$ [/mm] diese
existiert, weil...?
Wir wählen ein
[mm] $i_0 \in \{1,...,M\},$
[/mm]
und sehen dann, dass schon
[mm] $p_{i_0} \mid [/mm] c$
gilt. Wegen $c [mm] \mid [/mm] m=pq$ folgt dann auch
[mm] $p_{i_0} \mid m=pq\,.$
[/mm]
Weil [mm] $p_{i_0} \in \IP$ [/mm] auch ein primes Element im Ring [mm] $(\IZ,+,\cdot)$ [/mm] ist, folgt...?
Jetzt Du!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:11 Di 21.10.2014 | | Autor: | sissile |
Hallo Marcel,
Danke für die Antwort.
> das stimmt aber nur, wenn $ c [mm] \in \IN\,. [/mm] $ Ansonsten kann man nur sagen,
> dass $ [mm] c\, [/mm] $ assoziiert zu $ [mm] p\, [/mm] $ oder $ [mm] q\, [/mm] $ ist.
In welchen Ringen gilt das denn? In Integritätsbereichen, faktoriellen Ringen oder brauch ich nur ein kommutativen Ring mit 1? Weil so ein allgemeines Bsp. möchte ich mir dannach auch mal anschauen! Also wenn du mir aufschreiben könntest wie das Resultat mit welchen Vorbedingungen ausschaut.
> $ [mm] p_{i_0} \mid m=pq\,. [/mm] $
> Weil $ [mm] p_{i_0} \in \IP [/mm] $ auch ein primes Element im Ring $ [mm] (\IZ,+,\cdot) [/mm] $ ist, folgt...?
> Jetzt Du!
[mm] p_{i_0}|p\vee p_{i_0}|q
[/mm]
Da [mm] p_{i_0} [/mm] selbst eine Primzahl ist =>
[mm] p_{i_0}=p\vee p_{i_0}=q
[/mm]
Das ist ja eigentlich ein ausführlicher Beweis dafür, dass c mindestens p oder q als Primfaktor enthalten muss.
[mm] i_o [/mm] war ja beliebig gewählt, also enthält c nur p oder q als Primfaktoren.
Jetzt könnte man Tobit´s Beweis dranhängen und wäre fertig.
LG,
sissi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:12 Di 21.10.2014 | | Autor: | sissile |
Hallo Marcel ;=),
Danke für die Antwort.
> das stimmt aber nur, wenn $ c [mm] \in \IN\,. [/mm] $ Ansonsten kann man nur sagen,
> dass $ [mm] c\, [/mm] $ assoziiert zu $ [mm] p\, [/mm] $ oder $ [mm] q\, [/mm] $ ist.
In welchen Ringen gilt das denn? In Integritätsbereichen, faktoriellen Ringen oder brauch ich nur ein kommutativen Ring mit 1? Weil so ein allgemeines Bsp. möchte ich mir dannach auch mal anschauen! Also wenn du mir aufschreiben könntest wie das Resultat mit welchen Vorbedingungen ausschaut.
> $ [mm] p_{i_0} \mid m=pq\,. [/mm] $
> Weil $ [mm] p_{i_0} \in \IP [/mm] $ auch ein primes Element im Ring $ [mm] (\IZ,+,\cdot) [/mm] $ ist, folgt...?
> Jetzt Du!
$ [mm] p_{i_0}|p\vee p_{i_0}|q [/mm] $
Da $ [mm] p_{i_0} [/mm] $ selbst eine Primzahl ist =>
$ [mm] p_{i_0}=p\vee p_{i_0}=q [/mm] $
Das ist ja eigentlich ein ausführlicher Beweis dafür, dass c mindestens p oder q als Primfaktor enthalten muss.
$ [mm] i_o [/mm] $ war ja beliebig gewählt, also enthält c nur p oder q als Primfaktoren.
Jetzt könnte man Tobit´s Beweis dranhängen und wäre fertig.
LG,
sissi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:28 Di 21.10.2014 | | Autor: | Marcel |
Hallo Sissile,
> Hallo Marcel ;=),
> Danke für die Antwort.
>
> > das stimmt aber nur, wenn [mm]c \in \IN\,.[/mm] Ansonsten kann man
> nur sagen,
> > dass [mm]c\,[/mm] assoziiert zu [mm]p\,[/mm] oder [mm]q\,[/mm] ist.
>
> In welchen Ringen gilt das denn? In Integritätsbereichen,
> faktoriellen Ringen oder brauch ich nur ein kommutativen
> Ring mit 1?
in faktoriellen Ringen ist eine Primfaktorzerlegung nur eindeutig bis auf
Assoziiertheit. (Allgemeineres weiß ich auch nicht, da warten wir besser
auf Experten wie etwa Felixf, die kennen sich da besser aus...)
Gleiches gilt übrigens auch für kgV und ggT. Schau' mal in das Buch
"Elementare und algebraische Zahlentheorie" von Müller-Stach,
Piontkowski.
> Weil so ein allgemeines Bsp. möchte ich mir
> dannach auch mal anschauen!
Ich finde, dass [mm] $(\IZ,+,\cdot)$ [/mm] schon ein erstes passendes Beispiel ist - dieser
faktorielle Ring ist aber sehr überschaubar, es gibt ja nur die Einheiten [mm] $\pm 1\,.$
[/mm]
Ansonsten auch mal [mm] $\IZ+i\IZ$ [/mm] angucken, wobei Normfunktion [mm] $N(z):=z*\overline{z}\,.$
[/mm]
> Also wenn du mir aufschreiben
> könntest wie das Resultat mit welchen Vorbedingungen
> ausschaut.
>
> > [mm]p_{i_0} \mid m=pq\,.[/mm]
>
> > Weil [mm]p_{i_0} \in \IP[/mm] auch ein primes Element im Ring
> [mm](\IZ,+,\cdot)[/mm] ist, folgt...?
>
> > Jetzt Du!
>
> [mm]p_{i_0}|p\vee p_{i_0}|q[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> Da [mm]p_{i_0}[/mm] selbst eine Primzahl
> ist =>
> [mm]p_{i_0}=p\vee p_{i_0}=q[/mm]
>
> Das ist ja eigentlich ein ausführlicher Beweis dafür,
> dass c mindestens p oder q als Primfaktor enthalten muss.
Genau. Wegen $1 < [mm] p_{i_0} \le [/mm] c < p$ (warum gilt das?) kann aber [mm] $p_{i_0}=p$ [/mm] nicht sein
(wir haben [mm] $c=p\,$ [/mm] ausgeschlossen!). Folglich muss
[mm] $p_{i_0} \mid [/mm] q$
gelten. Daraus wiederum folgt, weil [mm] $p_{i_0},q \in \IP$ [/mm] sind,
[mm] $p_{i_0}=q\,.$
[/mm]
> [mm]i_o[/mm] war ja beliebig gewählt, also enthält c nur p oder q
> als Primfaktoren.
Wenn $c [mm] \not=p\,,$ [/mm] so haben wir oben gesehen, dass $q [mm] \mid p\,.$ [/mm] Das sollten
wir weiter verwenden...
> Jetzt könnte man Tobit´s Beweis dranhängen und wäre
> fertig.
Das muss ich mir mal in Ruhe angucken. Ich denke aber, dass sich der obige
Ansatz auch so noch zu Ende bringen läßt - ich hoffe es jedenfalls. Anscheinend
hatte ich das gestern *zu schnell* im Kopf durchgespielt...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:54 Do 23.10.2014 | | Autor: | sissile |
Hallo Marcel,
Sry ich war krank, deshalb erst jetzt meine Antwort.
> Genau. Wegen $ 1 < [mm] p_{i_0} \le [/mm] c < p $ (warum gilt das?)
Da [mm] p_{i_0} [/mm] | c ist mir 1 < [mm] p_{i_0} \le [/mm] c klar.
Aber c < p ist mir noch nicht klar. Wir wissen doch erstmal nur c [mm] \le [/mm] m=pq
lg,
sissi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:46 Do 23.10.2014 | | Autor: | Marcel |
Hallo Sissi,
> Hallo Marcel,
> Sry ich war krank, deshalb erst jetzt meine Antwort.
>
> > Genau. Wegen [mm]1 < p_{i_0} \le c < p[/mm] (warum gilt das?)
> Da [mm]p_{i_0}[/mm] | c ist mir 1 < [mm]p_{i_0} \le[/mm] c klar.
>
> Aber c < p ist mir noch nicht klar. Wir wissen doch erstmal
> nur c [mm]\le[/mm] m=pq
das war mir selber nicht so ganz klar. Mein Gedankengang dahingehend
war einfach, dass man das vermutlich o.E. annehmen kann, weil ja [mm] $m=p*q\,$ [/mm] die
Primfaktorzerlegung von [mm] $m\,$ [/mm] ist, und daher jeder (echte) Teiler von [mm] $m\,$ [/mm] sicher
kleinergleich einer der beiden Primzahlen sein muss.
Evtl. kann man aber auch obiges weiterführen, indem man $c > [mm] p\,$ [/mm] annimmt und
das zu einem Widerspruch führt... Aber das sehe ich eher kritisch (auch, wenn
ich das schonmal zu Papier gebracht hatte, aber da sah es mir so aus, als
wenn ich etwas unbedacht gelassen habe).
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:40 Mo 20.10.2014 | | Autor: | tobit09 |
Hallo sissile!
> Sei m =pq mit Primzahlen p und q. Sei c ein echter Teiler
> von m. Zeigen Sie, dass c=p oder c=q gilt.
Ich setze voraus, dass c eine natürliche Zahl ist.
Ebenso seien bei mir alle Primfaktoren natürliche Zahlen (d.h. nicht negativ).
> c|m das heißt [mm]\exists[/mm] d [mm]\in \IZ:[/mm] c * d=m
Guter Anfang.
> Wenn c=p fertig. Angenommen c [mm]\not=[/mm] p
Das braucht man nicht wirklich.
Damit wären q und p nicht mehr "gleichberechtigt" und dein o.B.d.A. weiter unten wäre ungerechtfertigt.
Also diese Zeile einfach streichen.
> cd=m=p*q
> Primfaktorzerlegung von p*q ist p*q, d.h. c muss
> Primfaktor p oder q enthalten
Ja, das kann man sich überlegen:
$c$ hat mindestens einen Primfaktor (sonst $c=1$ im Widerspruch zu $c$ ECHTER Teiler von $m$).
Da die Primfaktoren von $cd$ gerade $p$ und $q$ sind, kann $c$ auch nur maximal die Primfaktoren $p$ und $q$ enthalten.
Ich glaube, das Folgende hilft uns leider nicht weiter.
> und c < p*q da c echte Teiler
> von m.
> O.B.d.A. sei p Primfaktor von c
> D.h. c hast die Gestalt: c= [mm]\prod_{i=1}^M p_i[/mm] * p wobei
> [mm]p_i[/mm] Primzahlen sind
> Da c [mm]\not=[/mm] p ist das Produkt nicht leer.
Seien
[mm] $c=\prod_{i=1}^kp_i$
[/mm]
und
[mm] $d=\prod_{i=1}^lq_i$
[/mm]
die Primfaktorzerlegungen von $c$ und $d$.
Die Primfaktorzerlegung von $m=cd$ lautet also:
[mm] $m=\prod_{i=1}^kp_i*\prod_{i=1}^lq_i$.
[/mm]
Insbesondere hat $m$ genau $k+l$ viele (nicht notwendig paarweise verschiedene) Primfaktoren.
Die Primfaktorzerlegung von $m$ lautet aber auch:
$m=pq$.
Insbesondere hat $m$ genau $2$ (nicht notwendig verschiedene) Primfaktoren.
Also $k+l=2$.
Es liegt daher einer der folgenden drei Fälle vor:
1. Fall: $k=0$, $l=2$
Dann wäre
[mm] $c=\prod_{i=1}^kp_i=\prod_{i=0}^0p_i=1$
[/mm]
im Widerspruch zu $c$ ECHTER Teiler von $m$.
2. Fall: $k=2$, $l=0$
Dann wäre
[mm] $d=\prod_{i=1}^lq_i=\prod_{i=1}^0q_i=1$
[/mm]
und somit
$c=c*1=c*d=m$
im Widerspruch zu $c$ ECHTER Teiler von $m$.
3. Fall: $k=1$, $l=1$
Dann gilt
[mm] $c=\prod_{i=1}^kp_i=\prod_{i=1}^1p_i=p_1$.
[/mm]
[mm] $m=\prod_{i=1}^kp_i*\prod_{i=1}^lq_i$ [/mm] enthält also den Primfaktor $c$.
Die einzigen beiden Primfaktoren von $m=pq$ sind aber $p$ und $q$.
Also gilt $c=p$ oder $p=q$.
(Die wesentliche Idee dieses Beweises, ist die EINDEUTIGKEIT der Primfaktorzerlegung von $m$ bis auf Reihenfolge.)
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:31 Mo 20.10.2014 | | Autor: | Marcel |
Hallo Tobi,
> Hallo sissile!
>
>
> > Sei m =pq mit Primzahlen p und q. Sei c ein echter Teiler
> > von m. Zeigen Sie, dass c=p oder c=q gilt.
> Ich setze voraus, dass c eine natürliche Zahl ist.
>
> Ebenso seien bei mir alle Primfaktoren natürliche Zahlen
> (d.h. nicht negativ).
>
>
> > c|m das heißt [mm]\exists[/mm] d [mm]\in \IZ:[/mm] c * d=m
> Guter Anfang.
>
>
> > Wenn c=p fertig. Angenommen c [mm]\not=[/mm] p
> Das braucht man nicht wirklich.
> Damit wären q und p nicht mehr "gleichberechtigt" und
> dein o.B.d.A. weiter unten wäre ungerechtfertigt.
> Also diese Zeile einfach streichen.
ich verstehe an dieser Stelle Deine Argumentation nicht (wenn man davon
absieht, dass Du sagst, dass man darauf auch verzichten könnte).
Sissiles Aufgabe ist: Ist [mm] $c\,$ [/mm] echter Teiler von [mm] $m=p*q\,$ [/mm] mit Primzahlen [mm] $p,q\,,$
[/mm]
so folgt [mm] $c=p\,$ [/mm] oder [mm] $c=q\,.$
[/mm]
Im Falle [mm] $c=p\,$ [/mm] hat sie in der Tat nichts mehr zu zeigen. Sie muss also noch den
Fall [mm] $\neg(c =p)\,,$ [/mm] bzw. anders gesagt: $c [mm] \not=p\,$ [/mm] behandeln.
Was hat das mit "nicht gleichberechtigt" zu tun?
Ich finde die Strategie, wenn man
$A [mm] \Rightarrow$ [/mm] ($B [mm] \vee [/mm] C$)
zu beweisen hat, dann zu sagen:
1. Fall: Wenn [mm] $A\,$ [/mm] und [mm] $B\,$ [/mm] gilt, dann ist nichts mehr zu beweisen.
2. Fall: Gelte nun [mm] $A\,,$ [/mm] und [mm] $B\,$ [/mm] gelte nicht. Dann zeige, dass dann [mm] $C\,$ [/mm] gelten
muss!
durchaus absolut korrekt. Was anderes macht sie nicht.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:59 Di 21.10.2014 | | Autor: | tobit09 |
Hallo Marcel!
> > > Wenn c=p fertig. Angenommen c [mm]\not=[/mm] p
> > Das braucht man nicht wirklich.
> > Damit wären q und p nicht mehr "gleichberechtigt" und
> > dein o.B.d.A. weiter unten wäre ungerechtfertigt.
> > Also diese Zeile einfach streichen.
>
> ich verstehe an dieser Stelle Deine Argumentation nicht
> (wenn man davon
> absieht, dass Du sagst, dass man darauf auch verzichten
> könnte).
>
> Sissiles Aufgabe ist: Ist [mm]c\,[/mm] echter Teiler von [mm]m=p*q\,[/mm] mit
> Primzahlen [mm]p,q\,,[/mm]
> so folgt [mm]c=p\,[/mm] oder [mm]c=q\,.[/mm]
>
> Im Falle [mm]c=p\,[/mm] hat sie in der Tat nichts mehr zu zeigen.
> Sie muss also noch den
> Fall [mm]\neg(c =p)\,,[/mm] bzw. anders gesagt: [mm]c \not=p\,[/mm]
> behandeln.
>
> Was hat das mit "nicht gleichberechtigt" zu tun?
DAS hat nichts mit "nicht gleichberechtigt" zu tun.
Aber WEITER UNTEN stellt sissile "c muss Primfaktor p oder q enthalten" fest und möchte dann oBdA annehmen, dass c den Primfaktor p enthält.
DIESES oBdA wäre dann gerechtfertigt, wenn p und q absolut gleichberechtigt wären (und man so den Fall "c enthält den Primfaktor q" auf den Fall "c enthält den Primfaktor p" zurückführen könnte).
Durch sissiles Annahme [mm] $c\not=p$ [/mm] (ohne auch die Annahme [mm] $c\not=q$ [/mm] zu treffen) sind $p$ und $q$ aber nicht mehr gleichberechtigt.
Mein Vorschlag zur Abhilfe war, auf die Annahme [mm] $c\not=p$ [/mm] zu verzichten.
Alternativ könnte man auf das oBdA verzichten.
> Ich finde die Strategie, wenn man
>
> [mm]A \Rightarrow[/mm] ([mm]B \vee C[/mm])
>
> zu beweisen hat, dann zu sagen:
> 1. Fall: Wenn [mm]A\,[/mm] und [mm]B\,[/mm] gilt, dann ist nichts mehr zu
> beweisen.
>
> 2. Fall: Gelte nun [mm]A\,,[/mm] und [mm]B\,[/mm] gelte nicht. Dann zeige,
> dass dann [mm]C\,[/mm] gelten
> muss!
>
> durchaus absolut korrekt. Was anderes macht sie nicht.
Da stimme ich voll zu.
Das Problem entsteht dann erst weiter unten beim oBdA.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:45 Di 21.10.2014 | | Autor: | sissile |
Hallo tobit,
Vielen Dank für deinen einfach zu verstehenden Beweis!
|
|
|
|
