ggT - groeßter gemeinsamer T. < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:03 Fr 11.04.2008 | | Autor: | barsch |
| Aufgabe | Für [mm] a,b\in\IZ\backslash\{0\} [/mm] mit ggT(a,b)=1 berechne
ggT(a+2b,2a+b). |
Hi,
Ich habe erst einmal, um es etwas anschaulcher zu machen, verschiedene Werte für a und b eingesetzt. Der ggT ist entweder 1 oder 3.
Ich wollte es allgemein mit dem euklidischen Algorithmus beweisen, dass [mm] 1,3\in{ggT(a+2b,2a+b)}, [/mm] aber da hängt es. Vielleicht könnt ihr mir weiterhelfen.
1) (2a+b)=2*(a+2b)+(-3b)
2) (a+2b)=(-3b)+(a+5b)
...
Das geht jetzt so weiter. Davon, dass es determiniert ist noch nichts zu sehen. Wo liegt mein Fehler, was kann/muss ich anders machen?
MfG barsch
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:42 Fr 11.04.2008 | | Autor: | canuma |
Ich dachte ich komme zu einem Ergebins, aber die Rechnung wird recht lang. Aber evtl. hilft der Ansatz ja etwas.
ps: Sorry
|
|
|
| |
|
> Für [mm]a,b\in\IZ\backslash\{0\}[/mm] mit ggT(a,b)=1 berechne
>
> ggT(a+2b,2a+b).
> Hi,
>
> Ich habe erst einmal, um es etwas anschaulcher zu machen,
> verschiedene Werte für a und b eingesetzt. Der ggT ist
> entweder 1 oder 3.
>
> Ich wollte es allgemein mit dem euklidischen Algorithmus
> beweisen, dass [mm]1,3\in{ggT(a+2b,2a+b)},[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
aber da hängt es.
> Vielleicht könnt ihr mir weiterhelfen.
>
> 1) (2a+b)=2*(a+2b)+(-3b)
>
> 2) (a+2b)=(-3b)+(a+5b)
>
> ...
>
> Das geht jetzt so weiter. Davon, dass es determiniert ist
> noch nichts zu sehen. Wo liegt mein Fehler, was kann/muss
> ich anders machen?
(Bier-)Idee: Der gesuchte grösste gemeinsame Teiler $x$ von $a+2b$ und $2a+b$ muss sich in der Form $x=c_1\cdot (a+2b)+c_2\cdot(2a+b)$, mit $c_1,c_1\in\IZ$ darstellen lassen: und es handelt sich um die kleinste positive Zahl, die sich auf diese Weise (als ganzzahlige Linearkombination von $a+2b$ und $2a+b$) darstellen lässt. Diese Gleichung lässt sich auf die Form $x=(c_1+2c_2)\cdot a+(2c_1+c_2)\cdot b$ bringen.
Setzen wir nun $c_1+2c_2=d_1$ und $2c_1+c_2=d_2$ so folgt $c_1=-\frac{d_1}{3}+\frac{2d_2}{3}$ und $c_2=\frac{2d_1}{3}-\frac{d_2}{3}$. Daraus möchten wir schliessen, dass $d_1$ und $d_2$ ganzzahlige Vielfache von $3$ sind und daher $\mathrm{ggT}(d_1,d_2)\geq 3$ ist, woraus wegen $\mathrm{ggT}{a,b)=1$ sogleich $\mathrm{ggT}(a+2b,2a+b)=3$ folgen würde.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:20 Di 15.04.2008 | | Autor: | barsch |
Hi,
stimmt, habe das gerade einmal versucht, mit der Linearkombination. Jedoch habe ich am Ende anders argumentiert:
Nach Voraussetzung: ggt(a,b)=1.
Sei [mm] d_0=ggt(a+2b,2a+b)=x\cdot(a+2b)+y\cdot(2a+b)
[/mm]
[mm] =a\cdotx+2b*x+2a*y+b*y=2a*y+2b*x+a*x+b*y=2*(x*a+y*b)+(x*a+y*a)=2*ggt(a,b)+ggt(a,b)=2*1+1=3.
[/mm]
Wie gehe ich aber vor, wenn ich auf diese Weise [mm] ggt(a+b,a^2+b^2) [/mm] berechnen soll?
[mm] d_1=ggt(a+b,a^2+b^2)=x*(a+b)+y*(a^2+b^2)=x*a+x*b+y*a^2+y*b^2=x*a+y*a^2+x*b+y*b^2=ggt(a,a^2)+ggt(b,b^2)
[/mm]
wenn man jedoch anders umstellt:
[mm] d_1=ggt(a+b,a^2+b^2)=x*(a+b)+y*(a^2+b^2)=x*a+x*b+y*a^2+y*b^2=x*a+y*b^2+x*b+y*a^2=ggt(a,b^2)+ggt(b,a^2)
[/mm]
Was bringt mich hier weiter, wenn ich zeigen soll [mm] ggt(a+b,a^2+b^2)=2 [/mm] ?
Oder muss ich hier wieder anders vorgehen?
MfG barsch
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
|
| |
|
Ich zweifle, ob man [mm] ggt(a+b,a^2+b^2) [/mm] wirklich berechnen muss.
Und ich vermute, dass die Antwort einfach immer 1 ist.
Um einer Begründung auf die Spur zu kommen, würde ich den Euklidischen Algorithmus nachzuspielen versuchen...
Gruss Al-Ch.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:47 Di 15.04.2008 | | Autor: | barsch |
Hi,
> Ich zweifle, ob man [mm]ggt(a+b,a^2+b^2)[/mm] wirklich berechnen
> muss.
> Und ich vermute, dass die Antwort einfach immer 1 ist.
setze z.B. a=b=1.
Dann ist [mm] ggt(a+b,a^2+b^2)=ggt(2,2)=2.
[/mm]
Mit dem euklidischer Algorithmus kommt man hier auch nicht weiter!!!
MfG barsch
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:05 Di 15.04.2008 | | Autor: | felixf |
Hallo
> > Ich zweifle, ob man [mm]ggt(a+b,a^2+b^2)[/mm] wirklich berechnen
> > muss.
> > Und ich vermute, dass die Antwort einfach immer 1
> ist.
>
> setze z.B. a=b=1.
>
> Dann ist [mm]ggt(a+b,a^2+b^2)=ggt(2,2)=2.[/mm]
>
> Mit dem euklidischer Algorithmus kommt man hier auch nicht
> weiter!!!
Der ggT von $a + b$ und [mm] $a^2 [/mm] + [mm] b^2$ [/mm] ist gleich dem von $a + b$ und $2 a b$.
Jetzt nimmt man sich eine Primzahl $p$, die den ggT teilt. Sie muss also $2$ teilen, $a$ teilen oder $b$ teilen.
Wenn sie $a$ teilt, so teilt sie $b$ nicht (da teilerfremd), also teilt sie auch $a + b$ nicht, ein Widerspruch. Analog argumentiert man den Fall $p [mm] \mid [/mm] b$. Also muss $p = 2$ sein.
Hier sieht man auch gleich, wann $p = 2$ auftreten kann: naemlich nur dann, wenn $a + b$ gerade ist, und das kann nur sein, wenn sowohl $a$ als auch $b$ ungerade sind, und in dem Fall ist der ggT 2. Andernfalls ist der ggT 1.
LG Felix
|
|
|
| |
|
Sorry, meine frühere Vermutung, dass der ggT immer eins ist, war natürlich Schrott.
Probieren zeigt, dass wohl gilt:
[mm] ggT(a+2b,2a+b)=\left\{\begin{matrix}
3, & \mbox{falls }\mbox{(a-b)mod 3 = 0} \\
1, & \mbox{sonst }
\end{matrix}\right. [/mm]
Teilbarkeit durch 3 scheint also eine Rolle zu spielen.
Im Moment seh ich leider auch nicht weiter.
Al-Ch.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:19 Di 15.04.2008 | | Autor: | felixf |
Hallo,
> Sorry, meine frühere Vermutung, dass der ggT immer eins
> ist, war natürlich Schrott.
> Probieren zeigt, dass wohl gilt:
>
> [mm]ggT(a+2b,2a+b)=\left\{\begin{matrix}
3, & \mbox{falls }\mbox{(a-b)mod 3 = 0} \\
1, & \mbox{sonst }
\end{matrix}\right.[/mm]
ja, genauso ist es. Laesst sich mit der gleichen Methode beweisen wie in meiner anderen Antwort in diesem Thread.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:42 Di 15.04.2008 | | Autor: | barsch |
Hi,
vielen Dank. Deine Antwort hat mir sehr weitergeholfen.
MfG barsch
|
|
|
|
