teilerfremdheit

08.05.2011, 21:19

kuchen11

teilerfremdheit

Meine Frage:
Hallo, ich habe eine Frage.
Es geht um folgendes Problem:
es soll bewiesen werden, dass die darstellung einer primzahl p in der form ax²+by² mit a,b aus den natürlichen zahlen eindeutig ist.
ich hänge an folgender stelle:
es wird angenommen, dass p=au²+bv²=ax²+by² mit ggt(u,v)=1=ggt(x,y).
wenn uy=vx ist, dann ist wegen ggt(u,v)=1=ggt(x,y) u|x und x|u und somit u=x, aber wieso ist das so??

Meine Ideen:
also es ist schon klar, wenn man sich ein paar beispiele ansieht, aber mir ist nicht klar, wie ich das richtig erklären kann

09.05.2011, 11:46

Reksilat

Auf diesen Beitrag antworten »

RE: teilerfremdheit
Hallo kuchen,

Zitat:

Original von kuchen11
wenn uy=vx ist, dann ist wegen ggt(u,v)=1=ggt(x,y) u|x und x|u und somit u=x, aber wieso ist das so??

Wenn $\begin{eqnarray*} uy=vx \end{eqnarray*}$ ist, dann teilt $\begin{eqnarray*} u \end{eqnarray*}$ auch $\begin{eqnarray*} vx \end{eqnarray*}$ . Wenn also eine Primzahlpotenz $\begin{eqnarray*} q^t \end{eqnarray*}$ das $\begin{eqnarray*} u \end{eqnarray*}$ teilt, so muss $\begin{eqnarray*} q^t \end{eqnarray*}$ auch ein Teiler von $\begin{eqnarray*} vx \end{eqnarray*}$ sein. Aufgrund der Teilerfremdheit darf das $\begin{eqnarray*} q \end{eqnarray*}$ nicht das $\begin{eqnarray*} v \end{eqnarray*}$ teilen. Also teilt $\begin{eqnarray*} q^t \end{eqnarray*}$ das $\begin{eqnarray*} x \end{eqnarray*}$ und wir sehen, dass alle Primteiler von $\begin{eqnarray*} u \end{eqnarray*}$ in voller Potenz das $\begin{eqnarray*} x \end{eqnarray*}$ teilen. Also teilt auch $\begin{eqnarray*} u \end{eqnarray*}$ das $\begin{eqnarray*} x \end{eqnarray*}$ .
Mit exakt der gleichen Argumentation sieht man $\begin{eqnarray*} x|u \end{eqnarray*}$ . Es gibt also ein $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} u\cdot k=x \end{eqnarray*}$ und ein $\begin{eqnarray*} j \end{eqnarray*}$ mit $\begin{eqnarray*} x\cdot j=u \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} u=u\cdot k\cdot j \end{eqnarray*}$ und somit $\begin{eqnarray*} j\cdot k=1 \end{eqnarray*}$ .
Die einzige Möglichkeit in den natürlichen Zahlen ist dafür aber $\begin{eqnarray*} k=j=1 \end{eqnarray*}$ .

Gruß,
Reksilat.

09.05.2011, 14:10

kuchen11

Auf diesen Beitrag antworten »

vielen dank, das ist mir nun klar, die erklärung war aber doch etwas komplizierter als ich gedacht hatte, naja jetz hab ichs, nochmal danke
bei dem gleichen beweis stellt sich mir aber leider noch eine frage unglücklich

wenn uy nun ungleich vx ist, dann folgt aus p>a und a(v²x²-u²y²)=p(v²-y²)
uy kongruent zu +- vx mod p

wie man darauf kommt ist mir leider auch nich so ganz klar.
ich dachte mir, dass man dann
p(v²x²-u²y²)>p(v²-y²) annehmen kann und somit v²x²-u²y²>v²-y²
aber wie man auf die kongruenz kommt frag ich mich immer noch

09.05.2011, 15:55

Reksilat

Auf diesen Beitrag antworten »

Mit Abschätzungen wirst Du bei Kongruenzen nicht weit kommen, da Du ja dann die Information über die Teilbarkeit verlierst.

