عرض مصدر خوارزمية أقليدس

{{بطاقة خوارزمية}}
[[ملف:Euclid's algorithm Book VII Proposition 2 3.png|300px|thumb|left|طريقة أقليدس لإيجاد القاسم المشترك الأكبر لعددين ابتُدأ بهما ممثلين بالقطعتين AB و CD، عُرفا كل منهما على أنهما مضاعفين لوحدة طول مشتركة. بما أن طول CD أقصر من AB، استعمل لقياس AB، ولكنه قاسه مرة واحدة لأن الباقي EA أصغر قطعا من CD. الآن، EA تقيس (مرتين) الطول الأقصر DC، حيث الباقي FC أقصر من EA. إذن، FC تقيس (ثلاث مرات) الطولEA. لأنه لم يبق أي باق، تتوقف العملية مع كون FC القاسم المشترك الأكبر. في اليمين، مثال [[نيكوماكوس]] مع الأعداد 49 و21 معطيا قاسمهما المشترك الأكبر مساويا لسبعة. (أُخذ من Heath 1908:300).]]

في [[رياضيات|الرياضيات]]، '''خوارزمية أقليدس''' {{إنج|Euclidean algorithm}} هي طريقة فعالة تمكن من إيجاد [[قاسم مشترك أكبر|القاسم المشترك الأكبر]] لعددين وهو أكبر عدد يقسم في نفس الوقت العددين معا بدون أي [[باق (رياضيات)|باق]] من القسمة. يُرمز له بالفرنسية ب PGCD وبالإنجليزية GCD. 
سميت هذه الخوارزمية هكذا نسبة إلى عالم الرياضيات الإغريقي [[إقليدس|أقليدس]] الذي وصف الخوارزمية لأول مرة في كتابه المعروف باسم [[الأصول (كتاب)|الأصول]] (حوالي عام 300 ق.م). هي مثال عن الخوارزميات (الخوارزمية طريقةٌ تمكن من القيام بعملية ما، خطوة خطوة طِبقا لقواعد معينة محددة مسبقا). وهو من أقدم الخوارزميات اللائي ما زلن قيد الاستعمال. قد تستعمل من أجل اختزال كسر إلى [[كسر غير قابل للاختزال|شكله المبسط غير القابل للاختزال]]، وهي جزء من الحسابات المتعلقة بنظرية الأعداد والتشفير.

تعتمد خوارزمية أقليدس على مبدأ أن القاسم المشترك الأكبر لعددين لا يتغير إذا عُوض أكبرهما بالفرق بينه وبين أصغرهما. على سبيل المثال، 21 هو القاسم المشترك الأكبر للعددين 252 و 105 (نظرا إلى أن 252 = 21 * 12 و 105 = 21 * 5)، وأن 21 هو أيضا القاسم المشترك الأكبر ل 105 و 252 - 105 = 147. بقلب مراحل خوارزمية أقليدس، الأخيرة، فما قبلها، فما قبلها وهكذا، يُحصل على صيغة يُعبر فيها عن القاسم المشترك الأكبر [[تركيب خطي|بتأليفة خطية]] للعددين الأصليين، أي على شكل مجموعهما بعد ضرب كل واحد منهما في عدد صحيح ما. على سبيل المثال، <math>21=5*105+(-2)*252</math>. تعرف هذه المسألة [[متطابقة بيزو|بمتطابقة بيزو]] نسبة إلى عالم الرياضيات الفرنسي [[إيتيان بيزو]].

الصيغة التي وُصفت أعلاه لخوارزمية أقليدس (وهكذا وصفها إقليدس) قد تتأخر أثناء عملية حساب الفرق بين أكبر العددين وأصغرهما، خصوصا إذا كان العدد الأكبر أكبر بكثير من العدد الأصغر. هناك صيغة أكثر سرعة من هذه الصيغة، تمكن من اختصار هذه المراحل. بدلا من تعويض أكبر العددين بالفرق بينه وبين أصغر العددين، يُعوض أكبر العددين بباقي قسمته على أصغر العددين. في هذه الطريقة، الخوارزمية تتوقف عندما يصيرا الباقي مساويا للصفر. تطبيقا لهذه الطريقة، الخوارزمية لا تتطلب أبدا، من الخطوات ما يتجاوز خمسة أضعاف عدد أرقام العدد المقسوم عليه، مكتوبا في القاعدة 10. برهن على هذه المسألة عالم الرياضيات الفرنسي [[غابرييل لامي]]. كان ذلك عام 1844، غارسا بذلك البذرة الأولى [[نظرية التعقيد الحسابي|لعلم التعقد الحسابي]]. رأت النور خلال القرن العشرين طرق إضافية مكنت من جعل الخوارزمية أكثر قوة وسرعة.

لخوارزمية أقليدس العديد من التطبيقات النظرية والعملية. تستعمل من أجل اختزال [[كسر (رياضيات)|الكسور]] إلى [[كسر غير قابل للاختزال|شكلها المبسط]]. تستعمل أيضا في أثناء [[قسمة (رياضيات)|القسمة]] في إطار [[حسابيات معيارية|الحسابيات النمطية]]. قد تشكل بعض من الحسابات المستعملة لهذه الخوارزمية، جزءا من [[بروتوكول تعمية|بروتوكولات التعمية]] التي بفضلها تؤمن الاتصالات عبر الأنترنيت. وتستعمل أيضا في طرق تمكن من كسر هذه الأنظمة التشفيرية؛ وذلك ب[[تحليل عدد صحيح إلى عوامل]]. تستعمل خوارزمية أقليدس في حلحلة بعض الأشكال الخاصة من [[معادلة ديفونتية|المعادلات الديوفانتية]]، من قبيل ايجاد أعداد صحيحة تحقق معادلات تردُدية عدة في إطار [[مبرهنة الباقي الصينية]]، ومن قبيل إنشاء [[كسر مستمر|الكسور المستمرة]] ومن أجل ايجاد [[تقريب ديوفانتي|قيم مقربة جذرية]] لأعداد حقيقية. أضف إلى ذلك أنها تستعمل حجرَ أساس في البرهان على مبرهنات في [[نظرية الأعداد]] من قبيل [[مبرهنة المربعات الأربع للاغرانج]] و[[المبرهنة الأساسية في الحسابيات]]. صُممت الخوارزمية في الأصل من أجل العمل على قسمة الأعداد الطبيعية والقياسات الهندسية، ولكنها عُممت خلال القرن التاسع عشر على كائنات ر ياضية أخرى. [[عدد صحيح غاوسي|الأعداد الصحيحة الغاوسية]] و[[متعددة الحدود|متعددات الحدود]] ذات متغير واحد مثالان على ذلك.

== مثال ==
القاسم المشترك الأكبر ل 48 و 60 هو 12.

القاسم المشترك الأكبر للعددين 252 و 198:

252 = 198 * 1 + 54 ‘ أربع وخمسون هو باقي قسمة 252 على 198

فنجد القاسم المشترك للعددين 198 و 54

198 = 54 * 3 + 36 ‘ ست وثلاثون هو باقي القسمة.

نكرر العملية هذه المرة مع: 54 و 36

54 = 36 * 1 + 18

مرة أخرى:
36 = 18 * 2 + 0

هنا وصلنا للصفر فيكون العدد الثاني 18 هو القاسم المشترك الأكبر.

== الخلفية: القاسم المشترك الأكبر ==
{{مفصلة|قاسم مشترك أكبر}}

== وصف الخوارزمية ==

القاسم المشترك الأكبر لعددين طبيعيين A، B يساوي القاسم المشترك الأكبر للعدد الثاني B وباقي قسمة A على B، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر.
حيث r هو باقي قسمة A على B.

N هو القاسم المشترك الأكبر.

== التطور التاريخي ==
[[ملف:Euklid.jpg|thumb|alt="Depiction of Euclid as a bearded man holding a pair of dividers to a tablet."|من المحتمل أن تكون الخوارزمية الإقليدية قد اكتشفت قرونا قبل [[إقليدس]]. بُين هنا في رسم يعود تاريخه إلى عام 1474، حاملا ل[[مسماك|قدمة ذات الورنية]]]]

خوارزمية أقليدس هي واحدة من أقدم الخوارزميات الجارية الاستعمال. ظهرت في كتاب [[الأصول (كتاب)|الأصول]] لإقليدس (في حوالي عام 300 قبل الميلاد)، وبالتحديد في الكتاب السابع (الخاصيتان الأولى والثانية) والكتاب العاشر (الخاصيتان الثانية والثالثة). في الكاتب السابع، طُبقت الخوارزمية على الأعداد الطبيعية بينما في الكتاب العاشر، طُبقت على أطوال القطع المستقيمة.

خلال القرن التاسع عشر، فتحت خوارزمية أقليدس الباب نحو تطور أنظمة عددية جديدة. [[عدد صحيح غاوسي|الأعداد الغاوسية]] و[[عدد أيزنشتاين الصحيح|أعداد أيزنشتاين]] مثالان على ذلك. في عام 1815، استعمل [[كارل فريدريش غاوس|غاوس]] خوارزمية أقليدس من أجل البرهان على وحدانية تفكيك [[عدد صحيح غاوسي|الأعداد الغاوسية]]. رغم أن العمل قِيم بي في عام 1815، إلا أنه لم ينشر لأول مرة إلي في عام 1832. أشار غاوس إلى الخوارزمية في كتابه [[استفسارات حسابية (كتاب)|استفسارات حسابية]] والذي نُشر في عام 1801، ولكن فقط في شكل طريقة تمكن من حساب [[كسر مستمر|الكسور المستمرة]].

== تطبيقات رياضياتية ==
=== متطابقة بيزو ===
تنص [[متطابقة بيزو]] على أن القاسم المشترك الأكبر g لعددين a و b يمكن أن يمثل مجموعا خطيا للعددين a و b؛ أي أنه يوجد عددان، s و t حيث يتوفر ما يلي:
<math>g = sa + tb</math>

=== الخوارزمية الإقليدية الممتدة ===
{{مفصلة|خوارزمية إقليدس الممددة}}

یمكن تمثیل القاسم المشترك الأكبر للعددین عن طریق دمج خطي مع عددین آخرین،

كیف یمكن أیجاد قیمتي n و m وذلك عن طریق خوارزمیة اقلیدس الممتدة وهناك ثلاثة طرق لمعرفة هذه القیم (الطرق هي مشابه لبعض، لكن یمكن القول أنها مختصره من الأخریات).
الطريقة الأولى: وهي يمكن ان نطلق عليها التراجع وفي هذه الطريقة نقوم بالحل عن طريق خوارزمية اقليدس وبعدها تقول بالتراجع الخلفي لايجاد قيمتي m،n كما في المثال التالي:
مثال: قم بتمثيل العددين 26 و 21 بطريقة اقليدس الممتدة:
فنبدأ بالحل كما هو الحال في طريقة اقليدس:
26 = 1* 21 + 5 و 21 = 4 * 5 + 1 و 5 = 5 * 1 + 0
وتتوقف عند الصفر. الآن المعادلة التي قبل المعادلة التي باقيها صفر أي المعادلة الثانية نقوم بكتابتها بالشكل التالي:
:<math>1=21-4*5</math>
أیضا المعادلة الأولى بنفس الشكل:
:<math>5=26-1*21</math>

في المعادلتين السابقتين
:1 = 21 – 4 * (26 – 1 * 21)

ومن غیر أجراء عملیة حسابیة، فقط نفك القوس لینتج:
1 = 21 -4*26 +4*21
1=21(1+4)-4*26 حيث 21 عامل مشترك
لیكون لدینا الناتج النهائي: 4*21 +21

1 = 5*21 + (-4)*26
نتاكد من النتيجة 5*21+ -4*26 والناتج يساوي واحد إذاً المعادلة صحيحة

إذاً قيمة m هي 5 وقيمة n هي -4.

=== طريقة المصفوفات ===
: <math>
\begin{align}
a & = q_0 b + r_0 \\
b & = q_1 r_0 + r_1 \\
& \,\,\,\vdots \\
r_{N-2} & = q_N r_{N-1} + 0
\end{align}
</math>

:<math>
\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} \,.
</math>

:<math>
\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} \,.
</math>

