A := {d ∈ N | ∃ a, b ∈ Z : d = an + bm}, zz d | n und d | m), so folgt d | d0

Question

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.)

Answer 1

d | n und d | m

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

Dann ist d₀ = a₀n + b₀m = a₀dp + b₀dq = d·(a₀p + b₀q).

Also d₀ = d·(a₀p + b₀q) und somit d | d₀.