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

يمكن اعتبار خوارزمية إقليدس بمثابة إنشاء سلسلة من الأعداد الصحيحة غير السالبة تبدأ بالعددين الصحيحين المعطيين.${\displaystyle r_{-2}=a}$و${\displaystyle r_{-1}=b}$وستنتهي في النهاية بالعدد الصحيح صفر:${\displaystyle \{r_{-2}=a,\ r_{-1}=b,\ r_{0},\ r_{1},\ \cdots ,\ r_{n-1},\ r_{n}=0\}}$مع${\displaystyle r_{k+1}<r_{k}.}$العدد الصحيح${\displaystyle r_{n-1}}$سيكون حينها هو القاسم المشترك الأكبر، ويمكننا أن نقول${\displaystyle {\text{gcd}}(a,b)=r_{n-1}.}$توضح الخوارزمية كيفية إنشاء البواقي الوسيطة${\displaystyle r_{k}}$عن طريق القسمة مع الباقي على الزوج السابق${\displaystyle (r_{k-2},\ r_{k-1})}$عن طريق إيجاد ناتج قسمة صحيح${\displaystyle q_{k}}$لهذا السبب:

${\displaystyle r_{k-2}=q_{k}\cdot r_{k-1}+r_{k}{\text{, with }}\ r_{k-1}>r_{k}\geq 0.}$

لأن متتالية الأعداد الصحيحة غير السالبة${\displaystyle \{r_{k}\}}$بما أن الدالة تتناقص بشكل صارم، فلا بد أن تنتهي في النهاية . بعبارة أخرى، بما أن${\displaystyle r_{k}\geq 0}$لكل${\displaystyle k,}$وكل${\displaystyle r_{k}}$هو عدد صحيح أصغر تمامًا من العدد السابق.${\displaystyle r_{k-1},}$لا يمكن في النهاية أن يكون هناك عدد صحيح غير سالب أصغر من الصفر، وبالتالي يجب أن تتوقف الخوارزمية. في الواقع، ستتوقف الخوارزمية دائمًا عند الخطوة رقم n .${\displaystyle r_{n}}$يساوي الصفر. ^{[ 15 ]}

على سبيل المثال، لنفترض أننا طلبنا القاسم المشترك الأكبر للعددين 1071 و462. التسلسل هو في البداية${\displaystyle \{r_{-2}=1071,\ r_{-1}=462\}}$ومن أجل العثور${\displaystyle r_{0},}$نحتاج إلى إيجاد أعداد صحيحة${\displaystyle q_{0}}$و${\displaystyle r_{0}<r_{-1}}$بحيث:

${\displaystyle 1071=q_{0}\cdot 462+r_{0}.}$

هذا هو ناتج القسمة${\displaystyle q_{0}=2}$منذ${\displaystyle 1071=2\cdot 462+147.}$وهذا يحدد${\displaystyle r_{0}=147}$وهكذا أصبح التسلسل الآن${\displaystyle \{1071,\ 462,\ r_{0}=147\}.}$الخطوة التالية هي مواصلة التسلسل للعثور على${\displaystyle r_{1}}$عن طريق إيجاد الأعداد الصحيحة${\displaystyle q_{1}}$و${\displaystyle r_{1}<r_{0}}$بحيث:

${\displaystyle 462=q_{1}\cdot 147+r_{1}.}$

هذا هو ناتج القسمة${\displaystyle q_{1}=3}$منذ${\displaystyle 462=3\cdot 147+21.}$وهذا يحدد${\displaystyle r_{1}=21}$وهكذا أصبح التسلسل الآن${\displaystyle \{1071,\ 462,\ 147,\ r_{1}=21\}.}$الخطوة التالية هي مواصلة التسلسل للعثور على${\displaystyle r_{2}}$عن طريق إيجاد الأعداد الصحيحة${\displaystyle q_{2}}$و${\displaystyle r_{2}<r_{1}}$بحيث:

${\displaystyle 147=q_{2}\cdot 21+r_{2}.}$

هذا هو ناتج القسمة${\displaystyle q_{2}=7}$منذ${\displaystyle 147=7\cdot 21+0.}$وهذا يحدد${\displaystyle r_{2}=0}$وهكذا تكتمل السلسلة على النحو التالي:${\displaystyle \{1071,\ 462,\ 147,\ 21,\ r_{2}=0\}}$حيث لا يوجد عدد صحيح غير سالب أصغر من${\displaystyle 0}$يمكن العثور عليه. الباقي قبل الأخير${\displaystyle 21}$وبالتالي فإن القاسم المشترك الأكبر المطلوب هو:

${\displaystyle {\text{gcd}}(1071,\ 462)=21.}$

يمكننا التعميم قليلاً عن طريق إسقاط أي شرط ترتيب على القيمتين الأوليين${\displaystyle a}$و${\displaystyle b.}$لو${\displaystyle a=b,}$قد تستمر الخوارزمية وتجد ببساطة أن${\displaystyle {\text{gcd}}(a,\ a)=a}$حيث سيكون تسلسل البواقي${\displaystyle \{a,\ a,\ 0\}.}$لو${\displaystyle a<b,}$ثم يمكننا الاستمرار أيضاً لأن${\displaystyle a\equiv 0\cdot b+a,}$مما يشير إلى أن الباقي التالي يجب أن يكون${\displaystyle a}$نفسها، والتسلسل هو${\displaystyle \{a,\ b,\ a,\ \cdots \}.}$عادةً، سيكون هذا غير صالح لأنه يخالف الشرط.${\displaystyle r_{0}<r_{-1}}$لكننا الآن لدينا${\displaystyle a<b}$بحكم التصميم، يُلبى الشرط تلقائيًا، ويمكن لخوارزمية إقليدس أن تستمر كالمعتاد. لذا، فإن حذف أي ترتيب بين أول عددين صحيحين لا يؤثر على النتيجة القائلة بأن المتتالية يجب أن تنتهي في النهاية، لأن الباقي التالي سيُحقق الشرط دائمًا.${\displaystyle r_{0}<b}$ويستمر كل شيء كما هو مذكور أعلاه. التعديلات الوحيدة المطلوبة هي أن${\displaystyle r_{k}<r_{k-1}}$فقط لـ${\displaystyle k\geq 0,}$وأن المتتالية الفرعية من الأعداد الصحيحة غير السالبة${\displaystyle \{r_{k-1}\}}$ل${\displaystyle k\geq 0}$يتناقص بشكل صارم، وبالتالي يستبعد${\displaystyle a=r_{-2}}$من كلا البيانين.

