ggT < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:02 Do 20.01.2011 | | Autor: | ella87 |
| Aufgabe | Es seien a,b zwei natürliche Zahlen mit ggT(a,b)=1.
Bestimmen Sie ggT(ab,a+b). |
irgendwie komm ich nicht so richtig weiter, bzw. nur auch ne blöd aussehende Lösung...
ich habe ggT(a,b)=xa+yb
und ggT(a,b)*kgV(a,b)=ab
mach habe ich im Skript nicht gefunden.
also:
ggT(ab,a+b) = xab+y(a+b) = xab+ya+yb = xab+ya+yb+xa-xa
= xab+(xa+yb)+ya-xa = xab+1+a(y-x)
am elegantesten sieht dann vermutlich das aus:
ggT(ab,a+b)= x kgV(a,b) + ggT(a,b) + a(y-x)
aber ich glaub das geht besser. ich weiß auch nicht ob ich annehmen kann, dasa x und y von ggT(a,b)=xa+yb die selben sind wie bei ggT(ab,a+b) = xab+y(a+b)??
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:41 Do 20.01.2011 | | Autor: | felixf |
Moin!
> Es seien a,b zwei natürliche Zahlen mit ggT(a,b)=1.
> Bestimmen Sie ggT(ab,a+b).
> irgendwie komm ich nicht so richtig weiter, bzw. nur auch
> ne blöd aussehende Lösung...
>
> ich habe ggT(a,b)=xa+yb
> und ggT(a,b)*kgV(a,b)=ab
> mach habe ich im Skript nicht gefunden.
>
> also:
> ggT(ab,a+b) = xab+y(a+b) = xab+ya+yb = xab+ya+yb+xa-xa
> = xab+(xa+yb)+ya-xa = xab+1+a(y-x)
> am elegantesten sieht dann vermutlich das aus:
> ggT(ab,a+b)= x kgV(a,b) + ggT(a,b) + a(y-x)
>
> aber ich glaub das geht besser.
Ja.
> ich weiß auch nicht ob ich
> annehmen kann, dasa x und y von ggT(a,b)=xa+yb die selben
> sind wie bei ggT(ab,a+b) = xab+y(a+b)??
Sind sie im Allgemeinen nicht.
Geh doch so vor: sei $p$ ein Primteiler von $a b$. Kann $p$ ein Teiler von $a + b$ sein? Was folgt daraus fuer $ggT(a b, a + b)$?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:05 Fr 21.01.2011 | | Autor: | ella87 |
Hi!
> Geh doch so vor: sei [mm]p[/mm] ein Primteiler von [mm]a b[/mm]. Kann [mm]p[/mm] ein
> Teiler von [mm]a + b[/mm] sein? Was folgt daraus fuer [mm]ggT(a b, a + b)[/mm]?
das ist gut!
[mm]p|ab[/mm], da ggT(a,b)=1 sind a und b teilerfremd also hat man für p genau vier Möglichkeiten: 1, ab, a, b
a teilt a+b nicht, weil a b nicht teilt
b teilt a+b nicht, weil b a nicht teilt
ab teilt a+b nicht, zumindest nicht im Allgemeinen (reicht hier ein Gegenbeispiel?)
also bleibt nur die 1
stimmt das?
|
|
|
| |
|
Hallo Ella,
das Ergebnis stimmt, aber der Weg dahin nicht.
Nimm mal a=3*17=51 und b=5*11=55. Dann ist ggT(a,b)=1
Felix meinte nun dies: betrachte mal einen der Primteiler von a oder b, also die 3,5,11 oder 17.
Ist [mm] ab [/mm] durch diese Zahl teilbar? Ja.
Ist a+b durch diese Zahl teilbar?
Das musst Du jetzt beantworten, aber die Antwort ist eigentlich einfach.
Zu Deinem Ansatz:
> Hi!
> > Geh doch so vor: sei [mm]p[/mm] ein Primteiler von [mm]a b[/mm]. Kann [mm]p[/mm]
> ein
> > Teiler von [mm]a + b[/mm] sein? Was folgt daraus fuer [mm]ggT(a b, a + b)[/mm]?
>
>
> das ist gut!
> [mm]p|ab[/mm], da ggT(a,b)=1 sind a und b teilerfremd also hat man
> für p genau vier Möglichkeiten: 1, ab, a, b
Hier stimmt es schon nicht. Du könntest sehr viel mehr Möglichkeiten haben, im obigen Beispiel mit nur je zwei Primfaktoren wären es 1,3,5,11,15,17,33,51,55,85,165,187,255,561,935,2805.
> a teilt a+b nicht, weil a b nicht teilt
> b teilt a+b nicht, weil b a nicht teilt
Diese beiden Folgerungen sind allerdings richtig, und im Prinzip geht es mit einem allgemeinen Primteiler ganz ähnlich.
> ab teilt a+b nicht, zumindest nicht im Allgemeinen (reicht
> hier ein Gegenbeispiel?)
Nein, ein Gegenbeispiel reicht definitiv nicht. Für ggT(a,b)=1 gibt es nur einen einzigen Fall, in dem ab auch a+b teilt: a=b=1.
> also bleibt nur die 1
> stimmt das?
Wie gesagt: Ergebnis richtig, Weg falsch.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:48 Fr 21.01.2011 | | Autor: | ella87 |
> Hallo Ella,
>
> das Ergebnis stimmt, aber der Weg dahin nicht.
> Nimm mal a=3*17=51 und b=5*11=55. Dann ist ggT(a,b)=1
>
> Felix meinte nun dies: betrachte mal einen der Primteiler
> von a oder b, also die 3,5,11 oder 17.
>
> Ist [mm]ab[/mm] durch diese Zahl teilbar? Ja.
> Ist a+b durch diese Zahl teilbar?
> Das musst Du jetzt beantworten, aber die Antwort ist
> eigentlich einfach.
>
> Zu Deinem Ansatz:
>
dein Gegenbeispiel hat mich überzeugt, war ein bisschen kurz gedacht...
ich habe also folgende Primfaktorzerlegungen:
[mm]a=\produkt_{i=1}^{n}p_i[/mm] und [mm]b=\produkt_{j=1}^{n}q_j[/mm] wobei gilt [mm] p_i \not= q_j[/mm] [mm]\forall i, j \in \IN[/mm]
dann ist [mm]ab = \produkt_{i=1}^{n}p_i \produkt_{j=1}^{n}q_j[/mm] und [mm]a+b = \produkt_{i=1}^{n}p_i + \produkt_{j=1}^{n}q_j[/mm]
[mm]ab[/mm] hat also die Teiler [mm]p_i[/mm] und [mm]q_i[/mm]
[mm]a+b[/mm] hat bestimmt auch viele Teiler, aber keiner davon ist [mm]p_i[/mm] oder [mm]q_i[/mm], weil man einer Teiler ja quasi ausklammern kann und da a und b teilerfremd sind kann man keinen Teiler von den Teilern von a und b nehmen. (verwirrend ausgedrückt)
wir hatten da mal ne Regel:
"falls [mm]a|b[/mm] und [mm]a|c[/mm], dann [mm]a|b+c[/mm]"
hilft mir hier nicht weiter, weil wenn/dann-Relation und nicht Äquivalenz, oder?
|
|
|
| |
|
Hallo nochmal,
> dein Gegenbeispiel hat mich überzeugt, war ein bisschen
> kurz gedacht...
>
> ich habe also folgende Primfaktorzerlegungen:
> [mm]a=\produkt_{i=1}^{n}p_i[/mm] und [mm]b=\produkt_{j=1}^{n}q_j[/mm] wobei
> gilt [mm]p_i \not= q_j[/mm] [mm]\forall i, j \in \IN[/mm]
>
> dann ist [mm]ab = \produkt_{i=1}^{n}p_i \produkt_{j=1}^{n}q_j[/mm]
> und [mm]a+b = \produkt_{i=1}^{n}p_i + \produkt_{j=1}^{n}q_j[/mm]
>
> [mm]ab[/mm] hat also die Teiler [mm]p_i[/mm] und [mm]q_i[/mm]
Ja, schon gut. So viel Aufwand ist gar nicht nötig.
Mach einfach einen Widerspruchsbeweis:
Sei t=ggT(ab,a+b)>1
Dann gibt es drei Fälle: t|a, t|b oder t=cd mit c|a, d|b
Für die ersten beiden ist leicht zu zeigen, dass t kein Teiler von a+b ist, und für den dritten Fall ist es eigentlich nicht viel schwieriger.
In der Tat würde es reichen, einen echten Teiler von t zu untersuchen, der entweder a oder b teilt - eben der Vorschlag von Felix vorhin.
> [mm]a+b[/mm] hat bestimmt auch viele Teiler, aber keiner davon ist
> [mm]p_i[/mm] oder [mm]q_i[/mm], weil man einer Teiler ja quasi ausklammern
> kann und da a und b teilerfremd sind kann man keinen Teiler
> von den Teilern von a und b nehmen. (verwirrend
> ausgedrückt)
Hm, ja. Aber die Idee ist goldrichtig.
> wir hatten da mal ne Regel:
> "falls [mm]a|b[/mm] und [mm]a|c[/mm], dann [mm]a|b+c[/mm]"
> hilft mir hier nicht weiter, weil wenn/dann-Relation und
> nicht Äquivalenz, oder?
Diese Regel hilft hier nicht, aber Du brauchst eine ganz ähnliche:
"falls a|b, aber nicht a|c, dann auch nicht a|b+c"
Sie ist nicht schwierig herzuleiten.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:06 Fr 21.01.2011 | | Autor: | ella87 |
danke soweit!
das mach ich dann morgen in Ruhe!
Gute Nacht!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:43 Do 20.01.2011 | | Autor: | Sigma |
Hallo Ella87,
hab mich mal bei wikipedia schlau gemacht. Aber keine Ahnung was ihr verwenden dürft.
Es gilt: [mm]ggT(a*b,m)=ggT(a,m)*ggT(b,m)[/mm]
für teilerfremde Zahlen a und b.
Und [mm]ggT(a+m*b,b)=ggT(a,b)[/mm]
Nun in deinem Fall:
$ggT(a*b,a+b)=ggT(a,a+b)*ggT(b,a+b)=ggT(a,a+1*b)*ggT(b,a+1*b)=2*ggt(a,b)$
mfg sigma
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:45 Do 20.01.2011 | | Autor: | felixf |
Moin!
> hab mich mal bei wikipedia schlau gemacht. Aber keine
> Ahnung was ihr verwenden dürft.
>
> Es gilt: [mm]ggT(a*b,m)=ggT(a,m)*ggT(b,m)[/mm]
> für teilerfremde Zahlen a und b.
> Und [mm]ggT(a+m*b,b)=ggT(a,b)[/mm]
>
> Nun in deinem Fall:
>
> [mm]ggT(a*b,a+b)=ggT(a,a+b)*ggT(b,a+b)=ggT(a,a+1*b)*ggT(b,a+1*b)=2*ggt(a,b)[/mm]
Du meinst wohl eher:
[mm]ggT(a*b,a+b)=ggT(a,a+b)*ggT(b,a+b)=ggT(a,1*a+b)*ggT(b,a+1*b)=ggt(a,b)^2[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:50 Do 20.01.2011 | | Autor: | Sigma |
Danke felixf,
war wohl doch ein Bier zuviel. Hicks;)
Aber der Grundgedanke ist doch richtig. Und das überwiegt meine Flüchtigkeitsfehler.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:09 Fr 21.01.2011 | | Autor: | ella87 |
danke für die Wikipedia-Idee. Da hab ich auch geguckt und das haben wir alles nicht genacht. Voll dämlich, wir haben nur ggT(a,b)=xa+yb! Eigentlich lächerlich!
aber danke!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:19 Fr 21.01.2011 | | Autor: | felixf |
Moin!
> danke für die Wikipedia-Idee. Da hab ich auch geguckt und
> das haben wir alles nicht genacht. Voll dämlich, wir haben
> nur ggT(a,b)=xa+yb! Eigentlich lächerlich!
Nein, laecherlich ist das nicht. Die Bezout-Gleichung ist eins der maechtigsten Hilfsmittel.
Die hier verwendeten Aussagen bei Wikipedia sind viel einfacher zu beweisen als diese Darstellung mit $x$ und $y$.
LG Felix
|
|
|
|
