إيماءة حكم إقليدس. خوارزمية إقليدس لإيجاد GCD (القاسم المشترك الأكبر)

ضع في اعتبارك طريقتين رئيسيتين للعثور على GCD بطريقتين رئيسيتين: استخدام خوارزمية إقليدس وعن طريق التحليل. دعنا نطبق كلتا الطريقتين على رقمين وثلاثة أرقام وأكثر.

خوارزمية إقليدس لإيجاد GCD

تجعل خوارزمية إقليدس من السهل حساب القاسم المشترك الأكبر لرقمين موجبين. لقد قدمنا ​​الصيغ وإثبات خوارزمية إقليدس في الجزء الأكبر المشترك: المحدد ، قسم الأمثلة.

يتمثل جوهر الخوارزمية في إجراء القسمة باستمرار مع الباقي ، والتي يتم خلالها الحصول على سلسلة من المساواة في النموذج:

أ = ب س 1 + ص 1 ، 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

يمكننا إنهاء التقسيم عندما rk + 1 = 0، حيث ص ك = gcd (أ ، ب).

مثال 1

64 و 48 .

المحلول

دعنا نقدم الترميز: أ = 64 ، ب = 48.

بناءً على خوارزمية إقليدس ، سنقوم بإجراء القسمة 64 على ال 48 .

نحصل على 1 والباقي 16. اتضح أن q 1 = 1 ، r 1 = 16.

الخطوة الثانية هي القسمة 48 في سن 16 نحصل على 3. هذا هو q2 = 3، أ ص 2 = 0.وبالتالي ، فإن الرقم 16 هو القاسم المشترك الأكبر للأرقام من الشرط.

إجابه: gcd (64 ، 48) = 16.

مثال 2

ما هو GCD للأرقام 111 و 432 ?

المحلول

يقسم 432 على ال 111 . وفقًا لخوارزمية إقليدس ، نحصل على سلسلة المساواة 432 = 111 3 + 99 ، 111 = 99 1 + 12 ، 99 = 12 8 + 3 ، 12 = 3 4.

وهكذا ، فإن القاسم المشترك الأكبر للأرقام 111 و 432 هو 3.

إجابه: gcd (111 ، 432) = 3.

مثال 3

أوجد القاسم المشترك الأكبر للعددين 661 و 113.

المحلول

سنقسم الأرقام بالتتابع ونحصل على GCD (661 , 113) = 1 . هذا يعني أن 661 و 113 عددان أوليان نسبيًا. يمكننا معرفة ذلك قبل أن نبدأ العمليات الحسابية إذا نظرنا إلى جدول الأعداد الأولية.

إجابه: gcd (661 ، 113) = 1.

إيجاد GCD عن طريق تحليل الأرقام إلى العوامل الأولية

من أجل إيجاد القاسم المشترك الأكبر لرقمين من خلال التحليل إلى عوامل ، من الضروري ضرب جميع العوامل الأولية التي تم الحصول عليها عن طريق تحليل هذين العددين المشتركين بينهما.

مثال 4

إذا حللنا العددين 220 و 600 إلى عوامل أولية ، فسنحصل على منتجين: 220 = 2 2 5 11و 600 = 2 2 2 3 5 5. ستكون العوامل المشتركة في هذين المنتجين 2 و 2 و 5. هذا يعني أن NOD (220 ، 600) = 2 2 5 = 20.

مثال 5

أوجد القاسم المشترك الأكبر للأرقام 72 و 96 .

المحلول

أوجد جميع العوامل الأولية للأعداد 72 و 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

العوامل الأولية المشتركة لرقمين: 2 و 2 و 2 و 3. هذا يعني أن NOD (72 ، 96) = 2 2 2 3 = 24.

إجابه: gcd (72 ، 96) = 24.

تستند قاعدة إيجاد القاسم المشترك الأكبر لرقمين إلى خصائص القاسم المشترك الأكبر ، والذي وفقًا له gcd (m a 1، m b 1) = m gcd (a 1، b 1) ، حيث m هو أي عدد صحيح موجب .

