القاسم المشترك الأكبر

القاسم المشترك الأكبر (GCD) لعددين a و b هو أكبر عدد صحيح موجب يقسم كلاً من a و b. يُرمز له gcd(a, b) أو (a, b).

التعريف

gcd(a, b) هو أكبر d بحيث d | a و d | b.

gcd(12, 18) = 6 لأن القواسم المشتركة هي 1، 2، 3، 6، وأكبرها 6. gcd(7, 13) = 1 (العددان أوليان فيما بينهما).

لحساب gcd(a, b) حيث a ≥ b: • إذا b = 0، فـ gcd = a • وإلا gcd(a, b) = gcd(b, a mod b)

مثال: gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6.

تبسيط الكسور: 12/18 = 2/3 بعد القسمة على gcd = 6.

حساب LCM: gcd(a,b) × lcm(a,b) = a × b للأعداد الموجبة.

التشفير والنظريات العددية.

gcd(0, n) = |n| للعدد n ≠ 0. gcd(0, 0) غير معرّف عادة.

يعني أن العددين «أوليين فيما بينهما» (coprime): لا قاسم مشترك غير 1.