1071 mod 465 يساوي 141. و465 mod 141 يساوي 42. و141 mod 42 يساوي 15، و42 mod 15 يساوي 12، و15 mod 12 يساوي 3، و12 mod 3 يساوي 0. وآخر باقٍ غير صفري، 3، هو القاسم المشترك الأكبر، وكل خطوة مبرّرة بالسبب نفسه: كل عدد يقسم a وb معًا يقسم أيضًا a − qb، فالزوج وباقيه لهما القواسم نفسها بالضبط. لا شيء هنا يحتاج إلى تحليل إلى عوامل — وهذا هو المغزى العملي: 3 هي الإجابة قبل وقت طويل من معرفة أي أحد لماذا 1071 = 3·357.
عدد الخطوات هو ما يجدر النظر إليه. أثبت لامي عام 1844 أن خوارزمية إقليدس على زوج من الأعداد الصحيحة لا تستغرق أبدًا أكثر من نحو خمسة أمثال عدد الخانات العشرية للأصغر، وأسوأ الحالات هي أعداد فيبوناتشي المتتالية — ولهذا تتقلص 141، 42، 15، 12، 3 في هذه الصفحة بسرعة: لا شيء هنا جار لفيبوناتشي. والصيغة الموسّعة من جدول البواقي نفسه تعيد أيضًا المعاملات في 3 = 1071s + 465t، وهي مكوّن كل إجراء قسمة معيارية في نظام الجبر الحاسوبي.
الإجابة
3
كيف تقرأها
15 mod 12، آخر باقٍ غير صفري. الرابطان الأولان هما الخطوتان الافتتاحيتان، 1071 mod 465 = 141 و465 mod 141 = 42.
المصدر
Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give
احل في الحاسبة
تفتح هذه الروابط الحاسبة المناسبة بأرقام هذه المسألة مُدخَلة بالفعل. السطر أعلاه هو ما ينبغي أن تعرضه الشاشة — تحقّق بنفسك.