إيجاد GCD من ثلاثة أرقام أو أكثر

بغض النظر عن عدد الأرقام التي نحتاج إلى إيجاد GCD من أجلها ، سنتصرف وفقًا لنفس الخوارزمية ، والتي تتمثل في إيجاد GCD لرقمين على التوالي. تعتمد هذه الخوارزمية على تطبيق النظرية التالية: GCD من عدة أرقام أ 1 ، أ 2 ، ... ، أ كيساوي الرقم dk، والتي توجد في الحساب المتسلسل لـ gcd (أ 1 ، أ 2) = د 2، GCD (د 2 ، أ 3) = د 3 ، GCD (د 3 ، أ 4) = د 4 ، ... ، GCD (د ك - 1 ، أ ك) = د ك.

مثال 6

أوجد القاسم المشترك الأكبر للأعداد الأربعة 78 و 294 و 570 و 36 .

المحلول

دعنا نقدم الترميز: أ 1 = 78 ، أ 2 = 294 ، أ 3 = 570 ، أ 4 = 36.

لنبدأ بإيجاد GCD للرقمين 78 و 294: د 2 = GCD (78 , 294) = 6 .

لنبدأ الآن في العثور على d 3 \ u003d GCD (د 2 ، أ 3) \ u003d GCD (6 ، 570). وفقًا لخوارزمية إقليدس 570 = 6 95.هذا يعني انه د 3 = GCD (6 , 570) = 6 .

ابحث عن د 4 \ u003d GCD (د 3 ، أ 4) \ u003d GCD (6 ، 36). 36 يقبل القسمة على 6 بدون الباقي. هذا يسمح لنا بالحصول د 4 = GCD (6 , 36) = 6 .

د 4 = 6، هذا هو GCD (78 , 294 , 570 , 36) = 6 .

إجابه:

والآن دعونا نلقي نظرة على طريقة أخرى لحساب GCD لتلك الأرقام والمزيد. يمكننا إيجاد gcd بضرب كل العوامل الأولية المشتركة للأرقام.

مثال 7

احسب gcd للأرقام 78 و 294 و 570 و 36 .

المحلول

لنحلل هذه الأعداد إلى عوامل أولية: 78 = 2 3 13 ، 294 = 2 3 7 7 ، 570 = 2 3 5 19 ، 36 = 2 2 3 3.

لجميع الأعداد الأربعة ، فإن العوامل الأولية المشتركة هي العددين 2 و 3.

اتضح أن NOD (78 ، 294 ، 570 ، 36) = 2 3 = 6.

إجابه: gcd (78 ، 294 ، 570 ، 36) = 6.

إيجاد gcd للأرقام السالبة

إذا كان علينا التعامل مع الأعداد السالبة ، فيمكننا استخدام وحدات هذه الأعداد لإيجاد القاسم المشترك الأكبر. يمكننا القيام بذلك ، بمعرفة خاصية الأعداد ذات العلامات المتقابلة: الأعداد نو -نلها نفس القواسم.

المثال 8

أوجد gcd للأعداد الصحيحة السالبة − 231 و − 140 .

المحلول

لإجراء العمليات الحسابية ، دعنا نأخذ وحدات من الأرقام الواردة في الشرط. سيكون هذان الرقمان 231 و 140. دعونا نضعها بإيجاز: GCD (− 231 , − 140) = GCD (231 ، 140). الآن دعنا نطبق خوارزمية إقليدس لإيجاد العوامل الأولية المكونة من رقمين: 231 = 140 1 + 91 ؛ 140 = 91 1 + 49 ؛ 91 = 49 1 + 42 ؛ 49 = 42 1 + 7 و 42 = 7 6. نحصل على gcd (231 ، 140) = 7 .