وجود خطوة${\displaystyle N}$بحيث${\displaystyle r_{N}=0}$ويترتب على الشرط${\displaystyle |r_{i}|<|r_{i-1}|}$، ل${\displaystyle i\geq 1}$وهذا يضمن إنهاء الخوارزمية.

الباقي الأخير غير الصفري${\displaystyle r_{N-1}}$مساوياً لـ${\displaystyle \gcd(a,b)}$وينتج ذلك عن الخصائص التالية لـ${\displaystyle \gcd }$

1.${\displaystyle \gcd(x,0)=x}$للجميع${\displaystyle x\neq 0}$.

في الواقع، القواسم المشتركة لـ${\displaystyle x}$و${\displaystyle 0}$جميع قواسم${\displaystyle x}$، منها${\displaystyle x}$هي الأكبر بحد ذاتها.

2.${\displaystyle \gcd(x,y)=\gcd(y,x-zy)}$

في الواقع، مجموعات القواسم المشتركة للأزواج${\displaystyle (x,y)}$و${\displaystyle (y,x-zy)}$متماثلان. وعلى وجه الخصوص، فإن أكبر قواسمهما المشتركة متماثل.

لتوضيح ذلك، افترض أن${\displaystyle d}$هو قاسم مشترك لـ${\displaystyle x}$و${\displaystyle y}$هذا يعني أن هناك أعدادًا صحيحة${\displaystyle X,Y}$بحيث${\displaystyle x=dX}$و${\displaystyle y=dY}$ويترتب على ذلك أن${\displaystyle x-zy=dX-zdY=d(X-zY)}$، أين${\displaystyle X-zY}$هو عدد صحيح. لذلك،${\displaystyle d}$وهو أيضًا قاسم لـ${\displaystyle x-zy}$.

على العكس من ذلك، إذا${\displaystyle d}$هو قاسم مشترك لـ${\displaystyle x-zy}$و${\displaystyle y}$ثم هناك أعداد صحيحة${\displaystyle Z}$و${\displaystyle Y}$بحيث${\displaystyle x-zy=dZ}$و${\displaystyle y=dY}$من هذا${\displaystyle x=(x-zy)+zy=dZ+zdY=d(Z+zY)}$، أين${\displaystyle Z+zY}$هو عدد صحيح. لذلك،${\displaystyle d}$وهو أيضًا قاسم مشترك لـ${\displaystyle x}$و${\displaystyle y}$.

الآن، تبدأ خوارزمية إقليدس بالزوج${\displaystyle (r_{-2},r_{-1})=(a,b)}$وفي كل خطوة، يكون زوج الباقي${\displaystyle (r_{k-2},r_{k-1})}$يتم استبدالها بـ${\displaystyle (r_{k-1},r_{k-2}-q_{k}r_{k-1})=(r_{k-1},r_{k})}$تُظهر الخاصية 2 أن${\displaystyle \gcd }$يظل عدد الأزواج ثابتًا. على وجه الخصوص،${\displaystyle \gcd }$من الزوج الأول${\displaystyle (a,b)}$والزوج الأخير${\displaystyle (r_{N-1},0)}$متماثلان. بتطبيق الخاصية 1،${\displaystyle \gcd(a,b)=\gcd(r_{N-1},0)=r_{N-1}}$.

على سبيل المثال، يمكن استخدام خوارزمية إقليدس لإيجاد القاسم المشترك الأكبر للعددين a = 1071 و b = 462. للبدء، تُطرح مضاعفات العدد 462 من 1071 حتى يصبح الباقي أقل من 462. يمكن طرح مضاعفين من هذه المضاعفات ( _q₀ = 2 )، فيتبقى باقي قدره 147 .

1071 = 2 × 462 + 147 .

ثم تُطرح مضاعفات العدد 147 من _العدد 462 حتى يصبح الباقي أقل من 147. يمكن طرح ثلاثة مضاعفات ( q1 = 3 )، فيتبقى باقي قدره 21 .

462 = 3 × 147 + 21

