Beweis mit Euklidischem Algorithmus

Neue Frage »

nuerw3 Auf diesen Beitrag antworten »
Beweis mit Euklidischem Algorithmus
Meine Frage:
Hallo alle zusammen ich habe hier folgenden Beweis und die dazu gehörigen Theoreme..


Meine Ideen:
Ich verstehe jeden einzelnen schritt vom Beweis außer:

Warum kann man aus Theorem 1.2 folgern das gcd(a,b) den gcd(|b|, a mod |b|) teilt und umgekehrt ? Ich kann das nicht nachvollziehen kann mir jemand da auf die Sprünge helfen ?
HAL 9000 Auf diesen Beitrag antworten »

ist der Rest der Division von durch . Und genau dasselbe ist das in Theorem 1.2 (wenn wir dort mit statt arbeiten). Und damit ist man bei der Gleichung

mit .

Weiter dann wie in dem im Scan abgedruckten Beweis.
nuerw3 Auf diesen Beitrag antworten »

Ja das weiß ich, ich verstehe aber nicht warum der größte gemeinsame Teiler von a und b den größten gemeinsamen Teiler von |b| und a mod |b| teilt verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Das beruht auf einer elementaren Teilbarkeitseigenschaft: Sind zwei Zahlen durch teilbar, dann auch ihre Summe bzw. ihre Differenz. Angewandt auf mit folgt damit

1) Gilt sowie (und damit automatisch auch ), so gilt auch .

2) Damit ist jeder gemeinsamen Teiler von und auch ein gemeinsamer Teiler von und . Somit ist auch der größte gemeinsame Teiler von und ein gemeinsamer Teiler von und - hier aufpassen, es ist (zumindest allein auf Basis dieser Argumentation) noch nicht notwendig auch schon der größte gemeinsame Teiler von und , da braucht es noch ergänzende Argumente. Augenzwinkern
Nuerw3 Auf diesen Beitrag antworten »

Wir brauchen doch aber den fall das gcd(a,b) den gcd(|b|,a mod |b|) teilt und umgekehrt damit würde dann folgen das gcd(a,b)= gcd(|b|,a mod |b|).
Die regel die du ja am anfang beschrieben hast ist ja die 3 regel aus Theorem1.1.
Also angenommen es gelte gcd(a,b)=t dann gilt t | a und t | b ( und t | |b|) aus theorem 1.1 regel 3 folgt außerdem das t | r ist. Es folgt das t | gcd( |b|, a mod |b|) teilt denn t teilt auch |b| und r stimmt das so? Wie zeige ich dann das umgekehrte?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Nuerw3
Wir brauchen doch aber den fall das gcd(a,b) den gcd(|b|,a mod |b|) teilt

Was soll das "aber" in dem Satz? Genau auf diese Frage bin ich doch eingegangen! Wenn wir zeigen, dass gcd(a,b) ein gemeinsamer Teiler von |b| und r ist, dann ist das gleichbedeutend damit dass es ein Teiler von gcd(|b|,r) ist.

Zitat:
Original von Nuerw3
Wie zeige ich dann das umgekehrte?

Na im Prinzip genauso wie ich es für die andere Richung getan habe, nur diesmal angewandt auf . Das solltest du aber so langsam mal erkennen, dass da prinzipiell kein Unterschied ist. unglücklich
 
 
Nuerw3 Auf diesen Beitrag antworten »

Also wäre das dann so richtig mathematisch korrekt :

Gilt t | r und t | |b| somit auch ( t | b ) so gilt auch t | a sind nämlich zwei zahlen durch t teilbar dann auch die Summe der faktor q macht auch nichts aus.

Damit sit jeder gemeinsame teiler t von r und |b| Auch ein gemeinsamer teiler von a und b somit wäre auch der ggt von r und |b| ein gemeinsamer teiler von a und b. Somit teilt gcd( |b| , r) den gcd(a,b).

Stimmt das so? Würdest du das auch an der tafel so zeigen ist mir echt wichtig danke.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »