2,DÃY SỐ TỰ NHIÊN GIẢM DẦN NÊN SỐ PHÉP CHIA LÀ HỮU HẠN DO ĐÓ QUÁ TRÌNH...
2
,
dãy số tự nhiên giảm dần nên số phép chia là hữu hạn do đó quá trình trên kết thức với
một số dư bằng
0
). Theo chứng minh ở ví dụ trên ta có
( ) ( ) (
a b
,
=
b r
,
1
=
r r
1
,
2
)
=
...
(
r
n
−
1
,
r
n
)
=
r
n
vì
r
n
−
1
chia hết cho
r
n
Như vậy
UCLN a b
( , )
là số chia cuối cùng trong dãy các phép chia liên tiếp
a
cho
b
,
b
cho
r r
1
,
1
cho
r
2
,...
, trong đó
r r
1
, ,...
2
là số dư trong các phép chia theo thứ tự trên.
Trong thực hành người ta đặt tính như sau :
72
56
56
16
1
16
8
3
0
2
Việc thực hiện một dãy phép chia liên tiếp như trên được gọi là thuật toán Ơ clit.
Trường hợp tìm ƯCLN của ba số, ta tìm ƯCLN của hai số rồi tìm UCLN của kết quả
với số thứ ba.
Bài toán 3. Tìm ƯCLN( a, b) biết a là số gồm 1991 chữ số 2; b là số gồm 8 chữ số 2.
Hướng dẫn giải
Ta có: 1991 chia 8 dư 7, còn 8 chia 7 dư 1
Theo thuật toán Ơ- Clít:
( 22 ...2 ,22 ...2) (22 ...2,22 ...2) (22 ...2,2) 2.
(a, b)
=
=
=
=
1991 sè 2 8 sè 2
8 sè 2
7 sè 2
7 sè 2
Bài toán 4. Tìm ƯCLN của
a)
Bạn đang xem 2 , - Các bài toán về ước và bội -