ومنذ إيماءة (− 231 , − 140) = GCD (231 , 140) ، ثم gcd للأرقام − 231 و − 140 يساوي 7 .

إجابه: gcd (- 231 ، - 140) = 7.

المثال 9

أوجد Gcd لثلاثة أعداد - 585 و 81 و − 189 .

المحلول

دعنا نستبدل الأرقام السالبة في القائمة أعلاه بقيمها المطلقة ، نحصل على GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . ثم نحلل كل الأعداد المعطاة إلى عوامل أولية: 585 = 3 3 5 13 ، 81 = 3 3 3 3 و 189 = 3 3 3 7. العاملان الأوليان 3 و 3 مشتركان في الأعداد الثلاثة. اتضح أن gcd (585، 81، 189) = gcd (- 585، 81، - 189) = 9.

إجابه: GCD (- 585 ، 81 ، - 189) = 9.

إذا لاحظت وجود خطأ في النص ، فيرجى تمييزه والضغط على Ctrl + Enter

خوارزمية إقليدس

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

تأمل المشكلة التالية: مطلوب كتابة برنامج لتحديد القاسم المشترك الأكبر (GCD) لرقمين طبيعيين.

لنتذكر الرياضيات. القاسم المشترك الأكبر لعددين طبيعيين هو أكبر عدد طبيعي يقبل القسمة عليه بالتساوي. على سبيل المثال ، الأرقام 12 و 18 لها قواسم مشتركة: 2 ، 3 ، 6. القاسم المشترك الأكبر هو 6. وهذا مكتوب على النحو التالي:

gcd (12 ، 18) = 6.

قم بالإشارة إلى البيانات الأولية كـ M u N. بيان المشكلة كما يلي:
معطى:م ، ن
تجد: GCD (M ، N).

في هذه الحالة ، لا يلزم صياغة رياضية إضافية. بيان المشكلة نفسه ذو طبيعة رياضية رسمية. لا توجد معادلة لحساب GCD (M ، N) من قيم M و N ولكن من ناحية أخرى ، منذ وقت طويل ، قبل ظهور أجهزة الكمبيوتر بوقت طويل ، كانت الطريقة الحسابية لحل هذه المشكلة معروفة . تسمى خوارزمية إقليدس .

فكرة خوارزمية إقليدس

تعتمد فكرة هذه الخوارزمية على الخاصية التي إذا كانت M> N إذن

GCD (M ، N) = GCD (M - N ، N).

بعبارة أخرى ، فإن gcd عددين طبيعيين يساوي gcd لاختلافهما الموجب (معامل اختلافهما) والعدد الأصغر.

من السهل إثبات هذه الخاصية. لنفترض أن K قاسم مشترك M u N (M> N). هذا يعني أن M \ u003d mK ، N \ u003d nK ، حيث m ، n هي أرقام طبيعية ، و m> n. ثم M - N \ u003d K (m - n) ، مما يعني أن K هو مقسوم على الرقم M - N. ومن ثم ، فإن جميع القواسم المشتركة للأرقام M و N هي قواسم الفرق بينهما M - N ، بما في ذلك الأكبر القاسم المشترك.

الخاصية الواضحة الثانية:

GCD (م ، م) = م.

بالنسبة للعد "اليدوي" ، تبدو خوارزمية إقليدس كما يلي:

1) إذا كانت الأرقام متساوية ، فاخذ أيًا منها كإجابة ، وإلا استمر في الخوارزمية ؛

2) استبدل الرقم الأكبر بالفرق بين الرقمين الأكبر والأصغر ؛

3) العودة إلى تنفيذ الفقرة 1.

ضع في اعتبارك هذه الخوارزمية في مثال M = 32 ، N = 24:

بنية الخوارزمية عبارة عن حلقة متفرعة متداخلة. تتكرر الدورة حتى تتساوى قيم M و N مع بعضها البعض. في التفرع ، يتم استبدال أكبر القيمتين بالاختلاف بينهما.

