Hỏi về Extended Euclid Algorithm

Nobita1 · September 10, 2019, 1:27am

Mình đang cần chứng minh công thức này:

Ax+By=GCD(A,B)

Có tìm được một trang chứng minh cái này, nhưng mình đọc khó hiểu quá, ai có thể giải thích cho mình được không?
https://proofwiki.org/wiki/Bézout's_Lemma#Proof_2

Mình đang mắc ở chõ này:

không hiểu tại sao x lại được biễu diên qua d theo công thức như vậy.

rogp10 · September 10, 2019, 12:09am

Đó là định nghĩa phép chia lấy x chia cho d thì dư r.

Khi lấy số lớn trừ số bé thì kết quả cũng có dạng ma+nb mà phép chia có thể biểu diễn bằng phép trừ nên ta nghĩ đến phép chia.

Nobita1 · September 10, 2019, 6:47am

vì x và d đều thuộc S, mình chưa hiểu về mối quan hệ giữa x và d để đưa ra công thức x = qd + r đấy, chứ còn công thức định nghĩa phép chia thì không có gì

rogp10 · September 12, 2019, 8:43am

Cứ hai số nguyên dương thì chia được thôi
Mà bài này sử dụng extremal principle

rogp10 · August 5, 2020, 9:54am

Peano axiom:

0 là số tự nhiên
Nếu n là số tự nhiên thì succ(n) (số liền sau n) cũng là số tự nhiên
succ(n) luôn khác 0.
succ(m) = succ(n) <=> m = n

Phép nhân số tự nhiên theo Peano định nghĩa như này:

a * 0 = 0 * a = 0 (*)
a * succ(b) = a + a * b (**)

Thay b = 0 ta có a * succ(0) = a, giờ ta cần suy ra succ(0) * succ(b) = succ(b), hay succ(0) là phần tử trung hòa của phép nhân.

succ(0) * 0 = 0 (do *)
succ(0) * succ(b) = succ(0) + succ(0) * b
= succ(0) + b (giả thiết quy nạp theo b)
= succ(0 + b) (xem phép cộng)
= succ(b)

^{Giờ ta có thể đặt succ(0) = 1}

hungaya · July 5, 2020, 2:37pm

Thiếu 1 tiên đề kìa,

Số 0 không là số kế tiếp của bất kì số tự nhiên nào.

Nói cách chuẩn hơn, \forall n \in \mathbb{N}: \text{succ}(n) \ne 0.