Hàm gcd() trong Python: Ước chung lớn nhất

GCD (Greatest Common Divisor) - Ước chung lớn nhất: số nguyên dương lớn nhất chia hết cả hai số. Module math cung cấp math.gcd().

Cú pháp

math.gcd(x, y)  # x, y là integer (có thể âm)

Ví dụ

import math

print("GCD(75, 30) =", math.gcd(75, 30))      # 15
print("GCD(0, 12) =", math.gcd(0, 12))        # 12
print("GCD(0, 0) =", math.gcd(0, 0))          # 0
print("GCD(-24, -18) =", math.gcd(-24, -18))  # 6 (luôn trả về dương)

Kết quả

GCD(75, 30) = 15
GCD(0, 12) = 12
GCD(0, 0) = 0
GCD(-24, -18) = 6

Ứng dụng thực tế

1. Rút gọn phân số

def simplify_fraction(num, den):
    g = math.gcd(num, den)
    return num // g, den // g

print(simplify_fraction(75, 30))  # (5, 2)

2. Kiểm tra số nguyên tố cùng nhau (Coprime)

def are_coprime(a, b):
    return math.gcd(a, b) == 1

print(are_coprime(15, 28))  # True
print(are_coprime(15, 25))  # False

3. Tìm BCNN (LCM) từ GCD

def lcm(a, b):
    return abs(a * b) // math.gcd(a, b)

print(lcm(12, 18))  # 36

Lưu ý

• Python 3.5+: math.gcd() hỗ trợ 2 đối số
• Python 3.9+: math.gcd(*integers) hỗ trợ nhiều đối số
• Luôn trả về số không âm
• gcd(0, 0) = 0 (theo quy ước)