ثم تُطرح مضاعفات العدد ٢١ من ١٤٧ حتى يصبح الباقي أقل من ٢١. يمكن طرح سبعة مضاعفات ( q² = ٧ ₎ ، فلا يتبقى أي باقي.

147 = 7 × 21 + 0 .

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

يمكن تصور خوارزمية إقليدس باستخدام تشبيه التبليط المذكور أعلاه للقاسم المشترك الأكبر. ^{[ 16 ]} لنفترض أننا نريد تغطية مستطيل أبعاده a × b ببلاطات مربعة تمامًا، حيث a هو العدد الأكبر. نحاول أولًا تبليط المستطيل باستخدام b × b بلاطات مربعة؛ إلا أن هذا يترك مستطيلًا متبقيًا أبعاده r₀ _× b غير مُغطى، حيث r₀ < b . ثم نحاول تبليط المستطيل المتبقي ببلاطات _مربعة أبعادها _r₀ × r₀ . ينتج عن ذلك مستطيل متبقي ثانٍ أبعاده r₁ _× r₀ _، والذي نحاول تبليطه باستخدام بلاطات _{مربعة أبعادها} r₁ _× r₁ ، وهكذا. تنتهي العملية عندما لا يتبقى أي مستطيل متبقي، أي عندما تغطي البلاطات المربعة المستطيل المتبقي السابق تمامًا . طول أضلاع أصغر بلاطة مربعة هو القاسم المشترك الأكبر لأبعاد المستطيل الأصلي. على سبيل المثال، أصغر مربع في الشكل المجاور هو 21×21 (موضح باللون الأحمر)، و 21 هو القاسم المشترك الأكبر لـ 1071 و 462 ، وهما أبعاد المستطيل الأصلي (موضح باللون الأخضر).

في كل خطوة k ، تحسب خوارزمية إقليدس ناتج القسمة q _k والباقي r _k من عددين r _{k −1} و r _{k −2}

r _{k −2} = q _k r _{k −1} + r _k ,

حيث يكون r _k غير سالب وأقل تمامًا من القيمة المطلقة لـ r _{k −1} . تضمن النظرية التي يقوم عليها تعريف القسمة الإقليدية أن هذا الناتج والباقي موجودان دائمًا وفريدان. ^{[ 17 ]}

في النسخة الأصلية لخوارزمية إقليدس، يُحسب ناتج القسمة والباقي عن طريق الطرح المتكرر؛ أي يُطرح rk _{− 1 من} rk _{− 2} بشكل متكرر حتى يصبح الباقي rk أصغر من rk _{− 1.} بعد ذلك، _يُبدّل rk و _{rk −} 1 وتُكرر العملية. تُختزل القسمة الإقليدية جميع الخطوات بين عمليتي تبديل إلى خطوة واحدة، مما يجعلها أكثر كفاءة. علاوة على ذلك، لا حاجة لناتج القسمة، لذا يمكن استبدال القسمة الإقليدية بعملية باقي القسمة (modulo) ، التي تُعطي الباقي فقط. وهكذا _، يصبح تكرار خوارزمية إقليدس بسيطًا.

r _k = r _{k −2} mod r _{k −1} .

يمكن التعبير عن تطبيقات الخوارزمية باستخدام الشفرة الزائفة . على سبيل المثال، يمكن برمجة النسخة القائمة على القسمة على النحو التالي ^{[ 18 ]}

دالة gcd(a, b) طالما أن b ≠ 0 t := b b := a mod b أ := ت إرجاع أ

في بداية التكرار رقم k ، يحمل المتغير b قيمة الباقي الأخير rk _{− 1} ، بينما يحمل المتغير a _قيمة الباقي السابق rk _{− 2.} وتُكافئ الخطوة b  := a mod b صيغة الاستدعاء الذاتي المذكورة أعلاه rk ≡ rk _{− 2} mod _rk − _1. ويحتفظ المتغير المؤقت t بقيمة rk _{− 1} أثناء حساب الباقي التالي rk _. وفي نهاية تكرار الحلقة، يحمل المتغير b قيمة الباقي rk _، بينما يحمل المتغير a قيمة الباقي السابق rk _{− 1} .

(إذا كانت المدخلات السالبة مسموحة، أو إذا كانت modالدالة قد تُرجع قيمًا سالبة، فيجب استبدال السطر الأخير بـ return abs(a).)

في النسخة القائمة على الطرح، وهي النسخة الأصلية لإقليدس، يتم استبدال حساب الباقي ( ) بالطرح المتكرر. ^{[ 19 ]} على عكس النسخة القائمة على القسمة، والتي تعمل مع أي عدد صحيح كمدخلات، تفترض النسخة القائمة على الطرح أن المدخلات تتكون من أعداد صحيحة موجبة وتتوقف عندما يكون a = b .b := a mod b

دالة gcd(a, b) طالما أن a ≠ b إذا كان a > b أ := أ − ب آخر ب := ب − أ إرجاع أ

يتناوب المتغيران a و b في تمثيل الباقيين السابقين rk _{− 1} و rk _{− 2.} بافتراض أن a أكبر من b في بداية كل تكرار، فإن a يساوي rk _{− 2} ، لأن rk _{− 2} > rk _{− 1.} خلال التكرار، يُنقص a بمضاعفات الباقي السابق b حتى يصبح أصغر منه ، فيصبح a هو الباقي التالي rk. ثم يُنقص b بمضاعفات a حتى يصبح أصغر منه _مرة أخرى ، فيصبح الباقي التالي rk + 1 _{، وهكذا} .

يعتمد الإصدار التكراري ^{[ 20 ]} على تساوي القاسم المشترك الأكبر للبواقي المتتالية وشرط التوقف gcd( rN _{- 1,0} ) = rN _{- 1} .

دالة gcd(a, b) إذا كان b = 0 تُرجع a وإلا تُرجع gcd(b, a mod b)

(كما هو مذكور أعلاه، إذا كانت المدخلات السالبة مسموحة، أو إذا كانت الدالة قد تُرجع قيمًا سالبة، فيجب استبدال modالتعليمات بـ .)return areturn max(a, −a)

على سبيل المثال، يُحسب القاسم المشترك الأكبر للعددين 1071 و462 من القاسم المشترك الأكبر المكافئ لهما: القاسم المشترك الأكبر للعددين 462 و147 . ويُحسب القاسم المشترك الأكبر الأخير من القاسم المشترك الأكبر للعددين 147 و21، والذي يُحسب بدوره من القاسم المشترك الأكبر للعددين 21 و21 .

في نسخة أخرى من خوارزمية إقليدس، يُزاد ناتج القسمة في كل خطوة بمقدار واحد إذا كان الباقي السالب الناتج أصغر من الباقي الموجب المعتاد. ^{[ 21 ] [ 22 ]} سابقًا، كانت المعادلة

r _{k −2} = q _k r _{k −1} + r _k

بافتراض أن | rk ₋₁ | > rk _> 0. ومع ذلك _، يمكن حساب باقي قسمة سالب بديل e _{k :}

r _{k −2} = ( q _k + 1) r _{k −1} + e _k

إذا كان r _{k −1}  >  0 أو

r _{k −2} = ( q _k – 1) r _{k −1} + e _k

إذا كان r _{k −1}  <  0 .

إذا استُبدل rk بـ ek ، _وعندما يكون _| ek | < | rk | ، _فسنحصل على صيغة معدلة من خوارزمية إقليدس _بحيث

| rk | ≤ | rk _{−1 |} / 2_​

في كل خطوة.

أثبت ليوبولد كرونكر أن هذه النسخة تتطلب أقل عدد من الخطوات مقارنةً بأي نسخة أخرى من خوارزمية إقليدس. ^{[ 21 ] [ 22 ]} وبشكل أعم، فقد ثبت أنه لكل عددين مدخلين a و b ، يكون عدد الخطوات في حده الأدنى إذا وفقط إذا تم اختيار q _k بحيث${\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,}$أين${\displaystyle \varphi }$هي النسبة الذهبية . ^{[ 23 ]}

تنص متطابقة بيزو على أن القاسم المشترك الأكبر g لعددين صحيحين a و b يمكن تمثيله كمجموع خطي للعددين الأصليين a و b . ^{[ 53 ]} بعبارة أخرى، من الممكن دائمًا إيجاد عددين صحيحين s و t بحيث يكون g = sa + tb . ^{[ 54 ] [ 55 ]}

يمكن حساب العددين الصحيحين s و t من نواتج القسمة q₀ _و q₁ _وما إلى ذلك عن طريق عكس ترتيب المعادلات في خوارزمية إقليدس. [ ^{56 ] بدءًا} من المعادلة قبل الأخيرة، يمكن التعبير _عن g بدلالة _{ناتج القسمة} qN⁻¹ والباقيين _{السابقين} ، rN⁻² و _{rN⁻³ :}

g = r _{N −1} = r _{N −3} − q _{N −1} r _{N −2} .

ويمكن التعبير عن هذين الباقيين أيضاً بدلالة نواتج قسمتهما والباقي السابق لهما.

r _{N −2} = r _{N −4} − q _{N −2} r _{N −3} و

r _{N −3} = r _{N −5} − q _{N −3} r _{N −4} .

بإدخال هاتين الصيغتين لـ r_{_{N -2}} و r _{_{N -3}} في المعادلة الأولى، نحصل على g كمجموع خطي للبواقي r _{_{N -4}} و r_{_{N -5}}. ويمكن الاستمرار في عملية استبدال البواقي بصيغ تتضمن أسلافها حتى الوصول إلى العددين الأصليين a و b .

r ₂ = r ₀ − q ₂ r ₁

r ₁ = b − q ₁ r ₀

r ₀ = a − q ₀ b .

بعد استبدال جميع البواقي r ₀ ، r _{1 ، إلخ، فإن المعادلة النهائية تعبر عن} g كمجموع خطي لـ a و b ، بحيث يكون g = sa + tb .

يمكن تعميم خوارزمية إقليدس، وبالتالي هوية بيزو، إلى سياق المجالات الإقليدية .

تُقدّم متطابقة بيزو تعريفًا آخر للقاسم المشترك الأكبر g لعددين a و b . ^{[ 12 ]} لنفترض مجموعة جميع الأعداد ua + vb ، حيث u و v أي عددين صحيحين. بما أن a و b كلاهما يقبل القسمة على g ، فإن كل عدد في المجموعة يقبل القسمة على g . بعبارة أخرى، كل عدد في المجموعة هو مضاعف صحيح لـ g . هذا صحيح لكل قاسم مشترك لـ a و b . مع ذلك، على عكس القواسم المشتركة الأخرى، فإن القاسم المشترك الأكبر هو عنصر من المجموعة؛ فبحسب متطابقة بيزو، باختيار u = s و v = t نحصل على g . لا يمكن أن يكون القاسم المشترك الأصغر عنصرًا من المجموعة، لأن كل عنصر من المجموعة يجب أن يقبل القسمة على g . على العكس، يمكن الحصول على أي مضاعف m لـ g باختيار u = ms و v = mt ، حيث s و t هما العددان الصحيحان في متطابقة بيزو. ويمكن ملاحظة ذلك من خلال ضرب متطابقة بيزو في m ،

mg = msa + mtb .

لذا، فإن مجموعة جميع الأعداد ua + vb تُكافئ مجموعة مضاعفات العدد g . بعبارة أخرى، فإن مجموعة جميع المجاميع الممكنة لمضاعفات عددين صحيحين ( a و b ) تُكافئ مجموعة مضاعفات القاسم المشترك الأكبر (gcd( a , b )) . يُقال إن القاسم المشترك الأكبر هو مولد المثاليّين a و b . وقد أدى هذا التعريف للقاسم المشترك الأكبر إلى ظهور المفاهيم الجبرية المجردة الحديثة للمثاليّ الرئيسي (مثاليّ مُوَلَّد بواسطة عنصر واحد) ومجال المثاليّ الرئيسي ( مجال يكون فيه كل مثاليّ مثاليًّا رئيسيًّا).

يمكن حل بعض المسائل باستخدام هذه النتيجة. ^{[ 57 ]} على سبيل المثال، لنفترض وجود كوبين قياس حجمهما a و b . بجمع/طرح u من مضاعفات حجم الكوب الأول و v من مضاعفات حجم الكوب الثاني، يمكن قياس أي حجم ua + vb . جميع هذه الأحجام هي مضاعفات g = gcd( a , b ) .

يمكن حساب العددين الصحيحين s و t لهوية بيزو بكفاءة باستخدام خوارزمية إقليدس الموسعة . يضيف هذا التوسيع معادلتين تكراريتين إلى خوارزمية إقليدس ^{[ 58 ].}

s _k = s _{k −2} − q _k s _{k −1}

t _k = t _{k −2} − q _k t _{k −1}

مع القيم الأولية

s ₋₂ = 1، t ₋₂ = 0

s ₋₁ = 0، t ₋₁ = 1 .

باستخدام هذا التكرار، يتم إعطاء الأعداد الصحيحة s و t لـ Bézout بواسطة s = s _N و t = t _N ، حيث N + 1 هي الخطوة التي تنتهي عندها الخوارزمية مع r _{N +1} = 0 .

يمكن إثبات صحة هذا النهج بالاستقراء. افترض أن صيغة التكرار صحيحة حتى الخطوة k − 1 من الخوارزمية؛ بعبارة أخرى، افترض أن

r _j = s _j a + t _j b

لكل قيمة j أقل من k . تعطي الخطوة k من الخوارزمية المعادلة

r _k = r _{k −2} − q _k r _{k −1} .

بما أن صيغة التكرار قد افترضت أنها صحيحة بالنسبة لـ r _{k −2} و r _{k −1} ، فإنه يمكن التعبير عنها بدلالة المتغيرات s و t المقابلة.

r _k = ( s _{k −2} a + t _{k −2} b ) − q _k ( s _{k −1} a + t _{k −1} b ) .

بإعادة ترتيب هذه المعادلة نحصل على صيغة التكرار للخطوة k ، كما هو مطلوب

r _k = s _k a + t _k b = ( s _{k −2} − q _k s _{k −1} ) a + ( t _{k −2} − q _k t _{k −1} ) b .

يمكن أيضًا إيجاد العددين الصحيحين s و t باستخدام طريقة المصفوفة المكافئة . ^{[ 59 ]} سلسلة معادلات خوارزمية إقليدس

${\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{N-2}&=q_{N}r_{N-1}+0\end{aligned}}}$