انظر الآن إلى جدول تتبع الخوارزمية للقيم الأولية M = 32 ، N = 24.

خطوة عملية م ن حالة
1 المدخلات م 32
2 إدخال N 24
3 م ¹ ن 32 ¹ 24 ، نعم
4 م> ن 32> 24 ، نعم
5 م: = M-N 8
6 م ¹ ن 8 24 ، نعم
7 م> ن 8> 24 ، لا
8 N: = NM 16
9 م ¹ ن 8 16 ، نعم
10 م> ن 8> 16 ، لا
11 N: = NM 8
12 م ¹ ن 8 ، 8 ، لا
13 المحطة م 8
14 النهاية

النتيجة النهائية هي الصحيحة.

برنامج في AZ و Pascal

نكتب الخوارزمية في الذكاء الاصطناعي والبرنامج في باسكال.

أسئلة ومهام

1. قم بتشغيل برنامج Evklid على جهاز الكمبيوتر الخاص بك. اختبره على M = 32 ، N = 24 ؛ م = 696 ، ن = 234.

2. اكتب برنامجًا لإيجاد القاسم المشترك الأكبر لثلاثة أعداد باستخدام الصيغة التالية:

gcd (A، B، C) = gcd (gcd (A، B)، C).

3. اكتب برنامجًا للعثور على المضاعف المشترك الأصغر (LCM) لرقمين باستخدام الصيغة:

A × B = GCD (A، B) × LCM (A، B).

خوارزمية إقليدسهي طريقة لإيجاد القاسم المشترك الأكبر (gcd) لعددين صحيحين. تم اكتشاف النسخة الأصلية من الخوارزمية ، عندما تم العثور على GCD عن طريق الطرح ، من قبل إقليدس (القرن الثالث قبل الميلاد). في الوقت الحاضر ، يتم استخدام القسمة في كثير من الأحيان عند حساب GCD بواسطة خوارزمية إقليدس ، لأن هذه الطريقة أكثر كفاءة.

حساب gcd بالقسمة

القاسم المشترك الأكبر لزوج من الأرقام هو أكبر رقم يقسم كلا عددي الزوج. لنطلب حساب GCD للأرقام 108 و 72. ستكون خوارزمية حساب القسمة على النحو التالي:

  1. اقسم العدد الأكبر (المقسوم) على الأصغر (المقسوم عليه): 108/72 = 1 ، والباقي 36.
  2. نظرًا لأن الباقي لم يكن مساويًا للصفر ، فسنجعل المقسوم عليه مقسومًا ، والباقي مقسومًا عليه: 72/36 = 2 ، والباقي هو 0.
  3. عندما يكون الباقي صفرًا ، يكون القاسم هو gcd المطلوب لزوج الأرقام المعطاة. أي ، gcd (108 ، 72) = 36. في الواقع ، 108/36 = 3 و 72/36 = 2.

في هذه الخوارزمية تتكرر القسمة حتى يصبح الباقي صفرًا. عندما يصبح GCD هو قسمة القسمة الأخيرة. على سبيل المثال ، تريد العثور على GCD (106 ، 16):

  1. 106/16 = 6 ، الباقي 10
  2. 16/10 = 1 ، الباقي 6
  3. 10/6 = 1 ، الباقي 4
  4. 6/4 = 1 ، الباقي 2
  5. 4/2 = 2 ، الباقي 0
  6. gcd (106 ، 16) = 2

حساب GCD بالطرح

عند إيجاد GCD بالطرح ، يجب أيضًا الوصول إلى الصفر. تشبه الخوارزمية طريقة القسمة ، هنا فقط ، في كل مرحلة تالية ، يتم طرح المطروح والاختلاف عن الخطوة السابقة وتقليلها. يتم دائمًا طرح الرقم الأصغر من الرقم الأكبر. هذا النوع من الخوارزمية مناسب فقط للأعداد الصحيحة الموجبة.

