Vì sao lại trừ hai số a và b khi tìm UCLN?

[Nguyen_Luong_Dinh_Ho (Nguyễn Lương Đình Hoàng)]

Em có đoạn chương trình tìm UCLN bằng đệ quy như này:

int UCLN(int a, int b)
{

    if(a==b)
    {
        return a;
    }
    else if(a>b)
        return UCLN(a-b,b);
    else
        return UCLN(a,b-a);
}

Em ko hiểu cơ sở lý thuyết nào để thực hiện phép trừ như vậy. Anh chị giải thích giúp em với ạ. Em cảm ơn nhiều.

[noname00 (HK boy)]

Giả sử d = gcd(a,\ b). Đặt a = d*m, b = d*n, vậy a chia hết cho d và b chia hết cho d, gcd(m,\ n) = 1. Không mất tính tổng quát, giả sử a > b.

\Rightarrow a - b = d(m - n).

Xét d' = gcd(a-b,\ b) = gcd(d(m-n),\ dn) = d*gcd(m-n,\ n)

Gọi x = gcd(m-n, n) \Rightarrow m-n chia hết cho x và n chia hết cho x \Rightarrow (m-n)+n = m cũng chia hết cho x.

m và n cùng chia hết cho x, mà gcd(m,\ n) = 1 \Rightarrow x = 1.

Do vậy d' = d * gcd(m-n, n) = d*1 = d. Ta có điều phải chứng minh.

[library (La biblioteca)]

Đó là giải thuật Euclid cậu ạ

[Nguyen_Luong_Dinh_Ho (Nguyễn Lương Đình Hoàng)]

Thanks 2 anh, tính ra cái vấn đề nó đơn giản ghê mà em lại ko hiểu. Haha.