Cắt Vải Tấn Nhà Máy Dệt

Mô tả

Nhà máy dệt Thành Công vừa cho ra lò một mẻ sản xuất gồm một tấm vải hình chữ nhật có chiều rộng $a$ mét và chiều dài $b$ mét. Để chuẩn bị nguyên liệu cho dòng áo mới, tổ cắt may cần cắt tấm vải này thành các mảnh vải hình vuông có kích thước bằng nhau, sao cho không xén vứt bỏ bất kỳ mảnh vụn nào dư thừa.

Anh tổ trưởng muốn số lượng công đoạn cắt là ít nhất, tức là phải chọn kích thước mảnh vuông càng lớn càng tốt. Bạn hãy giúp anh tổ trưởng tìm ra độ dài cạnh của mảnh vải vuông lớn nhất thỏa mãn yêu cầu trên.

Về mặt toán học, bài toán này quy về việc tìm ước số chung lớn nhất (GCD) của hai chiều $a$ và $b$.