www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Lineare Algebra" - Euklidischer Algorithmus
Euklidischer Algorithmus < Lineare Algebra < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Lineare Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Euklidischer Algorithmus: ggT-Eigenschaft
Status: (Frage) beantwortet Status 
Datum: 18:47 Di 02.08.2005
Autor: Karl_Pech

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



        
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Euklidischer Algorithmus: n = 0?
Status: (Frage) beantwortet Status 
Datum: 21:13 Di 02.08.2005
Autor: Karl_Pech

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




Bezug
                        
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:00 Di 02.08.2005
Autor: Karl_Pech

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



Bezug
                                        
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
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]

Liebe Grüße
Stefan


Bezug
                                                
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:19 Mi 03.08.2005
Autor: Karl_Pech

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



Bezug
                                                        
Bezug
Euklidischer Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                                        
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                        
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:19 Mi 03.08.2005
Autor: Karl_Pech

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



Bezug
                                                                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                        
Bezug
Euklidischer Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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



Bezug
                                                                                
Bezug
Euklidischer Algorithmus: Super!
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:55 Do 04.08.2005
Autor: Stefan

Lieber Karl!

Es freut mich sehr, dass du den Beweis jetzt verstanden hast. [huepf]

Nur eine kleine Bemerkung:

> denn ein ggT ist ja
> nichts anderes als ein Produkt aller gemeinsamen gTs.

Das stimmt so nicht, aber ich weiß schon, was du meinst. ;-)

Liebe Grüße
Stefan

Bezug
                                                                                        
Bezug
Euklidischer Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:04 Do 04.08.2005
Autor: Karl_Pech

Hallo Stefan,


> > denn ein ggT ist ja
> > nichts anderes als ein Produkt aller gemeinsamen gTs.
>
> Das stimmt so nicht, aber ich weiß schon, was du meinst.
> ;-)


Ich scheine im oben Zitierten etwas Anderes gesagt zu haben, als ich eigentlich wollte, oder? Aber es gilt doch z.B.: 30 = 2*3*5 und 40 = 2*2*2*5. Die gemeinsamen Teiler sind hier 2 und 5. Das Produkt dieser Teiler ist 10, was ja gerade der ggT von 30 und 40 ist, und was habe ich dann oben gesagt? Kannst Du mir eventuell ein Gegenbeispiel geben? Danke! :-)



Viele Grüße
Karl



Bezug
                                                                                                
Bezug
Euklidischer Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:30 Do 04.08.2005
Autor: Stefan

Lieber Karl!

> Also, irgendwie verstehe ich das jetzt nicht. Ich scheine
> im oben Zitierten etwas Anderes gesagt zu haben, als ich
> eigentlich wollte, oder? Aber es gilt doch z.B.: 30 = 2*3*5
> und 40 = 2*2*2*5 die gemeinsamen Teiler sind hier 2 und 5.

Nein, die gemeinsamen Teiler sind $1$, $2$, $5$ und $10$ und ihr Produkt $100$.

> Das Produkt dieser Teiler ist 10, was ja gerade der ggT von
> 30 und 40 ist, und was habe ich dann oben gesagt? Kannst Du
> mir eventuell ein Gegenbeispiel geben? Danke! :-)

Du meintest: die gemeinsamen Primteiler (maximaler Vielfachheit)... :-)

Liebe Grüße
Stefan



Bezug
                                                                                                        
Bezug
Euklidischer Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:55 Do 04.08.2005
Autor: Karl_Pech

Hallo Stefan,


Vielen Dank für die Hilfe!



Grüße
Karl



Bezug
                        
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
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

Bezug
        
Bezug
Euklidischer Algorithmus: Vielen Dank!
Status: (Mitteilung) Reaktion unnötig Status 
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!

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Lineare Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de