Was Du sagen kannst, ist folgendes: Wenn $\begin{eqnarray*} p>a \end{eqnarray*}$ ist, so ist $\begin{eqnarray*} p \end{eqnarray*}$ mit Sicherheit kein Teiler von $\begin{eqnarray*} a \end{eqnarray*}$ und muss somit den anderen Faktor $\begin{eqnarray*} u^2y^2-v^2x^2 \end{eqnarray*}$ teilen.

Gruß,
Reksilat.

Und meine obige Erklärung ist eigentlich nicht kompliziert, sondern nur etwas lang geworden. Wenn Du Dich ein wenig mehr mit der Thematik beschäftigt hast, wirst Du das auch ziemlich leicht finden.
Augenzwinkern

09.05.2011, 21:09

kuchen11

Auf diesen Beitrag antworten »

hallo, nochmals vielen dank. das war wirklich einfach, da hätte ich auch selbst drauf kommen können.
ich muss mich wirklich noch ein bisschen einarbeiten. ich fang momentan auch eher hinten an und arbeite mich nach vorn durch Augenzwinkern

jetzt stellt sich mir aber nochmal eine frage zu deiner ersten antwort, tut mir leid,
aber warum teilt eine primzahlpotenz das u? die müsste doch eigentlich größer sein als das u oder?

09.05.2011, 21:43

Reksilat

Auf diesen Beitrag antworten »

Aaaahh... Entschuldige bitte. Hammer

Das $\begin{eqnarray*} p \end{eqnarray*}$ in meinem ersten Beitrag ist irgendeine Primzahl die $\begin{eqnarray*} u \end{eqnarray*}$ teilt und hat mit dem $\begin{eqnarray*} p \end{eqnarray*}$ aus der Aufgabenstellung nichts zu tun. Ich editiere das auch gleich mal.
Mir ging es da nur um die Primteiler von $\begin{eqnarray*} u \end{eqnarray*}$ , die halt jeweils in gewisser Potenz das $\begin{eqnarray*} u \end{eqnarray*}$ teilen. Schließlich lässt sich ja jede Zahl als Produkt von Primzahlen darstellen:
$\begin{eqnarray*} u=\prod_{i=1}^mq_i^{t_i} \end{eqnarray*}$ für geeignete $\begin{eqnarray*} m,q_i,t_i\in \mathbb{N} \end{eqnarray*}$

Wird es verständlicher?

22.05.2011, 17:07

kuchen11

Auf diesen Beitrag antworten »

ja kein problem. allerdings frage ich mich nun, waurm ich überhaupt dieses q brauche und nicht einfach sagen kann wenn u|vx und u,v teilerfremd, dann u|x.

achso und ich frage mich, warum ich zu anfangs überhaupt annehme, dass u,v und x,y teilerfremd sind. wieso sind sie das denn?

und nochmal zu der anderen frage. welcher ist denn der andere Faktor $\begin{eqnarray*} u^2y^2-v^2x^2 \end{eqnarray*}$ ? aus welcher gleichung nehme ich das denn?

sorry, für die vielen fragen, aber ich habe das gefühl, je länger ich draufgucke, desto verwirrter bin ich

22.05.2011, 18:02

Reksilat

Auf diesen Beitrag antworten »

Zitat:

ja kein problem. allerdings frage ich mich nun, waurm ich überhaupt dieses q brauche und nicht einfach sagen kann wenn u|vx und u,v teilerfremd, dann u|x.

Das kann man natürlich sagen, aber da Du die Aussage oben nicht verstanden hast, wollte ich es Dir eben ausführlich erklären und deshalb sah es so umfangreich aus. Wenn Dir diese kurze Aussage sinnvoll erscheint, dann ist ja alles bestens.

Zitat:

achso und ich frage mich, warum ich zu anfangs überhaupt annehme, dass u,v und x,y teilerfremd sind. wieso sind sie das denn?

