كيف تستعمل خوارزمية إقليدس (PGCD)
PGCD(a,b)
PGCD(a,b) = PGCD(b, a b)
نكرر حتى الباقي = 0
آخر باقي غير منعدم = PGCD
الحل خطوة بخطوة
PGCD(48, 18)
1
48 = 18 × 2 + 12
الخطوة 1
2
18 = 12 × 1 + 6
الخطوة 2
3
12 = 6 × 2 + 0
الخطوة 3
4
PGCD = 6
آخر باقي ≠ 0
الخلاصة
- اقسم a على b واحتفظ بالباقي
- اقسم b على الباقي
- كرر حتى الباقي = 0
- PGCD = آخر مقسوم عليه
⚠️ الخطأ الشائع
PGCD(48,18) = 18 (الأصغر)
PGCD(48,18) = 6 (بالخوارزمية)
PGCD ≠ العدد الأصغر دائمًا
خطوات القسمة والموافقات في Z
كيف تستعمل خوارزمية إقليدس (PGCD)
خوارزمية إقليدس تقسم ثم تأخذ الباقي وتكرر حتى الباقي = 0 — آخر باقي غير منعدم هو PGCD.
- PGCD(a,b) ≠ العدد الأصغر دائمًا — يجب تطبيق الخوارزمية
- الخوارزمية تُستعمل أيضًا لإيجاد معاملي بيزو (u و v)