[LẬP TRÌNH PYTHON] tìm UCLN bằng thuật toán Euclid.

Video tìm UCLN bằng thuật toán Euclid trình bày chi tiết từ cơ sở toán học, thuật toán và viết chương trình trên Python và trên Scratch.
Các bạn có thể xem phần chứng minh cho các tính chất có đề cập trong video tại phần bình luận nhé.

[@laptrinhpython2263]

Chứng minh: UCLN(a,b)=UCLN(b,R) với R là số dư của a/b Giả sử m là UCLN(a,b) ta có a "᎒" m và b "᎒" m. Ta viết a=b*x+R =>(b*x+R) "᎒" m Do tổng (b*x+R) "᎒" m và có b*x "᎒" m => R "᎒" m tức là m cũng là UCLN của b và R Vậy UCLN(a,b)=UCLN(b,R)=m

[@laptrinhpython2263]

Chứng minh: Nếu tổng (a+b) ᎒ m, a ᎒ m, Thì b ᎒ m Xét biểu thức (a+b):m = a/m+b/m là biểu thức nguyên vì (a+b)᎒ m Mà a/m nguyen=> b/m nguyên tức là b᎒m