خوارزمية إقليدس: القاسم المشترك الأعظم بالقسمات المتتالية

المبدأ

القاسم المشترك الأعظم لـ $a$ و $b$ لا يتغيّر إذا استبدلنا $a$ بـ باقي قسمة $a$ على $b$.

$\gcd(a, b) = \gcd(b, r) \quad \text{حيث } a = bq + r$

نكرّر حتى يصبح الباقي صفرًا. آخر باقٍ غير صفر هو القاسم المشترك الأعظم.

خطوة بخطوة

مثال: $\gcd(252, 105)$.

الخطوة	القسمة	الحاصل	الباقي
1	252 = 105 × 2 + 42	2	42
2	105 = 42 × 2 + 21	2	21
3	42 = 21 × 2 + 0	2	0

$\gcd(252, 105) = 21$.

مثال آخر

$\gcd(1071, 462)$:

• 1071 = 462 × 2 + 147
• 462 = 147 × 3 + 21
• 147 = 21 × 7 + 0

القاسم = 21.

لماذا ينجح؟

كل خطوة تقلّص الأعداد. الخوارزمية تنتهي. القاسم المشترك محفوظ في كل خطوة.

التطبيقات

• اختصار كسر: نقسم البسط والمقام على القاسم المشترك الأعظم.
• حل معادلة ديوفنطية $ax + by = c$: قابلة للحل إذا وفقط إذا $\gcd(a, b) \mid c$.
• التشفير: خوارزمية إقليدس الممتدّة تظهر في RSA.

أخطاء شائعة

1. التوقّف مبكرًا: يجب المتابعة حتى باقٍ صفري.
2. الباقي الخاطئ: القاسم = آخر باقٍ غير صفر.
3. الخلط بين الباقي والحاصل.

?À toi de jouer

$\gcd(48, 18)$ بخوارزمية إقليدس؟

A.6B.2C.12D.3

Valider