:<math> 
\begin{pmatrix} a \\ b \end{pmatrix} =
\mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} =
\mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix} \,.
</math>

:<math>
\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} \,.
</math>

: {{تعبير رياضي|1=''g'' = (−1)<sup>''N''+1</sup> ( ''m''<sub>22</sub> ''a'' − ''m''<sub>12</sub> ''b''),}}

=== المعادلات الديوفانتية الخطية ===
يمكن لخوارزمية أقليدس أيضا أن تستعمل من أجل حلحلة العديد من [[معادلة ديفونتية|المعادلات الديوفانتية]] الخطية. تظهر واحدة من هده المعادلات في [[مبرهنة الباقي الصينية|مبرهنة الباقي الصيني]].

: <math>
\begin{align}
x_1 & \equiv x \bmod m_1 \\
x_2 & \equiv x \bmod m_2 \\
& \vdots \\
x_N & \equiv x \bmod m_N\,.
\end{align}
</math>

=== مبرهنة الباقي الصيني ===
[[مبرهنة الباقي الصينية|مبرهنة الباقي الصيني]]

: <math>
\begin{align}
x_1 & \equiv x \pmod {m_1} \\
x_2 & \equiv x \pmod {m_2} \\
& \,\,\,\vdots \\
x_N & \equiv x \pmod {m_N} \,.
\end{align}
</math>

