Question

[Trần Hà Anh]

Hãy nêu thuật toán Ơ - Clit

Answer 1

[Dirty Vibe]

Bạn tick cho mình đi! Mình sẽ trả lời!

Để tìm USCLN của hai số tự nhiên a và b bất kỳ ta dùng cách chia liên tiếp hay còn gọi là thuật toán Oclit như sau:

Bước 1: Lấy a chia cho b:

• Nếu a chia hết cho b thì USCLN(a,b) = b.
• Nếu a không chia hết cho b (dư r) thì làm tiếp bước 2.

Bước 2: Lấy b chia cho số dư r:

• Nếu b chia hết cho r thì USCLN(a,b) = r
• Nếu b chia cho r dư r1 (r1 # 0) thì làm tiếp bước 3.

Bước 3: Lấy r chia cho số dư r1:

• Nếu r chia cho r1 dư 0 thì UCLN(a,b) = r1.
• Nếu r chia cho r1 dư r2 (r2 # 0) thì làm tiếp bước 4.

Bước 4: Lấy r1 chia cho số dư r2:

• Nếu r1 chia hết cho r2 thì USCLN(a,b) = r2.
• Nếu r1 cho cho r2 dư r3 (r3 # 0) thì làm tiếp như trên đến khi số dư bằng 0.

Số dư cuối cùng khác 0 trong dãy chia liên tiếp như trên là USCLN(a,b).