|
Gọi d’ > 0 là giá trị nhỏ nhất của số có dạng (am + bn),với m,n thuộc Z, và m, n độc lập với nhau: d′=am+bn′ Giả sử am+bn⋮d′ ⇔am+bn=d′q+rq∈N,r∈Z,r<d′ Do đó : r=am+bn−(am′+bn′)q⇔r=a(m−m′q)+b(n−n′q) Điều này có nghĩa là tồn tại một số r > 0 có dạng (am + bn) và r < d, mâu thuẫn với cách chọn d’ Vậy : am+bn⋮d′ ⇔d′|am+bn Ta chọn m=1;n=0 ⇒d|a.1+b.0=a Ta lại chọn m=0,n=1: ⇒d′|b Do đó d’ là ước số chung của a và b ⇔d′|d=(a,b) (1) Mặt khác d=(a,b)⇒d|a∧d|b⇒d|am+bn∀m,n∈Z⇒d|d′(2) Từ (1), và (2) ⇒d=d′ (đpcm)
|