=== شجرة ستيرن-بروكوت ===
[[ملف:SternBrocotTree.svg|thumb|300px|شجرة ستيرن-بروكوت، و متتاليات ستيرن-بروكوت من الرتبة ''i'' حيث ''i'' = 1، 2، 3، 4.]]

تُستعمل خوارزمية أقليدس من أجل ترتيب جميع [[عدد كسري|الأعداد الجذرية]] الموجبة في [[شجرة ثنائية البحث]] غير منتهية، تسمى [[شجرة ستيرن-بروكوت]].

=== الكسور المستمرة ===
:<math>
\begin{align}
\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{align}
</math>

:<math>\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac{r_1}{r_0}} \,.</math>

:<math>\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac 1 {q_2 + \cfrac{r_2}{r_1}}}\,. </math>

:<math>\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 ] \,.</math>

:<math>\frac{1071}{462} = 2 + \cfrac 1 {3 + \cfrac 1 7} = [2; 3, 7]</math>

== الفعالية الخوارزمية ==
[[ملف:Euclidean algorithm running time X Y.png|thumb|alt="A set of colored lines radiating outwards from the origin of an ''x''-''y'' coordinate system. Each line corresponds to a set of number pairs requiring the same number of steps in the Euclidean algorithm."|عدد الخطوات المطلوبة في الخوارزمية الإقليدية لحساب القاسم المشترك الأكبر(''x''،''y''). النقط الحمراء تدل على عدد صغير نسبيا من الخطوات (سريع)، بينما النقط الصفراء والخضراء والزرقاء تدل على عدد أكبر على التوالي من النقط (بطيء). المنطقة الداكنة الزرقاء تخضع لمعادلة المستقيم ''y'' = Φ''x''، حيث Φ يمثل [[نسبة ذهبية|النسبة الذهبية]].]]

