Thuật Toán ƠcLit

Gia sư toán lớp 6 của gia sư hà nội xin giới thiệu thuật toán Oclit – Một thuật toán chuyên dùng để tìm USCLN của 2 số tự nhiên bất kỳ.

Để 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).

Trên đây gia sư toán đã giới thiệu thuật toán chia liên tiếp hay còn gọi là thuật toán Oclit, hy vọng bài viết sẽ giúp các em đơn giản hơn trong việc giải quyết các bài toán tìm USCLN.

 

About Toàn Lê