يمكن كتابة ذلك كحاصل ضرب مصفوفات قسمة 2×2 في متجه باقي ثنائي الأبعاد

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}\,.}$

لنفترض أن M تمثل حاصل ضرب جميع مصفوفات القسمة

${\displaystyle \mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}\,.}$

هذا يبسط خوارزمية إقليدس إلى الشكل التالي:

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}\,.}$

للتعبير عن الدالة g كمجموع خطي للمتغيرين a و b ، يمكن ضرب طرفي هذه المعادلة في معكوس المصفوفة M. [ ^{59 ] [ 60 ]} محدد المصفوفة M يساوي (−1) ^{N + 1} ، لأنه يساوي حاصل ضرب محددات مصفوفات القسمة، وكل منها يساوي سالب واحد. وبما أن محدد المصفوفة M لا يساوي صفرًا أبدًا، يمكن إيجاد متجه البواقي النهائية باستخدام معكوس المصفوفة M.

${\displaystyle {\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}\,.}$

بما أن المعادلة العلوية تعطي

g = (−1) ^{N +1} ( m ₂₂ a − m ₁₂ b ) ,

العددان الصحيحان في متطابقة بيزو هما s = (−1) ^{N +1} m ₂₂ و t = (−1) ^N m _12. طريقة المصفوفة فعالة مثل التكرار المكافئ، مع عمليتي ضرب وعمليتي جمع لكل خطوة من خوارزمية إقليدس.

