05/10/27 10:19:18
命題
a と b が Z の元のとき (a, b) = (r) となる r ∈ Z がある。
証明
a ≧ 0, b ≧ 0 と仮定してよい。
a と b の最大値を max(a, b) と書く。
max(a, b) に関する帰納法を使う。
a = b ならこの命題は明らかだから、b > a とする。
b = aq + r, 0 < r < a となる q, r ∈ Z がある。
補題(>>563)より、(a, b) = (a, r) となる。max(a, r) = a
だから、帰納法の仮定より (a, r) = (s) となる s ∈ Z がある。
証明終