Beweise modulo/ggT < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Noch ein letzter Beweis:
a, b, m Element N
a [mm] \equiv [/mm] b mod m --> ggT (a,m) = ggT (b,m) |
Ich habe herausgefunden, dass a = qm+b und b=a-qm
Den ggT kann ich über den Eukl. Algorithmus bestimmen, weiß aber nicht, wie ich diesen hier anwenden kann.
Im Lösungsblatt bei mir heißt es:
a = q1m + r, und b = ~q1m + r. Daher liefert die DurchfÄuhrung des
euklidischen Algorithmus' identische Ergebnisse, denn der nÄachste Schritt lautet in beiden
FÄallen:
m = q2*r + r2.
Das kapiere ich so nicht, obwohl ich es sicherlich so ähnlich da stehen habe.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:33 So 25.11.2007 | | Autor: | leduart |
Hallo
fang doch einfach mit dem eukl. Alg. für a und m an und von dem mit b und m mach den ersten und den zweiten schritt, wobei du schon weisst dass a und b bei division durch m denselben Rest lassen.
Gruss leduart
|
|
|
|