تُعدّ متطابقة بيزو أساسيةً للعديد من تطبيقات خوارزمية إقليدس، مثل إثبات التحليل الفريد للأعداد إلى عواملها الأولية. ^{[ 61 ]} ولتوضيح ذلك، لنفترض أن العدد L يُمكن كتابته كحاصل ضرب عاملين u و v ، أي L = uv . إذا كان هناك عدد آخر w يقسم L أيضًا ولكنه أولي نسبيًا مع u ، فإن w يجب أن يقسم v ، وذلك وفقًا للحجة التالية: إذا كان القاسم المشترك الأكبر لـ u و w هو 1 ، فإنه يُمكن إيجاد عددين صحيحين s و t بحيث

1 = su + tw

باستخدام متطابقة بيزو. بضرب كلا الطرفين في v نحصل على العلاقة التالية:

v = suv + twv = sL + twv

بما أن العدد w يقسم كلا الحدين في الطرف الأيمن، فلا بد أنه يقسم الطرف الأيسر v أيضًا . تُعرف هذه النتيجة باسم مبرهنة إقليدس . ^{[ 62 ]} تحديدًا، إذا كان عدد أولي يقسم L ، فلا بد أنه يقسم عاملًا واحدًا على الأقل من عوامل L. وعلى العكس، إذا كان العدد w أوليًا نسبيًا مع كل عدد من سلسلة الأعداد a₁ , _{a₂ ,} ... , an _، فإن w يكون ^أوليًا نسبيًا أيضًا مع حاصل ضربها، a₁ _× a₂ _× ... _× an . ^{[ 62} ]

تكفي مبرهنة إقليدس لإثبات أن لكل عدد تحليلًا فريدًا إلى عوامله الأولية. ^{[ 63 ]} ولإثبات ذلك، لنفترض العكس، أي أن هناك تحليلين مستقلين للعدد L إلى m و n من العوامل الأولية، على التوالي.

L = p ₁ p ₂ ... p _m = q ₁ q ₂ ... q _n  .

بما أن كل عدد أولي p يقسم L بحسب الفرض، فلا بد أنه يقسم أحد عوامل q أيضًا ؛ وبما أن كل q عدد أولي كذلك، فلا بد أن يكون p = q . وبقسمة كل عدد على عوامل p بشكل متكرر ، يتضح أن لكل p نظيرًا مساويًا له q ؛ فالتحليلان إلى عوامل أولية متطابقان تمامًا باستثناء الترتيب. وللتحليل الفريد للأعداد إلى عواملها الأولية تطبيقات عديدة في البراهين الرياضية، كما هو موضح أدناه.

المعادلات الديوفانتية هي معادلات تقتصر حلولها على الأعداد الصحيحة؛ وقد سُميت نسبةً إلى عالم الرياضيات الإسكندري ديوفانتوس الذي عاش في القرن الثالث الميلادي . ^{[ 64 ]} تسعى المعادلة الديوفانتية الخطية النموذجية إلى إيجاد عددين صحيحين x و y بحيث ^{[ 65 ]}

ax + by = c

حيث a و b و c أعداد صحيحة معطاة. يمكن كتابة ذلك كمعادلة لـ x في الحساب النمطي :

ax ≡ c mod b .

ليكن g القاسم المشترك الأكبر للمعادلتين a و b . كلا الحدين في المعادلة ax + by يقبلان القسمة على g ؛ لذا، يجب أن يكون c أيضًا قابلاً للقسمة على g ، وإلا فلن يكون للمعادلة حلول. بقسمة طرفي المعادلة على c / g ، يمكن اختزالها إلى متطابقة بيزو.

sa + tb = g ,

حيث يمكن إيجاد s و t بواسطة خوارزمية إقليدس الموسعة . ^{[ 66 ]} وهذا يوفر حلاً واحداً للمعادلة الديوفانتية _، x1 = s ( c / g ) و y1 = t ₍ c / g ) .

_{بشكل عام، إما أن} يكون للمعادلة الديوفانتية الخطية حلول معدومة، أو أن يكون لها عدد لا نهائي من الحلول. _{[ 67 ]} ^{لإيجاد الحل الأخير} ، نعتبر حلين، ( x1 , y1 ) و ( x2 , y2 ) ، حيث

ax ₁ + by ₁ = c = ax ₂ + by ₂

أو ما يعادل ذلك

أ ( x ₁ − x ₂ ) = ب ( y ₂ − y ₁ ) .

لذلك، فإن أصغر فرق بين حلين لـ x هو b / g ، بينما أصغر فرق بين حلين لـ y هو a / g . وبالتالي، يمكن التعبير عن الحلول كما يلي:

x = x ₁ − bu / g

y = y ₁ + au / g .

بجعل قيمة u متغيرة على جميع الأعداد الصحيحة الممكنة، يمكن توليد عدد لا نهائي من الحلول من حل واحد ( x1 , y1 ) . إذا اشترطنا أن تكون الحلول أعدادًا صحيحة موجبة ( x > 0, y > 0) ، فلن يكون _{هناك سوى عدد محدود من الحلول الممكنة. هذا القيد على الحلول المقبولة يسمح لبعض أنظمة المعادلات الديوفانتية التي تحتوي على عدد} من المجاهيل يفوق عدد المعادلات بأن يكون لها عدد محدود من الحلول؛ ^{[ 68 ]} وهذا مستحيل بالنسبة لنظام المعادلات الخطية عندما يمكن أن تكون الحلول أي عدد حقيقي (انظر: النظام غير المحدد ).

