✖

Ước chung lớn nhất

Ước chung lớn nhất của hai số nguyên là số mà cả hai số đều chia hết cho nó, đồng thời không có số nào lớn hơn mà cả hai số cũng chia hết cho nó.

Ví dụ, lấy hai số 24 và 32. Ước chung lớn nhất của chúng là bao nhiêu? Trước hết ta tìm một số là ước của cả hai số.

  • Chẳng hạn 24 chia hết cho 12, nhưng 32 không chia hết cho 12, vì 32 / 12 bằng 2,666…, không phải số nguyên. Vậy 12 không thể là ước chung lớn nhất của 24 và 32.
  • Còn số 4 thì sao? Cả hai số đều chia hết cho 4: 24 / 4 bằng 6 và 32 / 4 bằng 8. Vậy số 4 là ứng viên đầu tiên của ta. Có số nào lớn hơn mà cả hai số đều chia hết cho nó không?
  • Cả 24 và 32 đều chia hết cho 8, và 8 lớn hơn 4.
  • Không có số nào lớn hơn 8 mà cả hai số đều chia hết cho nó. Vậy 8 là ước chung lớn nhất của 24 và 32.

Thuật toán Euclid tìm ước chung lớn nhất

Có một cách khá đơn giản để tìm ước chung lớn nhất của hai số, đó là thuật toán Euclid. Lúc đầu có hai số x và y mà ta cần tìm ước chung lớn nhất. Ta thử với ví dụ x = 50 và y = 35. Cách làm như sau:

  1. Thực hiện phép chia x / y và ghi nhớ số dư. Gọi số dư này là z. Trong ví dụ ta có 50 / 35, được số dư z = 15.
  2. Bây giờ đổi chỗ các biến: gán cho biến x giá trị của y, và gán cho y giá trị của z. Giá trị cũ của x bỏ đi. Sau bước này ta có x = 35 và y = 15.
  3. Bây giờ kiểm tra xem y có bằng 0 không. Nếu có thì ước chung lớn nhất là số x. Vì y khác 0 nên ta tiếp tục và lặp lại cả quá trình từ bước 1.
  4. Lại thực hiện phép chia x / y, tức là 35 / 15, được số dư z = 5.
  5. Đổi chỗ các biến, ta được x = 15 và y = 5. Vì y khác 0 nên ta tiếp tục.
  6. Thực hiện phép chia x / y, tức là 15 / 5. Số dư là z = 0.
  7. Đổi chỗ các biến, ta được x = 5 và y = 0.
  8. Lúc này y = 0 và thuật toán kết thúc. Ước chung lớn nhất là số x = 5.

Điều quan trọng là thứ tự của hai số không ảnh hưởng đến kết quả. Nếu đổi chỗ hai số trong ví dụ, ta được cặp x = 35 và y = 50. Cách làm vẫn như cũ:

  1. Thực hiện phép chia x / y, tức là 35 / 50, được số dư z = 35.
  2. Đổi chỗ các biến: x = 50 và y = 35.
  3. Ta thấy bước này chỉ đơn giản là đổi chỗ giá trị của hai biến x và y cho nhau…

Máy tính

Máy tính dưới đây tính ước chung lớn nhất cho bạn.