دُرست فعالية خوارزمية أقليدس بشكل كثيف. تتمثل هذه الفعالية في عدد الخطوات اللازمة من أجل إيجاد القاسم المشترك الأكبر المراد حسابه. أول تحليل لفعالية الخوارزمية يرجع إلى العالم [[غيينو]]، (كان ذلك عام 1811)، حيث أثبت أنه أثناء حساب القاسم المشترك الأكبر للعددين u و v، عدد الخطوات اللازمة، لا يمكن أن يتجاوز v. وزاد فيما بعد هذا البرهانَ دقة عندما برهن أن هذا العدد لا يمكن أن يتجاوز v/2 +2.

انظر إلى [[بيير جوزيف إتيان فينك]]. في عام 1837، درس [[إيميل ليجي]] أسوأ حالة، والتي هي حيث يكون المقسوم والمقسوم عليه عددان متتاليان من [[عدد فيبوناتشي|متتالية فيبوناتشي]]. واصل [[غابرييل لامي]] سير فينك في عام 1844، مبرهنا على أن عدد خطوات خوارزمية إقليدس لا تتجاوز أبدا خمس مرات عدد الأرقام اللائي يكونن المقسوم عليه، مكتوبا في القاعدة العشرية.

== في النظم العددية الأخرى ==
=== الأعداد الجذرية والأعداد الحقيقية ===
=== متعددات الحدود ===
{{مفصلة|القاسم المشترك الأكبر لمتعددتي حدود}}