دعه مطلوبًا للعثور على GCD (108 ، 72):

  1. 108 - 72 = 36
  2. 72 - 36 = 36
  3. 36 - 36 = 0
  4. gcd (108 ، 72) = 36

ابحث عن gcd (44، 60):

  1. 60 - 44 = 16
  2. 44 - 16 = 28
  3. 28 - 16 = 12
  4. 16 - 12 = 4
  5. 12 - 4 = 8
  6. 8 - 4 = 4
  7. 4 - 4 = 0
  8. gcd (44 ، 60) = 4

يتم وصف هذه الخوارزمية أحيانًا بشكل مختلف. ينتهي الطرح في وقت سابق ، في الخطوة عندما يقسم أحد الأرقام الآخر. أي أنها تجمع بين الطرح واختبار القابلية للقسمة. ثم سيبدو العثور على GCD لـ 44 و 60 كما يلي:

  1. هل 44 تقسم 60 بالتساوي؟ رقم. 60 - 44 = 16.
  2. هل 16 تقسم 44 بالتساوي؟ رقم. 44 - 16 = 28.
  3. هل 16 تقسم 28 بالتساوي؟ رقم. 28 - 16 = 12.
  4. هل 12 تقسم 16 بالتساوي؟ رقم. 16-12 = 4.
  5. هل 4 تقسم 12 بالتساوي؟ نعم. إذن gcd (44 ، 60) = 4.

ملحوظة، GCD ليس حاصل قسمة ، بل مقسوم عليه. إذا قسمنا في المثال 12 على 4 ، فسنحصل على حاصل القسمة 3. لكن هذا ليس GCD.

دليل على خوارزمية إقليدس

دعنا نأخذ في الاعتبار حقيقة أنه إذا كان أحد الأرقام الطبيعية من أحد الزوجين يقسم الآخر تمامًا ، فإن gcd الخاص بهما سيكون مساويًا لأصغرهما. يمكنك كتابتها على هذا النحو:

إذا كان a / b عددًا صحيحًا ، فإن gcd (a، b) = b. على سبيل المثال ، gcd (15، 5) = 5.

وبالتالي ، إذا توصلنا في النهاية إلى زوج من الأرقام ، أحدهما يقسم الآخر ، فإن الأقل سيكون هو القاسم المشترك الأكبر لكليهما. يتم البحث عن زوج من الأرقام بواسطة خوارزمية إقليدس: أحدهما يقسم الآخر تمامًا.

الحقيقة الثانية. مطلوب إثبات أنه إذا كان أحد الأرقام أكبر من الآخر ، فإن القاسم المشترك الأكبر لهما يساوي أكبر قاسم مشترك للعدد الأصغر من الزوج ، والفرق بين الأرقام الأكبر والأصغر. يمكن كتابة هذا على النحو التالي:

اذا كان< b, то НОД(a, b) = НОД(a, b - a).

يمكننا إثبات أن gcd (a، b) = gcd (a، b - a) على النحو التالي. دعونا ب - أ = ج. إذا كان أي رقم x يقسم a و b ، فسيتم قسمة c أيضًا. بعد كل شيء ، إذا كان a و b مختلفين ، فإن المقسوم عليه يلائمهما عددًا صحيحًا ، ولكن عددًا مختلفًا من المرات. وإذا طرحت أحدهما من الآخر ، فيجب أن يتناسب المقسوم عليه أيضًا مع عدد صحيح من المرات في الفرق الناتج.

إذا قللنا a و b على التوالي ، فسنصل عاجلاً أم آجلاً إلى قيمة أصغر منهما ، والتي تقسم القيمة الأكبر تمامًا. سيكون أصغر مثل هذا الزوج هو القاسم المشترك الأكبر للزوج الأصلي من الأعداد الطبيعية. هذا ما تدور حوله خوارزمية إقليدس.

أكبر عدد مشترك من اثنين من أرقام ral $ a $ و $ b $ - $ gcd (a، b) $ - هو الرقم الأكبر ، في بعض السرب الأرقام $ a $ و $ b $ هي دي ليات شيا بدون أثر.

