duongsonhaiphong

Chào các bạn mình là lính mới. Mình xin gửi bản dịch các tài liệu nước ngoài của mình cho bài toán chứng minh GCD(m, n)=GCD(n, m mod n). Đặc biệt trong đây còn có cả chứng minh bổ đề Bezout

____________________________________________________________________________________________________________BÀI TOÁN: Chứng minh GCD(m,n)=GCD(n,m mod n) với m, n là các số nguyên không đồng thời bằng 0. Trong đó GCD(m,n) là ƯCLN của m, n; mod là phép chi lấy dư.

____________________________________________________________________________________________________________

Đặt m= pn+r; d=GCD(m, n); e=GCD(n, r)
Chứng minh d=e
@ Chứng minh e|d
Có e=GCD(n,r)
 e|n và e|r
 e| (pn+r) (Chứng minh: e|n nên n=a.e; e|r nên r=b.e => pn+r=p.a.e + b.e=[(pa+b).e] ⋮ e)
 e|m
Vì e|m và e|n nên e|GCD(m,n) suy ra e|d (1)
Thật vậy:

Bổ đề: Nếu d=GCD(a, b) thì ∃ x, y d=xa+yb với a, b, x, y là các số nguyên và a, b không đồng thời bằng 0 (Bổ đề Bezout)

Chứng minh bổ đề: Vào link sau xem bản dịch của mình:       https://drive.google...gaQ1RogB3iNRFOA

Trở lại bài chứng minh ban đầu:

Đặt GCD(m, n)= um+vn

Do e|m và e|n nên e|(um+vn) => e|GCD(m, n)
@ Chứng minh d|e
Có d=GCD(m, n)
 d|m và d|n
 d|(m-pn)
 d|r
Vậy d|n và d|r
 d|GCD(n, r) suy ra d|e
Thật vậy:
Đặt GCD(n, r)=xn+yr
Do d|n và d|r => d|GCD(n, r) => d|e (2)
Từ (1), (2) => d=e (ĐPCM) ∎

__________________________________________________________________________________________________________________________________________________________

TÀI LIỆU GỐC TIẾNG ANH:

1. https://math.stackex...-n-gcdn-m-mod-n

2. https://proofwiki.or...Bézout's_Lemma 

____________________________________________________________________________________________________________

Cảm ơn các bạn đã theo dõi!