الحقل المنتهي هو مجموعة من الأعداد تتضمن أربع عمليات حسابية عامة. تُسمى هذه العمليات الجمع والطرح والضرب والقسمة، وتتمتع بخصائصها المعتادة، مثل التبديل والتجميع والتوزيع . مثال على حقل منتهٍ هو مجموعة الأعداد 13 {0،  1،  2،  ...،  12} باستخدام الحساب النمطي . في هذا الحقل، تُختزل نتائج أي عملية حسابية (الجمع، الطرح، الضرب، أو القسمة) بتردد 13 ؛ أي تُجمع أو تُطرح مضاعفات العدد 13 حتى تصبح النتيجة ضمن النطاق من 0 إلى 12. على سبيل المثال، نتيجة 5 × 7 = 35 بتردد 13 = 9. يمكن تعريف هذه الحقول المنتهية لأي عدد أولي p ؛ وباستخدام تعريفات أكثر دقة، يمكن تعريفها أيضًا لأي قوة m للعدد الأولي p ^. غالبًا ما تسمى الحقول المنتهية بحقول غالوا ، ويتم اختصارها إلى GF( p ) أو GF( pm ⁾ .

في حقل كهذا يحتوي على ^m عددًا ، لكل عنصر غير صفري a معكوس ضربي معياري فريد ، a⁻¹ ^، بحيث يكون aa⁻¹ ⁼ a⁻¹a ≡ 1 mod m . يمكن إيجاد هذا المعكوس بحل معادلة التطابق ax ≡ 1 mod m ، ^{[ 69 ]} أو المعادلة الديوفانتية الخطية المكافئة ^{[ 70 ]} .

ax + my = 1 .

يمكن حل هذه المعادلة باستخدام خوارزمية إقليدس، كما هو موضح أعلاه . يُعدّ إيجاد المعكوس الضربي خطوة أساسية في خوارزمية RSA ، المستخدمة على نطاق واسع في التجارة الإلكترونية ؛ وتحديدًا، تحدد هذه المعادلة العدد الصحيح المستخدم لفك تشفير الرسالة. ^{[ 71 ]} على الرغم من أن خوارزمية RSA تستخدم الحلقات بدلًا من الحقول، إلا أنه لا يزال بالإمكان استخدام خوارزمية إقليدس لإيجاد المعكوس الضربي حيثما وُجد. كما أن لخوارزمية إقليدس تطبيقات أخرى في رموز تصحيح الأخطاء ؛ فعلى سبيل المثال، يمكن استخدامها كبديل لخوارزمية بيرلكامب-ماسي لفك تشفير رموز BCH وريد -سولومون ، التي تعتمد على حقول غالوا. ^{[ 72 ]}

يمكن أيضًا استخدام خوارزمية إقليدس لحل معادلات ديوفانتية خطية متعددة. ^{[ 73 ]} تظهر هذه المعادلات في نظرية الباقي الصينية ، التي تصف طريقة جديدة لتمثيل عدد صحيح x . فبدلاً من تمثيل العدد الصحيح بأرقامه، يمكن تمثيله بباقي قسمته _xᵢ على مجموعة من N أعداد أولية فيما _بينها mᵢ : ^{[ 74 ]}

${\displaystyle {\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\&\,\,\,\vdots \\x_{N}&\equiv x{\pmod {m_{N}}}\,.\end{aligned}}}$

الهدف هو تحديد قيمة x من باقي قسمتها N، xᵢ _. يكمن الحل في دمج المعادلات المتعددة في معادلة ديوفانتية خطية واحدة ذات معيار أكبر بكثير M، _وهو حاصل ضرب جميع المعايير الفردية mᵢ _، وتعريف Mᵢ على النحو التالي:

${\displaystyle M_{i}={\frac {M}{m_{i}}}.}$

وبالتالي، فإن كل قيمة من _قيم Mi هي حاصل ضرب جميع المعاملات باستثناء m _i . ويعتمد الحل على إيجاد N عددًا جديدًا من قيم h _i بحيث

${\displaystyle M_{i}h_{i}\equiv 1{\pmod {m_{i}}}\,.}$

باستخدام هذه الأرقام h _i ، يمكن إعادة بناء أي عدد صحيح x من باقي قسمته x _i بواسطة المعادلة

${\displaystyle x\equiv (x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots +x_{N}M_{N}h_{N}){\pmod {M}}\,.}$

بما أن هذه الأرقام h _i هي المعكوسات الضربية لـ M _i ، فإنه يمكن إيجادها باستخدام خوارزمية إقليدس كما هو موضح في القسم الفرعي السابق.

يمكن استخدام خوارزمية إقليدس لترتيب مجموعة جميع الأعداد النسبية الموجبة في شجرة بحث ثنائية لانهائية ، تُسمى شجرة ستيرن-بروكوت . يُوضع العدد 1 (المُعبَّر عنه ككسر 1/1) في جذر الشجرة، ويمكن إيجاد موقع أي عدد آخر a / b بحساب القاسم المشترك الأكبر (gcd( a , b )) باستخدام الصيغة الأصلية لخوارزمية إقليدس، حيث تستبدل كل خطوة العدد الأكبر من العددين المُعطيين بفرقه مع العدد الأصغر (وليس باقيه)، وتتوقف عند الوصول إلى عددين متساويين. تُقابل خطوة خوارزمية إقليدس التي تستبدل العدد الأول خطوة في الشجرة من عقدة إلى ابنها الأيمن، وتُقابل خطوة تستبدل العدد الثاني خطوة في الشجرة من عقدة إلى ابنها الأيسر. لا يعتمد تسلسل الخطوات المُنشأ بهذه الطريقة على ما إذا كان a / b مُعطى في أبسط صورة، ويُشكّل مسارًا من الجذر إلى عقدة تحتوي على العدد a / b . ^{[ 75 ]} يمكن استخدام هذه الحقيقة لإثبات أن كل عدد نسبي موجب يظهر مرة واحدة بالضبط في هذه الشجرة.

على سبيل المثال، يمكن إيجاد 3/4 بالبدء من الجذر، والتحرك إلى اليسار مرة واحدة، ثم إلى اليمين مرتين:

${\displaystyle {\begin{aligned}&\gcd(3,4)&\leftarrow \\={}&\gcd(3,1)&\rightarrow \\={}&\gcd(2,1)&\rightarrow \\={}&\gcd(1,1).\end{aligned}}}$

تتشابه خوارزمية إقليدس تقريبًا مع شجرة ثنائية أخرى على الأعداد النسبية تُسمى شجرة كالكين-ويلف . ويكمن الاختلاف في أن المسار معكوس: فبدلًا من إنشاء مسار من جذر الشجرة إلى الهدف، تُنشئ مسارًا من الهدف إلى الجذر.

ترتبط خوارزمية إقليدس ارتباطًا وثيقًا بالكسور المستمرة . ^{[ 76 ]} يمكن كتابة سلسلة المعادلات على الصورة التالية:

${\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&\,\,\,\vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&\,\,\,\vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\,.\end{aligned}}}$

