| Autor |
Beitrag |
    
Ivo Matzekat (Lucifer)
| | Veröffentlicht am Freitag, den 27. Oktober, 2000 - 15:51: | 
|
ich habe folgendes problem:
Seien m, n, q Element der nat. Zahlen. Zeige, daß
ggT(m,n)=ggT(m,n+mq) gilt.
hat vieleicht jemand einen Lösungsvorschlag? |
Zaph (Zaph)
| | Veröffentlicht am Freitag, den 27. Oktober, 2000 - 17:05: |
|
Du musst zeigen:
d ist genau dann ein Teiler von m und n, wenn d ein Teiler von m und n + mq ist. (Klar wieso?)
Sei also d ein Teiler von m und n. Etwa m = ad und n = bd. Dann ist n + mq = bd + adq = d(b + aq). Also ist d ein Teiler von n + mq.
Sei andererseits d ein Teiler von m und n + mq, etwa m = ad und n + mq = bd. Dann ist n = n + mq - mq = bd - adq = d(b - aq). Also ist d ein Teiler von n. |
Matroid (Matroid)
| | Veröffentlicht am Freitag, den 27. Oktober, 2000 - 17:44: |
|
Ja Ivo,
das ggt von zwei Zahlen ist ein Teiler jeder der beiden Zahlen. Eine Zahl, die n und m teilt, teilt auch n+mq. Das ist schon mal sicher. Offen ist die Frage, ob es sich dabei nur im irgendeinen Teiler oder wirklich um das ggt von m und n+mq handelt.
Nehmen wir mal an, es sei ggt(m,n) nicht das ggt von m und n+mq, dann gibt es eine größere Zahl p=ggt(m,n+mq). Damit p das ggt sein kann, muß es
m teilen. Wenn p aber ein Teiler von m ist, aber nicht das ggt von m und n (denn wir hatten ja angenommen, das ggt(m,n+mq) sei groesser als ggt(m,n)), dann kann p kein Teiler von n sein und ausserdem gibt es ein xeN mit m=xp.
Da aber p=ggt(m,n+mq) => p|n+mq <=> p|n+xpq
<=> Es ex. ein yeN mit yp=n+xpq.
Nun umordnen und ausklammern: p*(y-xq)=n. Dann wäre also p doch ein Teiler von n. Insgesamt ein Teiler von m und ein Teiler von n, der größer ist als ggt(m,n). Die Überlegung führt zu einem Widerspruch. Das bedeutet, das ggt(m,n+mq) kann nicht größer sein als ggt(m,n).
Ergo: ggt(m,n)=ggt(m,n+mq)
Gruß
Matroid |
|