:<math>r_{k-2}(x) = q_k(x)r_{k-1}(x) + r_k(x),</math>

:<math>\begin{align}
   a(x) &= x^4 - 4x^3 + 4x^2 - 3x + 14 = (x^2 - 5x + 7)(x^2 + x + 2) \qquad \text{and}\\
   b(x) &= x^4 + 8x^3 + 12x^2 + 17x + 6 = (x^2 + 7x + 3)(x^2 + x + 2).
 \end{align}</math>

=== الأعداد الطبيعية الغاوسية ===
[[ملف:Gaussian primes.svg|thumb|alt="A set of dots lying within a circle. The pattern of dots has fourfold symmetry، i.e.، rotations by 90 degrees leave the pattern unchanged. The pattern can also be mirrored about four lines passing through the center of the circle: the vertical and horizontal axes، and the two diagonal lines at ±45 degrees."|توزيع الأعداد الطبيعية الغاوسية ''u''&nbsp;+&nbsp;''vi'' في المستوى العقدي، من معايير ''u''<sup>2</sup>&nbsp;+&nbsp;''v''<sup>2</sup> أصغر من 500]]

الأعداد الغاوسية الصحيحة هن [[عدد مركب|أعداد مركبة]] {{تعبير رياضي|1=''α'' = ''u'' + ''vi''}} حيث u و v [[عدد صحيح|أعداد صحيحة]]، و{{mvar|i}} هو [[وحدة تخيلية|الجذر التربيعي لناقص واحد]]. بتعريف خوارزمية مماثلة لخوارزمية أقليدس، يتبين أن الأعداد الغاوسية تقبل هي الأخرى تفكيكا وحيدا لجداء أعداد غاوسية أخرى، وذلك باستعمال الحجة نفسها التي استعمل [[خوارزمية أقليدس#تطبيقات رياضياتية#متطابقة بيزو|أعلاه]]. هذا التفكيك الوحيد يساعد في العديد من المجالات، منها على سبيل المثال، ايجاد جميع [[ثلاثية فيثاغورس|ثلاثيات فيثاغورس]]، ومنها أيضا البرهان على [[مبرهنة فيرما حول مجموع مربعين]]. مساهمة خوارزمية أقليدس في هذه التطبيقات غير أساسية حيث يمكن أن يُبرهن عليها بطرق أخرى.

=== المجالات الإقليدية ===
=== الحلقات غير التبادلية ===

== تعميمات إلى بُنى رياضياتية أخرى ==
[[ملف:TorusKnot3D.png|thumb|alt="A cord wound seven times around a torus and reconnected to its beginning، forming a closed loop. In the process، the cord completes three circuits of the torus، forming a (3، 7) torus knot."|يمكن أن تطبق الخوارزمية الإقليدية في [[نظرية العقد (رياضيات)|نظرية العقد]].<ref>{{استشهاد بأرخايف | author = Yamada Y | year = 2007 | title = Generalized rational blow-down، torus knots، and Euclidean algorithm | publisher = | eprint=0708.2316 | class = math.GT}}</ref>]]

== المراجع ==
* من كتاب مقدمة في التشفير بالطرق الكلاسيكية
{{مراجع}}

== وصلات خارجية ==
{{شريط بوابات|خوارزميات|رياضيات|علم الحاسوب|نظرية الأعداد}}

{{تصنيف كومنز|Euclidean algorithm}}
{{خوارزميات نظرية الأعداد}}

{{ضبط استنادي}}

[[تصنيف:إقليدس]]
[[تصنيف:حسابيات]]
[[تصنيف:خوارزميات نظرية الأعداد]]
[[تصنيف:مقالات تحوي براهين]]