Da $\begin{eqnarray*} p=au^2+bv^2 \end{eqnarray*}$ ist, muss ein gemeinsamer Teiler von $\begin{eqnarray*} u \end{eqnarray*}$ und $\begin{eqnarray*} v \end{eqnarray*}$ ja auch das $\begin{eqnarray*} p \end{eqnarray*}$ teilen, also $\begin{eqnarray*} {\rm ggT}(u,v)\in\{1,p\} \end{eqnarray*}$ .
Angenommen $\begin{eqnarray*} {\rm ggT}(u,v)=p \end{eqnarray*}$ , dann teilt $\begin{eqnarray*} p^2 \end{eqnarray*}$ den Ausdruck $\begin{eqnarray*} au^2+bv^2 \end{eqnarray*}$ , aber $\begin{eqnarray*} p^2 \end{eqnarray*}$ ist mit Sicherheit kein Teiler von $\begin{eqnarray*} p \end{eqnarray*}$ .

Zitat:

und nochmal zu der anderen frage. welcher ist denn der andere Faktor $\begin{eqnarray*} u^2y^2-v^2x^2 \end{eqnarray*}$ ? aus welcher gleichung nehme ich das denn?

Das kommt aus der Gleichung $\begin{eqnarray*} a(v^2x^2-u^2y^2)=p(v^2-y^2) \end{eqnarray*}$ , die Du in Deinem zweiten Beitrag erwähnt hast.

Gruß,
Reksilat.

22.05.2011, 19:45

kuchen11

Auf diesen Beitrag antworten »

Das kommt aus der Gleichung $\begin{eqnarray*} a(v^2x^2-u^2y^2)=p(v^2-y^2) \end{eqnarray*}$ , die Du in Deinem zweiten Beitrag erwähnt hast.

und wie kommt man mit der gleichung darauf, dass p eine der beiden sachen teilen muss?

und dann habe ich noch eine LETZTE frage :
wenn ich nun die kongruenz habe, wie ergibt sich daraus |uy+-vx|=p ?

22.05.2011, 20:13

Reksilat

Auf diesen Beitrag antworten »

Wenn $\begin{eqnarray*} a(v^2x^2-u^2y^2)=p(v^2-y^2) \end{eqnarray*}$ ist, so teilt $\begin{eqnarray*} p \end{eqnarray*}$ den Ausdruck $\begin{eqnarray*} a(v^2x^2-u^2y^2) \end{eqnarray*}$ . Da $\begin{eqnarray*} p \end{eqnarray*}$ eine Primzahl ist, muss es eben mindestens einen der Faktoren teilen.

Wie man aus der Kongruenz auch schon die Gleichheit folgert, sehe ich im Moment nicht und gleich fängt der Polizeiruf an.
Steht da nicht noch was dazu?

Gruß,
Reksilat. Wink

22.05.2011, 20:44

kuchen11

Auf diesen Beitrag antworten »

polizeiruf Augenzwinkern

naja aus der kongruenz und wegen p²>= ab(uy+-vx)² ergibt sich
|uy+-vx|=p, a=b=1 und aux+-bvy=0, steht da.

23.05.2011, 11:01

Reksilat

Auf diesen Beitrag antworten »

Wenn Du die Ungleichung hast, dann ist es klar, denn da p ein Teiler von $\begin{eqnarray*} uy-vx \end{eqnarray*}$ ist, ist $\begin{eqnarray*} (uy-vx)^2\geq p^2 \end{eqnarray*}$ .
Also steht da:
$\begin{eqnarray*} p^2\geq ab(uy+-vx)^2\geq abp^2 \end{eqnarray*}$
Dann muss $\begin{eqnarray*} a=b=1 \end{eqnarray*}$ sein und natürlich kann auch $\begin{eqnarray*} |uy-xv| \end{eqnarray*}$ nicht echt größer als $\begin{eqnarray*} p \end{eqnarray*}$ sein.

24.05.2011, 21:57

kuchen11

Auf diesen Beitrag antworten »

okay das mit dem a=b=1 hatte ich auch daraus gezogen, naja gut okay, jetz hatte ich doch alle fragen zu dem beweis, bei dem ich dachte, er wäre am einfachsten und zu den anderen keine einzige Big Laugh

naja vielen, vielen dank!

Neue Frage »

Antworten »

teilerfremdheit

Verwandte Themen