0 Daumen
486 Aufrufe

Gegeben seien n, m ∈ N. Betrachte die Menge
A := {d ∈ N | ∃ a, b ∈ Z : d = an + bm}.
Offenbar ist A keine ∅ (a = b = 1 ist 1 · n + 1 · m ∈ N, also n + m ∈ A). Also gibt
es ein kleinstes Element d0 ∈ A; dazu gibt es a0, b0 ∈ Z mit d0 = a0n + b0m.


Zeigen Sie:
(a) Ist d ∈ N ein gemeinsamer Teiler von n und m (d.h., es gilt d | n und d | m), so folgt d | d0,
und damit auch d ≤ d0

(b) d0 selbst ist ein gemeinsamer Teiler von n und m. (Hinweis: Nehmen Sie an, es gilt d0 (teilt nicht) n und
teilen Sie dann n mit Rest durch d0; es gilt also n = qd0 + r mit q, r ∈ Z und 0 < r < d0.)

Avatar von

1 Antwort

0 Daumen
d | n und d | m

Seien dann p,q ∈ ℤ mit dp = n und dq = m.

Dann ist d0 = a0n + b0m = a0dp + b0dq = d·(a0p + b0q).

Also d0 = d·(a0p + b0q) und somit d | d0.

Avatar von 105 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community