للعثور على $ GCD (a، b) $ ، يمكنك شرب الطريقة الطبيعية التالية ولكن خطوة بخطوة: فك كلا الرقمين la بواسطة قوى الأعداد الأولية: $ a = 2 ^ (\ alpha_1) \ cdot 3 ^ ( \ alpha_2) \ cdot \ ldots \ cdot p ^ (\ alpha_n) _n $، $ b = 2 ^ (\ beta_1) \ cdot 3 ^ (\ beta_2) \ cdot \ ldots \ cdot p ^ (\ beta_n) _n $، (يمكن أن يكون $ \ alpha_k $ و $ \ beta_k $ خاليًا). ثم $$ gcd (a، b) = 2 ^ (\ min (\ alpha_1، \ beta_1)) \ cdot 3 ^ (\ min (\ alpha_2، \ beta_2)) \ cdot \ ldots \ cdot p ^ (\ min ( \ alpha_n، \ beta_n)) _ n. $$ $ احصل عليه: $ 2625 = 2 ^ 0 \ cdot 3 ^ 1 \ cdot 5 ^ 3 \ cdot 7 ^ 1، 8100 = 2 ^ 2 \ cdot 3 ^ 4 \ cdot 5 ^ 2 \ cdot 7 ^ 0 $ يعني $ gcd (2625، 8100) = 2 ^ 0 \ cdot 3 ^ 1 \ cdot 5 ^ 2 \ cdot 7 ^ 0 = 75 $.

العيب الأساسي في هذه الطريقة هو أن تقسيم عدد كبير إلى مضاعفات بسيطة ليس مؤيدًا - مائة ، ولكن بشكل أكثر دقة - ليس بهذه السرعة.

يصف إقليدس في الكتاب السابع "البداية" إيقاع الجو لإيجاد "المقياس العام لرقمين". يصف Al-go-rhythm-san geo-met-ri-che-ski ، بأنه على أساس القياس العام لاثنين من القطع. يتعلق الأمر بـ "after-to-va-tel-no-mu from-nya-ty" من المزيد من القطع الأقل من القطع. الآن هذا الإيقاع من الجدران الخمسة يشبه إيقاع آل جو-غو-كلي-دا لإيجاد أكثر عدد من اللاعبين على الإطلاق. قرى رال نيه تشي.

الفكرة الأساسية ، على أساس ما ، os-no-van al-go-rhythm ، تتمثل في حقيقة أن $ GCD $ chi-sat $ a $ و $ b $ يساوي $ GCD $ chi-sat $ b $ و $ a-b $. من هنا ، نعم ، هذا يعني أنك إذا صببت $ a $ على $ b $ مع الباقي ، أي ضع النموذج $ a = b \ cdot q + r $ ، ثم $ gcd (a، b) = gcd (b، r) $.

دعنا نصف الجغرافيا الجميلة ، ri-che-skuyu inter-ter-pre-tion al-go-rit-ma ، inter-active-tiv-naya re-a-li-za -tion لشخص ما قبل لو-ذا-أون-ذا-هي.

في المستطيل - no-ke مع أطوال ضلعه $ a $ و $ b $ وراء مربع edge-shi-va-em max-si-mal-but-possible. في بقية المستطيل-مو-فحم-نو-كي مرة أخرى ، فإن لحافة-شي-فا-إم عبارة عن مربع ماك-سي-مال-لكن ممكن. وهكذا دواليك حتى لا يتم رسم المستطيل المنتهية ولايته بالكامل. يبلغ طول مربع مائة رور ني سا مو-جو-ما-لازي-كو-ث-را-تا ويساوي $ GCD (a، b) $.

المزيد من الكسور ولكن جيو-ميت-ري-تشي-سكاي في-تير- قبل-تا-تشون-سا-سا-على نفس ، وشبه-رال-ليل-لكن مع-دي-تشي-سكاي-لي -ti-che-description of al-go-rit-ma Ev-kli-da.

