Euklidischer Algorithmus < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
Es soll folgende Beziehung bewiesen werden: [mm] $\ggT\left(a,b\right) [/mm] = [mm] \ggT\left(b, a \mod b \right)$. [/mm] Das Problem ist, daß mir hier nicht einleuchten will, wieso das funktioniert. $a [mm] \mod [/mm] b$ bewirkt, daß beim nächsten rekursiven Aufruf der zweite Parameter kleiner ist als der erste. Daß der ggT-Algorithmus schließlich terminieren muß, ist auch klar, weil dadurch beide Parameter immer kleiner werden bis wir schließlich bei [mm] $\ggT\left(a, 0\right)$ [/mm] ankommen und das ist [mm] $a\!$, [/mm] weil die 0 durch jede beliebige ganze Zahl ohne Rest teilbar ist, und die größte Zahl, die eine beliebige ganze Zahl teilt, nunmal gerade diese Zahl selbst ist.
Trotzdem kann ich nicht so ganz nachvollziehen, das dieser "rekursive Abstieg" immer zum ggT der beiden Zahlen führt.
Viele Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:49 Di 02.08.2005 | | Autor: | DaMenge |
Hallo Karl,
das ist relativ simpel:
angenommen du hast zwei Zahlen a und b und oBdA sei a<b , dann gilt ja für eine natürlich Zahl n :
a=n*b + (a mod b)
d.h. alle gemeinsamen Teiler von a und b muss auch Teiler von (a mod b) sein, denn sonst wäre es (durch die Summe) kein Teiler von a.
Ich hoffe dir leuchtet es genauso ein, wie mir gerade..
viele Grüße
DaMenge
|
|
|
| |
|
Hallo DaMenge,
Vielen Dank für die Antwort!
> angenommen du hast zwei Zahlen a und b und oBdA sei a<b ,
> dann gilt ja für eine natürlich Zahl n :
> a=n*b + (a mod b)
Sehe ich das richtig, daß n dann immer 0 sein muß? Wegen a < b gilt doch immer $a = n*b + [mm] \left( a \mod b \right) [/mm] = n*b + a [mm] \gdw [/mm] 0 = nb [mm] \gdw [/mm] n = 0$. Ist das denn so überhaupt erwünscht?
> d.h. alle gemeinsamen Teiler von a und b muss auch Teiler
> von (a mod b) sein, denn sonst wäre es (durch die Summe)
> kein Teiler von a.
>
> Ich hoffe dir leuchtet es genauso ein, wie mir gerade..
Im Moment noch nicht, ich verstehe noch nicht so richtig, was ich mit der obigen Gleichung anfangen soll. Ich sehe natürlich, daß sie eine gewisse Ähnlichkeit zu der rekursiven Beziehung des Algorithmus besitzt aber mehr auch nicht, oder?
Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:24 Di 02.08.2005 | | Autor: | Stefan |
Lieber Karl!
Die Voraussetzung $a<b$ tut hier nichts zur Sache, vergiss sie einfach wieder. 
Ist $u:=ggT(a,b)$, dann teilt $u$ mit $a$ und $b$ auch jede ganzzahlige Linearkombination von $a$ und $b$, also auch $a [mm] \pmod{b}$. [/mm] Somit teilt $u$ die beiden Zahlen $b$ und $a [mm] \pmod{b}$ [/mm] und damit auch
[mm] $v:=ggT(b,a\pmod{b})$.
[/mm]
Zu zeigen bleibt, dass umgekehrt auch $v$ $u$ teilt, denn dann gilt: $u=v$. Aber hier zieht das gleiche Argument:
$v$ teilt mit $b$ und $a [mm] \pmod{b}$ [/mm] auch jede ganzzahlige Linearkombination von $b$ und $a [mm] \pmod{b}$, [/mm] also auch $a$. Damit teilt $v$ sowohl $b$ als auch $a$, und damit auch
$u=ggT(a,b)$.
Jetzt klar? 
Liebe Grüße
Stefan
|
|
|
| |
|
Hallo Stefan,
> also auch [mm]a \pmod{b}[/mm].
Ich habe das jetzt an einem Beispiel probiert und es stimmt: $u = 5, a = [mm] 175\!$ [/mm] und $b = [mm] 30\!$ [/mm] und $175 [mm] \pmod{30}=25$, [/mm] und tatsächlich [mm] $u\!$ [/mm] teilt diesen Rest aber eine allgemeine Erklärung konnte ich dafür bisher nicht finden.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:18 Di 02.08.2005 | | Autor: | Stefan |
Lieber Karl!
Wenn dir das hier klar ist:
> > Ist [mm]u:=ggT(a,b)[/mm], dann teilt [mm]u[/mm] mit [mm]a[/mm] und [mm]b[/mm] auch jede
> > ganzzahlige Linearkombination von [mm]a[/mm] und [mm]b[/mm],
dann müsste dir doch auch das hier klar sein:
> > also auch [mm]a \pmod{b}[/mm],
denn $(a [mm] \pmod{b})$ [/mm] ist doch eine ganzzahlige Linearkombination von $a$ und $b$, denn
$a [mm] \pmod{b} [/mm] = [mm] \underbrace{a - nb}_{\mbox{\scriptsize ganzzahlige Linearkombination von a und b}}$, [/mm]
wenn
$a = nb + (a [mm] \pmod{b})$.
[/mm]
Was genau ist jetzt noch unklar? ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Liebe Grüße
Stefan
|
|
|
| |
|
Hallo Zusammen,
Offenbar habe ich doch nur den ersten Teil des Beweises mit den Linearkombinationen verstanden. Zwar ist mir jetzt klar, daß der Euklidische Algorithmus einen gemeinsamen Teiler zweier ganzer Zahlen liefert, aber muß dieser Teiler denn unbedingt der Größte sein? Nehmen wir als Beispiel 70 und 30; Deren ggT ist 10, aber ein gT von diesen beiden Zahlen ist 2. Mit der Argumentation über Linearkombinationen von vorhin, sage ich nun 2 teilt 70 und 30, also auch 30 und 10, also auch 10. (Ich weiß, ich habe gerade den Euklidischen Algorithmus ausgeführt und denn ggT bestimmt, aber das kann ja auch nur "Zufall" gewesen sein. ). Ich will jedenfalls nur sagen, daß die Argumentation über Linearkombinationen für jeden gT von [mm] $a\!$ [/mm] und [mm] $b\!$ [/mm] anwendbar ist. Es könnte also zwei Zahlen [mm] $a_1$ [/mm] und [mm] $b_1$ [/mm] geben für die der Algo mal einen [m]\operatorname{GT} _{a_1,b_1} \ni \operatorname{gT} \ne \ggT\left( a_1,b_1 \right)[/m] bestimmt und dann kann er für andere zwei Zahlen [mm] $a_2$ [/mm] und [mm] $b_2$ [/mm] doch den [mm] $\ggT\left(a_2,b_2\right) \in \operatorname{GT}_{a_2,b_2}$ [/mm] bestimmen (das wäre dann Zufall), wobei [mm] $\operatorname{GT}_{a,b}$ [/mm] die Menge aller gemeinsamer Teiler von $a, b [mm] \in \IZ$ [/mm] sein soll.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:45 Mi 03.08.2005 | | Autor: | DaMenge |
Hi,
wir hatten doch schon festgestellt, wenn wir die zwei Schritte:
[mm] ggt(a_1 [/mm] , [mm] b_1 [/mm] ) und [mm] ggT(a_2 [/mm] , [mm] b_2) [/mm] haben,
wobei [mm] $a_2=b_1$ [/mm] und [mm] b_2=(a_1 [/mm] mod [mm] b_1 [/mm] )
Dann gilt immer, dass der ggT Teiler der [mm] b_i [/mm] ist (denn JEDER gT ist Teiler davon),
und weiterhin gilt [mm] $b_{i+1} [/mm] < [mm] b_i$ [/mm] , also ist irgendwann [mm] $b_j=ggT(a,b)$ [/mm]
dies erkennt man dann daran, dass dann [mm] $b_{j+1}=0$ [/mm] ist...
Also zusammenfassend: ALLE gemeinsamen Teiler bleiben erhalten und die b's werden irgendwann zum ggT, weil sie echt kleiner werden.
Deshalb wird der ggT tatsächlich erreicht.
P.S : dies ist keine Antwort, denn eure Teildiskussion benutzt eine andere, technischere Schreibweise
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:04 Mi 03.08.2005 | | Autor: | Stefan |
Lieber Karl!
Ich glaube du hast dir einen Teil meiner Argumentation noch nicht so richtig verinnerlicht , daher wiederhole ich ihn noch einmal.
Wir hatten ja:
$a=n [mm] \cdot [/mm] b + (a [mm] \pmod{b})$.
[/mm]
Dann haben wir argumentiert, dass $ggT(a,b)$ mit $a$ und $b$ auch $a [mm] \pmod{b}$ [/mm] teilt (als ganzzahlige Linearkombination), und damit auch $ggT(b,a [mm] \pmod{b})$.
[/mm]
Aber aus der gleichen Gleichung folgt auch (da $a$ eine ganzzahlige Linearkombination von $b$ und $a [mm] \pmod{b}$ [/mm] ist), dass $ggT(b,a [mm] \pmod{b})$ [/mm] mit $b$ und $a [mm] \pmod{b}$ [/mm] auch $a$ teilt, und daher auch $ggT(a,b)$.
Somit teilt $ggT(a,b)$ die Zahl $ggT(b, a [mm] \pmod{b})$ [/mm] und umgekehrt. Aber zwei ganze Zahlen, die sich gegenseitig teilen und beide positiv sind, müssen gleich sein.
Jetzt klar?
Man kann es sich auch (einfacher) so überlegen wie Andreas, aber so wie oben ist es in jedem Fall auch korrekt.
Liebe Grüße
Stefan
|
|
|
| |
|
Hallo Stefan,
Ich habe jetzt vergeblich versucht deinen Widerspruchsbeweis nachzuvollziehen, ich scheitere an der abschließenden Begründung, das [mm] $\ggT(a,b)$ [/mm] den [mm] $\ggT(b, [/mm] a [mm] \pmod{b})$ [/mm] teilt.
@DaMenge: Deine Argumentation erinnert mich an die Induktion. Insbesondere, weil Du am Schluß mit [mm] $\ggT(b, [/mm] 0)$ argumentierst:
[m]\underline{\texttt{Induktionsanfang }(b = 0):}[/m]
[mm] $\ggT\left(a, 0\right) [/mm] = a$, denn 0 ist durch jede Zahl teilbar, und die größte Zahl, die a restlos teilt, ist a selbst.
Angenommen [mm] $\ggT(a, [/mm] b)$ ist in der Tat der größte gemeinsame Teiler für zwei beliebige ganze Zahlen [mm] $a\!$ [/mm] und [mm] $b\!$, [/mm] dann machen wir den ...
[m]\underline{\texttt{Induktionsschritt }(b \leadsto b+1):}[/m]
[mm] $\ggT\left(a,b+1\right) [/mm] = [mm] \ggT\left(b+1, a\right) [/mm] = [mm] \ggT\left(a, \left(b+1\right) \pmod{a} \right) [/mm] = [mm] \ggT\left(a, \left(\left( b \pmod{a}\right) + 1 \right) \pmod{a}\right)$
[/mm]
Zu einem Punkt, wo man die Induktionsannahme anwenden könnte, bin ich zwar nicht gekommen, aber es leuchtet irgendwie schon ein, daß das zum Induktionsanfang führen muß, weil die 1 hier nicht verschwindet sondern bis zum Schluß "mitgeschleppt" wird (vermute ich jetzt mal) und am Ende ist dann gerade diese 1 der gesuchte ggT oder aber sie ist ein Summand einer Summe, die der gesuchte ggT ist.
Danke für eure Hilfe!
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:23 Mi 03.08.2005 | | Autor: | Stefan |
Lieber Karl!
Ich mache doch gar keinen Widerspruchsbeweis. Ich zeige, dass $ggT(a,b)=ggT(b, [mm] a\pmod{b})$ [/mm] gilt, indem ich zeige, dass diese beiden ganzen Zahlen sich gegenseitig teilen (und damit gleich sind).
Eine Zahl $u$ teilt den größten gemeinsamen Teiler $ggT(a,b)$ zweier Zahlen genau dann, wenn $u$ sowohl $a$ als auch $b$ teilt. Dies folgt unmittelbar aus der Definition des größten gemeinsamen Teilers.
Nun teilt ja $ggT(a,b)$ offenbar $b$ (nach Definition von $ggT(a,b)$). $ggT(a,b)$ teilt ebenso $a$. Weiterhin hatten wir uns überlegt, dass $ggT(a,b)$ mit $a$ und $b$ auch jede ganzzahlige Linearkombination dieser beiden ganzen Zahlen teilt, also auch $a [mm] \pmod{b}$.
[/mm]
Wenn aber nun $ggT(a,b)$ sowohl $b$ als auch $a [mm] \pmod{b}$ [/mm] teilt, dann nach der obigen Bemerkung auch den größten gemeinsamen Teiler dieser beiden ganzen Zahlen, also auch $ggT(b,a [mm] \pmod{b})$.
[/mm]
Genauso überlegt man sich, dass $ggT(b, [mm] a\pmod{b})$ [/mm] auch $ggT(a,b)$ teilt.
Zur Definition des größten gemeinsamen Teilers:
Der $ggT(a,b)$ zweier ganzer Zahlen $a$ und $b$ ist die eindeutig bestimmte nichtnegative ganze Zahl mit den beiden folgenden Eigenschaften
1) $ggT(a,b)|a$ und $ggT(a,b)|b$
2) Ist $d [mm] \in \IZ$ [/mm] mit $d|a$ und $d|b$, dann gilt auch: $d|ggT(a,b)$.
Und 2) haben wir oben ausgenutzt.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:21 Mi 03.08.2005 | | Autor: | Karl_Pech |
Hallo Stefan,
Ich habe die Argumentation jetzt verstanden. Wir betrachten also den [mm] $\ggT\left(a,b\right)$ [/mm] für $a,b [mm] \in \IZ$. [/mm] Nach dem 1ten Teil der Definition teilt diese Zahl [mm] $a\!$ [/mm] und [mm] $b\!$. [/mm] Nun können wir [mm] $a\!$ [/mm] aber folgendermaßen darstellen: $a = bn + a - [mm] bn\!$ [/mm] für eine geeignete natürliche Zahl [mm] $n\!$. [/mm] Durch diese Darstellung hat sich natürlich nichts geändert. Wegen dem 1ten Teil der Definition ist klar, daß [mm] $\ggT\left(a,b\right)$ [/mm] auch $bn + a - [mm] bn\!$ [/mm] teilt. Das folgt aber auch schon aus der Gleichheit. Ich definiere mal: [m]n: = \left\lfloor {\left| {\tfrac{a}{b}} \right|} \right\rfloor[/m]. Insgesamt erhalten wir damit gerade die Modulo-Operation, weil wir jetzt eine ganzzahlige Division vornehmen (nach unten runden) und durch die Multiplikation mit dem Teiler (nach dem Runden) und der anschließenden Subtraktion erhalten wir gerade den Rest.) Also schreiben wir das jetzt so:
$a = bn + a [mm] \pmod{b}$
[/mm]
Vergessen wir jetzt für einen Augenblick die obige Darstellung und stellen uns stattdessen die Frage, was der ggT von [mm] $b\!$ [/mm] und $a [mm] \pmod{b}$ [/mm] ist? Jetzt erinnern wir uns wieder an die obige Darstellung. Wegen dem 1ten Teil der Definition teilt [mm] $\ggT\left(b, a \pmod{b}\right)$ $b\!$ [/mm] und $a [mm] \pmod{b}$ [/mm] und wegen der Gleichheit auch [mm] $a\!$, [/mm] ist also Teiler von [mm] $a\!$ [/mm] und [mm] $b\!$. [/mm] Nach dem zweiten Teil der Definition teilt er also [mm] $\ggT\left(a,b\right)$, [/mm] denn ein ggT ist ja nichts anderes als ein Produkt aller gemeinsamen gTs. Und wieder wegen der obigen Gleichheit teilt der [mm] $\ggT\left(a,b\right)$ [/mm] auch [mm] $b\!$ [/mm] und $a [mm] \pmod{b}$. [/mm] Aber das ist ja gerade der ggT, von dem wir vorher ausgegangen sind, und ebenfalls nach dem 2ten Teil der Definition teilt [mm] $\ggT\left(a,b\right)$ [/mm] also [mm] $\ggT\left(b,a \pmod{b}\right)$. $\square$
[/mm]
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:55 Do 04.08.2005 | | Autor: | Karl_Pech |
Hallo Stefan,
Vielen Dank für die Hilfe!
Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:09 Di 02.08.2005 | | Autor: | DaMenge |
AAAAAAAARRRGGGHHHH !!
ich meinte natürlich oBdA a>b , denn dann ist a=n*b + (a mod b) .
dann ist ein Teiler t von a, der zugleich Teiler von b ist sicher auch Teiler von n*b
Weil aber a=x+y und t Teiler von x ist, muss er auch Teiler von y sein, sonst wäre er kein Teiler von a.
Also jeder gemeinsame Teiler von a und b ist auch gemeinsamer Teiler von b und (a mod b), damit insbesondere auch der größte...
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:58 Di 02.08.2005 | | Autor: | Karl_Pech |
Hallo DaMenge, Hallo Stefan,
Danke für die Hilfe, insbesondere auch für die andere Darstellung des mod-Operators (das war der nötige Denkanstoss): $a [mm] \pmod{b} :\gdw \exists [/mm] n [mm] \in \IN: [/mm] a - nb$. [mm] $\ggT\left( a,b \right)$ [/mm] teilt [mm] $a\!$ [/mm] und [mm] $b\!$ [/mm] also auch [mm] $a+b\!$ [/mm] wegen dem Distributivgesetz, also auch $a - [mm] bn\!$ [/mm] für eine natürliche Zahl [mm] $n\!$ [/mm] wegen dem Distributivgesetz; Man kann also ggT ausklammern.
Was macht also der Euklidische Algorithmus? Die Idee ist eine rekursive Beziehung anhand der Linearkombinationseigenschaften des ggT zu konstruieren. Teilt der ggT [mm] $a\!$ [/mm] und [mm] $b\!$, [/mm] dann teilt er auch $a - [mm] bn\!$; [/mm] Dann nehmen wir [mm] $b\!$ [/mm] und [mm] $a-bn\!$ [/mm] als neue Ausgangskomponenten u.s.w. .
Der Euklidische Algorithmus ist also eine geschickte Ausnutzung des Distributivgesetzes.
Vielen Dank euch Beiden!
|
|
|
|
![[huepf]](/images/smileys/huepf.gif "[huepf]"){kind=small}