الحد الأخير في الطرف الأيمن يساوي دائمًا معكوس الطرف الأيسر للمعادلة التالية. وبالتالي، يمكن دمج المعادلتين الأوليين لتكوين

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}\,.}$

يمكن استخدام المعادلة الثالثة لاستبدال حد المقام r1 _/ r0 ، مما ينتج _عنه

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}\,.}$

يمكن دائمًا استبدال النسبة النهائية للبواقي rk / rk _{−1 باستخدام المعادلة التالية في} المتسلسلة، وصولًا إلى المعادلة الأخيرة. والنتيجة هي كسر مستمر _.

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]\,.}$

في المثال المحلول أعلاه ، تم حساب القاسم المشترك الأكبر للعددين 1071 و462، وكانت نواتج القسمة q _k هي 2 و3 و7 على التوالي. لذلك، يمكن كتابة الكسر 1071/462 على النحو التالي:

${\displaystyle {\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]}$

كما يمكن تأكيده بالحساب.

يُعدّ حساب القاسم المشترك الأكبر خطوةً أساسيةً في العديد من خوارزميات تحليل الأعداد الصحيحة إلى عواملها الأولية ، ^{[ 77 ]} مثل خوارزمية بولارد رو ، ^{[ 78 ]} وخوارزمية شور ، ^{[ 79 ]} وطريقة ديكسون للتحليل إلى عوامل أولية ^{، [ 80 ]} وتحليل لينسترا باستخدام المنحنى الإهليلجي . ^{[ 81 ]} ويمكن استخدام خوارزمية إقليدس لإيجاد هذا القاسم المشترك الأكبر بكفاءة. أما تحليل الكسور المستمرة فيعتمد على الكسور المستمرة، والتي تُحدد باستخدام خوارزمية إقليدس. ^{[ 82 ]}

يمكن التعبير عن عدد الخطوات اللازمة لحساب القاسم المشترك الأكبر لعددين طبيعيين، a و b ، بالرمز T ( a , b ). ^{[ 93 ]} إذا كان g هو القاسم المشترك الأكبر لـ a و b ، فإن a = mg و b = ng لعددين أوليين فيما بينهما m و n .     

T ( a , b ) = T ( m , n )

كما يتضح من قسمة جميع خطوات خوارزمية إقليدس على g . ^{[ 94 ]} وبناءً على الحجة نفسها، يظل عدد الخطوات ثابتًا إذا ضُرب a و b بعامل مشترك w : T ( a , b ) = T ( wa , wb ). لذلك، قد يختلف عدد الخطوات T اختلافًا كبيرًا بين أزواج الأعداد المتجاورة، مثل T( a , b ) و T( a , b + 1)، اعتمادًا على حجم القاسم المشترك الأكبر لكل منهما.   

تُعطي الطبيعة التكرارية لخوارزمية إقليدس معادلة أخرى

T ( a , b ) = 1 + _T ( b , r0 ) = 2 + T ( r0 _, r1 ₎ = … = N + T ( rN - ₂ , rN _{- 1 )} = N + 1

حيث T ( x , 0)  =  0 حسب الفرضية. ^{[ 93 ]}

في كل خطوة k من خوارزمية إقليدس، يتم حساب ناتج القسمة q _k والباقي r _k لزوج معين من الأعداد الصحيحة r _{k −2} و r _{k −1}

r _{k −2} = q _k r _{k −1} + r _k .

يرتبط العبء الحسابي لكل خطوة بشكل رئيسي بإيجاد قيمة q _k ، حيث يمكن حساب الباقي r _k بسرعة من r _{k −2} و r _{k −1} و q _k

r _k = r _{k −2} − q _k r _{k −1} .

تتناسب التكلفة الحسابية لقسمة الأعداد المكونة من h بت مع O ( h ( ℓ + 1)) ، حيث ℓ هو طول ناتج القسمة. ^{[ 90 ]}

للمقارنة، قد تكون خوارزمية إقليدس الأصلية القائمة على الطرح أبطأ بكثير. فعملية قسمة عدد صحيح واحد تعادل ناتج قسمة يساوي q عملية طرح. إذا كانت نسبة a إلى b كبيرة جدًا، فسيكون ناتج القسمة كبيرًا، وسيتطلب الأمر العديد من عمليات الطرح. من ناحية أخرى، فقد ثبت أن نواتج القسمة غالبًا ما تكون أعدادًا صحيحة صغيرة. احتمال ناتج قسمة معين q يُقارب ln | u /( u - 1) |، حيث u = ( q + 1) ^² . ^{[ 111 ]} على سبيل المثال، احتمال ناتج قسمة يساوي 1 أو 2 أو 3 أو 4 هو 41.5% و17.0% و9.3% و5.9% تقريبًا، على التوالي. بما أن عملية الطرح أسرع من عملية القسمة، خاصةً للأعداد الكبيرة، ^{[ 112 ]} فإن خوارزمية إقليدس القائمة على الطرح تُنافس النسخة القائمة على القسمة. ^{[ 113 ]} يتم استغلال هذا في النسخة الثنائية من خوارزمية إقليدس. ^{[ 114 ]}

^{بدمج عدد الخطوات المُقدَّر مع التكلفة الحسابية المُقدَّرة لكل خطوة ،} يتضح أن خوارزمية إقليدس تنمو تربيعيًا ( h² ) مع متوسط ​​عدد الأرقام h في العددين الأوليين a و b . لنفترض أن _h₀ ، _h₁ ، _... ، _hₙ₋₁ تُمثل عدد الأرقام في البواقي المتتالية r₀ _، r₁ _، ...، _rₙ₋₁ . _بما أن عدد الخطوات N ينمو خطيًا مع h ، فإن زمن التشغيل محدود بـ

${\displaystyle O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).}$