In-ter-pre-tion al-go-rit-ma Al-go-rhythm Ev-cli-da
في مستطيل بطول ضلعه $ a $ و $ b $ (a \ gt b) $ وراء حواف si-mal-but-th-me-ra (بمائة $ b $). تتكرر هذه العملية قدر الإمكان لجزء غير مطلي. العدد الأكبر $ a $ غير مضاء مع الباقي على الرقم الأصغر $ b $: $ a = b \ cdot q_1 + r_1 $.
إذا كانت هذه المربعات تغطي المستطيل بأكمله ، فإن الرقم $ b $ هو $ GCD $. إذا كان المتبقي من $ r_1 $ من إزالة ra-veins هو nu-lu ، فإن الرقم الأصغر $ b $ هو $ GCD $.
إذا ظل هناك مستطيل نيك (بمئة رو-أون-مي $ ب $ و $ r_1 $) ، فإنه يحتوي على أكثر عدد ممكن من المربعات المؤلمة في الحد الأقصى لمقياس max-si-mal-but-th -ra (بجانب $ r_1 $). إذا كان المتبقي من $ r_1 $ لا يساوي صفرًا ، فإن الرقم الأصغر $ b $ يتم إلغاء مضاءته والباقي على $ r_1 $: $ b = r_1 \ cdot q_2 + r_2 $.
إذا كان المربع الذي يحتوي على 100 $ r_1 $ يغطي المستطيل بالكامل ، فإن $ r_1 $ هو $ GCD $. إذا كان الباقي من $ r_2 $ يساوي صفرًا في النتيجة الثانية ، فإن $ r_1 $ هو $ GCD $.
إذا كان هناك مستطيل-نيك (مع مائة رو-أون-مي $ r_1 $ و $ r_2 $) ، فإنه يحتوي على أكبر عدد ممكن من المربعات من max-si-small-size-me-ra (بضلع $ r_2 $). إذا كان ما تبقى من $ r_2 $ خلال de-le-ni الثاني لا يساوي صفرًا ، فإن $ r_1 $ يكون غير مضاء بمقدار $ r_2 $: $ r_1 = r_2 \ cdot q_3 + r_3 $.
وهكذا دواليك حتى يصبح نيك الزاوية اليمنى بالكامل غير مربع-را-تا-مي. (عاجلاً أم آجلاً ، سيحدث هذا ، لأن مائة رات مربعة ستقلل من شا أوت سييا وعلى أي حال ، يمكنك نصف خيط ما تبقى من فحم-مو-نيك-كواد-را-تا -مي بوحدة مائة ريال عماني). وهكذا دواليك حتى يصبح باقي $ r_n $ الحالي مساويًا للصفر (ra-ولكن سيحدث لاحقًا ، لأن -ku the rest-ki يقلل-sha-ut-sya).
طول مربع مائة ميل لا صغير لكن انطلق هو $ GCD $ لأرقام البداية. الأخير لا يساوي صفرًا متبقيًا الحالي $ r_ (n-1) $ هو $ GCD $ للأرقام الأصلية.

Al-go-rhythm Ev-kli-yes هي أداة قوية تستخدم في حل العديد من المشاكل الشخصية. على سبيل المثال ، يستخدم لحل المعادلات في أعداد صحيحة ، والتي تمثل الأرقام في شكل اللانهاية -كسر- nyh (سلسلة- th) التعادل ، يمكن تعميمها للعثور على أكبر-هي-الذهاب- الذهاب- de-li-te-la لعضوين متعددين.

المؤلفات

إقليدس. نا تشا لا إيف كلي دا. الكتب السابع والعاشر - M.-L: GITTL ، 1950.

ر.كورانت ، ج.روبينز. ما هو هذا ma-te-ma-ti-ka؟ - م: MTsNMO ، 2010.