أوجد القاسم المشترك الأكبر دون قسمة واحدة

الخوارزمية في جملة واحدة

القاسم المشترك الأكبر لعددين لا يتغيّر إذا استبدلنا الأكبر بالفرق مع الأصغر.

مثال خطوة بخطوة: PGCD(84, 30)

الخطوة	العملية	النتيجة
1	$84 - 30$	$(54, 30)$
2	$54 - 30$	$(24, 30)$
3	$30 - 24$	$(24, 6)$
4	$24 - 6$	$(18, 6)$
5	$18 - 6$	$(12, 6)$
6	$12 - 6$	$(6, 6)$ ✓

PGCD(84, 30) = 6.

إصدار « القسمة » (أسرع)

بدلًا من الطرح عدة مرات، خذ باقي القسمة:

• $84 = 2 \times 30 + 24$ ← PGCD(30, 24)
• $30 = 1 \times 24 + 6$ ← PGCD(24, 6)
• $24 = 4 \times 6 + 0$ ← PGCD = 6.

هذه هي خوارزمية إقليدس الكلاسيكية.

اختصار للكشف السريع

إذا انتهى العددان بنفس الرقم الزوجي، جرّب 2 كعامل. إذا كانا مضاعفَي 3 (مجموع الأرقام)، جرّب 3. لتجنّب الخوارزمية.

?دورك الآن

ما القاسم المشترك الأكبر لـ 48 و36؟

A.6B.12C.18D.24

تحقّق