تُستخدم خوارزمية إقليدس على نطاق واسع في التطبيقات العملية، لا سيما مع الأعداد الصغيرة، نظرًا لبساطتها. ^{[ 115 ]} وللمقارنة، يمكن تحديد كفاءة البدائل لخوارزمية إقليدس.

إحدى الطرق غير الفعالة لإيجاد القاسم المشترك الأكبر لعددين طبيعيين a و b هي حساب جميع قواسمهما المشتركة؛ إذ يكون القاسم المشترك الأكبر هو أكبر قاسم مشترك. ويمكن إيجاد القواسم المشتركة بقسمة كلا العددين على أعداد صحيحة متتالية من 2 إلى العدد الأصغر b . ويتزايد عدد خطوات هذه الطريقة خطيًا مع b ، أو أُسّيًا مع عدد الأرقام. وهناك طريقة أخرى غير فعالة وهي إيجاد العوامل الأولية لأحد العددين أو كليهما. وكما ذُكر سابقًا ، فإن القاسم المشترك الأكبر يساوي حاصل ضرب العوامل الأولية المشتركة بين العددين a و b . ^{[ 8 ]} كما أن الطرق الحالية لتحليل الأعداد إلى عواملها الأولية غير فعالة أيضًا؛ بل إن العديد من أنظمة التشفير الحديثة تعتمد على هذا القصور. ^{[ 11 ]}

تُعدّ خوارزمية القاسم المشترك الأكبر الثنائية بديلاً فعالاً يستبدل القسمة بعمليات أسرع من خلال استغلال التمثيل الثنائي المستخدم في الحواسيب. ^{[ 116 ] [ 117 ]} ومع ذلك، فإن هذا البديل يتوسع أيضًا بمعدل O ( h² ) . وهو أسرع عمومًا من خوارزمية إقليدس على الحواسيب الحقيقية، على الرغم من أنه يتوسع بنفس الطريقة. ^{[ 91 ]} ويمكن تحقيق كفاءة إضافية من خلال فحص الأرقام الأولى فقط من العددين a و b . ^{[ 118 ] [ 119 ]} ويمكن توسيع الخوارزمية الثنائية لتشمل أنظمة عد أخرى ( خوارزميات k -ary)، ^{[ 120 ]} مع زيادة في السرعة تصل إلى خمسة أضعاف. ^{[ 121 ]} وتستخدم خوارزمية ليمر للقاسم المشترك الأكبر نفس المبدأ العام للخوارزمية الثنائية لتسريع حسابات القاسم المشترك الأكبر في أنظمة العد المختلفة.

يؤدي استخدام أسلوب تكراري للأعداد الصحيحة الكبيرة جدًا (التي يزيد عدد أرقامها عن 25000) إلى خوارزميات شبه خطية لإيجاد القاسم المشترك الأكبر للأعداد الصحيحة، ^{[ 122 ]} مثل خوارزميات شونهاج، ^{[ 123 ] [ 124 ]} وستيهلي وزيمرمان. ^{[ 125 ]} تستغل هذه الخوارزميات شكل المصفوفة 2×2 لخوارزمية إقليدس المذكورة أعلاه . وتتناسب هذه الطرق شبه الخطية عمومًا مع O ( h log h² log log h ⁾ . ^{[ 91 ] [ 92 ]}

يمكن تطبيق خوارزمية إقليدس على الأعداد الحقيقية ، كما وصفها إقليدس في الكتاب العاشر من كتابه " الأصول" . تهدف الخوارزمية إلى تحديد عدد حقيقي g بحيث يكون عددان حقيقيان معطيان، a و b ، من مضاعفاته الصحيحة: a = mg و b = ng ، حيث m و n عددان صحيحان . [ ^{25 ] هذا} التحديد يُكافئ إيجاد علاقة عددية صحيحة بين العددين الحقيقيين a و b ؛ أي أنه يُحدد عددين صحيحين s و t بحيث يكون sa + tb = 0. إذا كانت هذه المعادلة ممكنة، يُطلق على a و b اسم أطوال قابلة للقياس، وإلا فهما أطوال غير قابلة للقياس . ^{[ 129 ] [ 130 ]}

تختلف خوارزمية إقليدس للأعداد الحقيقية عن نظيرتها للأعداد الصحيحة في جانبين. أولًا، تكون البواقي r _k أعدادًا حقيقية، على الرغم من أن نواتج القسمة q _k أعداد صحيحة كما في السابق. ثانيًا، لا يُضمن أن تنتهي الخوارزمية عند عدد محدود N من الخطوات. إذا انتهت عند عدد محدود، فإن الكسر a / b يكون عددًا نسبيًا، أي نسبة عددين صحيحين.

${\displaystyle {\frac {a}{b}}={\frac {mg}{ng}}={\frac {m}{n}},}$

ويمكن كتابتها على شكل كسر مستمر محدود [ q₀ ; q₁ _, q₂ , ..., qₙ ] . إذا لم تتوقف الخوارزمية، فإن الكسر a / b يكون عددًا غير نسبي _، ويمكن وصفه بكسر مستمر غير محدود _[ q₀ ; q₁ , _{q₂ ,} ...] . ^{[ 131 ]} من أمثلة الكسور المستمرة غير المحدودة النسبة الذهبية φ = [1; 1, 1, ...] _والجذر التربيعي للعدد 2 ، _√2 = [1; 2, 2, ...] . [ 132 ] ^{عند تطبيقها على} عددين حقيقيين عشوائيين، فمن غير المرجح أن تتوقف الخوارزمية، لأن جميع نسب a / b تقريبًا بين عددين حقيقيين هي أعداد غير نسبية. ^{[ 133 ]}

يمكن اقتطاع كسر مستمر لانهائي عند خطوة k [ q₀ ; q₁ _, q₂ _, ..., qₖ _] للحصول على تقريب لـ a/ b يتحسن مع زيادة k . يُوصف هذا التقريب بمُقاربات mₖ / _nₖ ؛ _البسط والمقام أوليان فيما بينهما ويخضعان لعلاقة التكرار _.

${\displaystyle {\begin{aligned}m_{k}&=q_{k}m_{k-1}+m_{k-2}\\n_{k}&=q_{k}n_{k-1}+n_{k-2},\end{aligned}}}$