Teilbarkeitslehre < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:45 Do 25.04.2013 | | Autor: | hubi92 |
| Aufgabe | Es seien a,b,c natürliche Zahlen und ggT(a,b) bezeichne den größten gemeinsamen Teiler von a und b. Zeigen Sie:
a) ggT(ca,cb) = c*(ggT(a,b)
b) Aus c | a und c | b folgt, dass ggT(a/c , b/c) = 1/c*ggT(a,b)
c) ggT(a/ggT(a,b), b/ggT(a,b)) = 1 |
Hallo ihr Lieben!
ich komme bei meiner Aufgabe leider mal wieder nicht weiter und hoffe, dass ihr mir helfen könnt!
Ich weiß, dass ich bei a) den euklidischen Algorithmus anwenden muss.
Dieser lautet:
a=q*b+r1 mit r1<b
b=q2*r1+r2 mit r2<r1
r1=q3*r2+r3 mit r3<r2
rn-1=qn+1*rn+rn+1 mit rn+1<rn
rn=qn+2*rn+1 mit 0<rn+1
ggT(a,b)=ggT(b,r1)
ggt(b,r1)=ggT(r1,r2)
ggT(r1,r2)=ggT(r2,r3)
ggT(rn-1,rn)=ggT(rn,rn-1)
ggT(rn,rn+1)=rn+1
=> ggT(a,b)=rn+1
Jetzt weiß ich aber leider nicht, wie ich das auf meine Aufgabe beziehen kann oder wie ich damit die oben genannten Behauptungen beweisen kann.
Ich hoffe, dass ihr mir helfen könnt! Vielen Dank!
|
|
| |
|
Hallo hubi,
> Es seien a,b,c natürliche Zahlen und ggT(a,b) bezeichne
> den größten gemeinsamen Teiler von a und b. Zeigen Sie:
>
> a) ggT(ca,cb) = c*(ggT(a,b)
> b) Aus c | a und c | b folgt, dass ggT(a/c , b/c) =
> 1/c*ggT(a,b)
> c) ggT(a/ggT(a,b), b/ggT(a,b)) = 1
>
>
> ich komme bei meiner Aufgabe leider mal wieder nicht weiter
> und hoffe, dass ihr mir helfen könnt!
>
> Ich weiß, dass ich bei a) den euklidischen Algorithmus
> anwenden muss.
Woher weißt Du das? Aus Horoskopen oder von übereifrigen Übungsleitern? Oder gar von Kommilitonen, die behaupten, die Aufgabe schon gelöst zu haben?
Man könnte das Lemma von Bézout nutzen, das in engem Zusammenhang mit dem erweiterten euklidischen Algorithmus steht. Aber es geht eigentlich viel einfacher.
> Dieser lautet:
> a=q*b+r1 mit r1<b
> b=q2*r1+r2 mit r2<r1
> r1=q3*r2+r3 mit r3<r2
> rn-1=qn+1*rn+rn+1 mit rn+1<rn
> rn=qn+2*rn+1 mit 0<rn+1
>
> ggT(a,b)=ggT(b,r1)
> ggt(b,r1)=ggT(r1,r2)
> ggT(r1,r2)=ggT(r2,r3)
> ggT(rn-1,rn)=ggT(rn,rn-1)
> ggT(rn,rn+1)=rn+1
Bestimmt nicht. [mm] \ggT{(rn,rn+1)}=1.
[/mm]
> => ggT(a,b)=rn+1
>
> Jetzt weiß ich aber leider nicht, wie ich das auf meine
> Aufgabe beziehen kann oder wie ich damit die oben genannten
> Behauptungen beweisen kann.
Weiß ich auch nicht.
Alle drei Aufgaben gehen recht leicht so:
Sei [mm] g=\ggT{(a,b)} [/mm] und [mm] a=g\alpha,\;\; b=g\beta.
[/mm]
Dann würde ich erst Aufgabe c) lösen und zeigen, dass [mm] \ggT{(\alpha,\beta)}=1 [/mm] ist.
Danach Aufgabe a).
Für Aufgabe b) ist zu zeigen, dass $c|g$. Ab da gehts einfach.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:53 Mo 29.04.2013 | | Autor: | hubi92 |
>
> Woher weißt Du das? Aus Horoskopen oder von übereifrigen
> Übungsleitern? Oder gar von Kommilitonen, die behaupten,
> die Aufgabe schon gelöst zu haben?
>
Das hat mein Übungsleiter gesagt..
> > Dieser lautet:
> > a=q*b+r1 mit r1<b
> > b=q2*r1+r2 mit r2<r1
> > r1=q3*r2+r3 mit r3<r2
> > rn-1=qn+1*rn+rn+1 mit rn+1<rn
> > rn=qn+2*rn+1 mit 0<rn+1
> >
> > ggT(a,b)=ggT(b,r1)
> > ggt(b,r1)=ggT(r1,r2)
> > ggT(r1,r2)=ggT(r2,r3)
> > ggT(rn-1,rn)=ggT(rn,rn-1)
> > ggT(rn,rn+1)=rn+1
>
> Bestimmt nicht. [mm]\ggT{(rn,rn+1)}=1.[/mm]
>
> > => ggT(a,b)=rn+1
> >
Das hatten wir in der Vorlesung.....
>
> Alle drei Aufgaben gehen recht leicht so:
> Sei [mm]g=\ggT{(a,b)}[/mm] und [mm]a=g\alpha,\;\; b=g\beta.[/mm]
>
> Dann würde ich erst Aufgabe c) lösen und zeigen, dass
> [mm]\ggT{(\alpha,\beta)}=1[/mm] ist.
>
> Danach Aufgabe a).
>
> Für Aufgabe b) ist zu zeigen, dass [mm]c|g[/mm]. Ab da gehts
> einfach.
>
> Grüße
> reverend
Danke für deine Antwort! Aber was bedeuten hierbei jetzt alpha und beta? und wie kommst du darauf?
LG
|
|
|
| |
|
> > Alle drei Aufgaben gehen recht leicht so:
> > Sei [mm]g=\ggT{(a,b)}[/mm] und [mm]a=g\alpha,\;\; b=g\beta.[/mm]
> > .....
> > .....
> was bedeuten hierbei jetzt alpha und beta?
Wenn g definiert ist als der größte gemeinsame
Teiler von a und b, dann muss g offenbar wenigstens
einmal ein gemeinsamer Teiler von a und b sein,
d.h.
(1) g ist Teiler von a
(2) g ist Teiler von b
Wie würdest du die Aussagen (1) und (2) denn
formal ausdrücken ?
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:31 Mo 29.04.2013 | | Autor: | hubi92 |
> (1) g ist Teiler von a
> (2) g ist Teiler von b
>
> Wie würdest du die Aussagen (1) und (2) denn
> formal ausdrücken ?
Okay, also sind alpha und beta nur irgendeine beliebige zahl?
das heißt, ich könnte es auch so ausdrücken:
(1) g | a
(2) g | b
g=a*n und g=b*m ??
LG
|
|
|
| |
|
Hallo nochmal,
wozu mache ich es eigentlich vor?
> > (1) g ist Teiler von a
> > (2) g ist Teiler von b
> >
> > Wie würdest du die Aussagen (1) und (2) denn
> > formal ausdrücken ?
>
> Okay, also sind alpha und beta nur irgendeine beliebige
> zahl?
Wenn a und b feststehen und damit auch ihr ggT, sind [mm] \alpha [/mm] und [mm] \beta [/mm] alles andere als beliebig.
> das heißt, ich könnte es auch so ausdrücken:
> (1) g | a
> (2) g | b
>
> g=a*n und g=b*m ??
Natürlich nicht!
Sei a=12, b=22. Dann ist g=ggT(a,b)=2.
Und jetzt?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:54 Mo 29.04.2013 | | Autor: | Marcel |
Hallo,
> Es seien a,b,c natürliche Zahlen und ggT(a,b) bezeichne
> den größten gemeinsamen Teiler von a und b. Zeigen Sie:
>
> a) ggT(ca,cb) = c*(ggT(a,b)
> b) Aus c | a und c | b folgt, dass ggT(a/c , b/c) =
> 1/c*ggT(a,b)
> c) ggT(a/ggT(a,b), b/ggT(a,b)) = 1
> Hallo ihr Lieben!
> ich komme bei meiner Aufgabe leider mal wieder nicht weiter
> und hoffe, dass ihr mir helfen könnt!
>
> Ich weiß, dass ich bei a) den euklidischen Algorithmus
> anwenden muss.
kannst Du - musst Du nicht:
https://matheraum.de/read?i=958663 (klick!)
Du kannst Dir auch dort den ganzen Thread durchlesen. Mit dem euklidischen
Algorithmus bist Du aber schnell fertig:
Man startet diesen ja hier mit
[mm] $$(\*)\;\;\;ca=q*cb+r\,.$$
[/mm]
Dabei ist $q [mm] \in \IN_0$ [/mm] und $0 [mm] \le [/mm] r < [mm] cb\,.$
[/mm]
Weil [mm] $g:=\ggT(a,b)$ [/mm] erfüllt [mm] $g|a\,$ [/mm] und [mm] $g|b\,$ [/mm] folgt $cg|ca$ und [mm] $cg|cb\,.$
[/mm]
Aus [mm] $cg|ca\,$ [/mm] und [mm] $cg|cb\,$ [/mm] folgt aber in [mm] $(\*)$ [/mm] dann, wenn man dort $q:=cg$ wählt, sofort [mm] $r=0\,.$
[/mm]
(Na okay, das ist vielleicht doch zu kurz gesagt, vielleicht besser so: Überlege Dir, dass der [mm] $\ggT(a,b,)$
[/mm]
mithilfe des euklidischen Algorithmus meinetwegen in [mm] $k\,$ [/mm] Schritten gefunden worden wäre. (Im [mm] $k\,$-ten
[/mm]
Schritt sei [mm] $r_k=0$!) [/mm]
Stelle nun die einzelnen Schritte zum Auffinden des [mm] $\ggT(a,b)$ [/mm] denen zum Auffinden von [mm] $\ggT(ca,cb)$ [/mm] direkt
gegenüber, dann folgt das obige.
Beispiel: (1) sei das erste Ergebnis bzgl. des eukl. Alg. bzgl. [mm] $\ggT(a,b)\,:$
[/mm]
(1) [mm] $a=q_1*b+r_1$ [/mm] mit $0 [mm] \le r_1 [/mm] < [mm] b\,.$
[/mm]
Dann ist das Ergebnis (1') bzgl. des eukl. Alg. angewendet auf [mm] $\ggT(ca,cb)$:
[/mm]
(1') [mm] $ca=q_1 cb+cr_1$ [/mm] mit $0 [mm] \le cr_1 [/mm] < [mm] cb\,.$
[/mm]
Im (2) Schritt bzw. im Schritt (2'):
(2) [mm] $b=q_2 r_1+r_2$ [/mm] mit $0 [mm] \le r_2 [/mm] < [mm] r_1$
[/mm]
liefert dann
(2') [mm] $cb=q_2 cr_1+cr_2$ [/mm] mit $0 [mm] \le cr_2 [/mm] < [mm] cr_1$
[/mm]
etc. pp.. Das, was ich oben sagte, ergibt sich dann "im [mm] $k\,$-ten [/mm] Schritt" des Algorithmus... nur die
Teilbarkeitsargumente alleine reichen da natürlich nicht! Also die wirkliche Begründung ist eher das,
was hier in der Klammer steht! Das war vorhin wohl einfach ein "gedanklicher Schnellschuss"!)
Fertig!
P.S. Wenn Du schon den euklidischen Algorithmus "so vermurkst" notierst, dann schreibe
doch bitte wenigstens sowas wie r(n+1) für [mm] $r_{n+1}\,.$ [/mm] Den hattest Du ja grauenvoll hier
notiert - grauenvoll sogar im Sinne von falsch, weil Indizes oft gar nicht wie Indizes aussehen...
Ich meine: Wenn jemand $a3+a4$ schreibt, gehe ich davon aus, dass er [mm] $a*3+a*4=a*(3+4)=7a\,,$
[/mm]
und nicht [mm] $a_3+a_4$ [/mm] meint. Und selbst, wenn aus dem Zusammenhang heraus sowas klar wäre:
Ist dann $an+1$ im Sinne von [mm] $a_n+1$ [/mm] oder [mm] $a_{n+1}$ [/mm] gemeint...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:16 Do 02.05.2013 | | Autor: | hubi92 |
Vielen Dank für eure Hilfe!!
|
|
|
|
