خوارزمية أقليدس مثال
مثال
القاسم المشترك الأكبر للعددين 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 alt Depiction of Euclid as a bearded man holding a pair of dividers to a tablet. من المحتمل أن تكون الخوارزمية الإقليدية قد اكتشفت قرونا قبل إقليدس . بين هنا حاملا ل Caliper Divider caliper dividers
خوارزمية أقليدس هي واحدة من أقدم الخوارزميات الجارية الاستعمال. ظهرت في كتاب أصول إقليدس الأصول لإقليدس (في حوالي عام 300 قبل الميلاد).
تطبيقات رياضياتية
متطابقة بوزو
تنص متطابقة بوزو على أن القاسم المشترك الأكبر g لعددين a و b يمكن أن يمثل مجموعا خطيا للعددين a و b؛ أي أنه يوجد عددان، s و t حيث يتوفر ما يلي
g sa + tb
الخوارزمية الإقليدية الممددة
مقال تفصيلي خوارزمية إقليدس الممددة
غŒمكن تمثغŒل القاسم المشترك الأكبر للعددغŒن عن طرغŒق دمج خطي مع عددغŒن آخرغŒن ،
كغŒف غŒمكن أغŒجاد قغŒمتي n و m وذلك عن طرغŒق خوارزمغŒة اقلغŒدس الممتدة وهناك ثلاثة طرق لمعرفة هذه القغŒم (الطرق هي مشابه لبعض، لكن غŒمكن القول أنها مختصره من الأخرغŒات).
الطريقة الأولى وهي يمكن ان نطلق عليها التراجع وفي هذه الطريقة نقوم بالحل عن طريق خوارزمية اقليدس وبعدها تقول بالتراجع الخلفي لايجاد قيمتي m،n كما في المثال التالي
مثال قم بتمثيل العددين 26 و 21 بطريقة اقليدس الممتدة
فنبدأ بالحل كما هو الحال في طريقة اقليدس
26 1* 21 + 5 و 21 4 * 5 + 1 و 5 5 * 1 + 0
وتتوقف عند الصفر. الآن المعادلة التي قبل المعادلة التي باقيها صفر أي المعادلة الثانية نقوم بكتابتها بالشكل التالي
- 1 21-4*5
أغŒضا المعادلة الأولى بنفس الشكل
- 5 26-1*21
في المعادلتين السابقتين
- 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.
طريقة المصفوفات
المعادلات الديوفانتية الخطية
يمكن لخوارزمية أقليدس أيضا أن تستعمل من أجل حلحلة العديد من معادلة ديوفانتية المعادلات الديوفانتية الخطية. تظهر واحدة من هده المعادلات في مبرهنة الباقي الصيني .
egin
x_1 & equiv x mod m_1 \
x_2 & equiv x mod m_2 \
& vdots \
x_N & equiv x mod m_N,.
end
مبرهنة الباقي الصيني
مبرهنة الباقي الصيني
شجرة ستيرن-بروكوت
SternBrocotTree.svg 300 شجرة ستيرن-بروكوت، و متتاليات ستيرن-بروكوت من الرتبة < >i حيث < >i 1، 2، 3، 4.
انظر شجرة ستيرن-بروكوت .
الكسور المستمرة
الفعالية الخوارزمية
Euclidean algorithm running time X Y.png alt A set of colored lines radiating outwards from the origin of an < >x-< >y coordinate syst . Each line corresponds to a set of number pairs requiring the same number of steps in the Euclidean algorithm. عدد الخطوات المطلوبة في الخوارزمية الإقليدية لحساب القاسم المشترك الأكبر(< >x،< >y). النقط الحمراء تدل على عدد صغير نسبيا من الخطوات (سريع)، بينما النقط الصفراء والخضراء والزرقاء تدل على عدد أكبر على التوالي من النقط (بطيء). The largest blue area follows المستقيم < >y خ¦< >x، حيث خ¦ يمثل نسبة ذهبية النسبة الذهبية .
في النظم العددية الأخرى
الأعداد الجذرية والأعداد الحقيقية
متعددات الحدود
مقال تفصيلي القاسم المشترك الأكبر لمتعددات الحدود
الأعداد الطبيعية الغاوسية
Gaussian primes.png 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 of the circle the vertical and horizontal axes، and the two diagonal lines at ±45 degrees. توزيع الأعداد الطبيعية الغاوسية < >u + < >vi في المستوى العقدي، من معايير < >u2 + < >v2 أصغر من 500
المجالات الإقليدية
الحلقات غير التبادلية
تعميمات إلى بُنى رياضياتية أخرى
TorusKnot3D.png 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. يمكن أن تطبق الخوارزمية الإقليدية في نظرية العقد . cite arxiv author Yamada Y year Generalized rational blow-down، torus knots، and Euclidean algorithm publisher eprint 0708.2316 math.GT
أنظر أيضاً
- الخوارزمية الثنائية لحساب القاسم المشترك الأكبر ،
- القاسم المشترك الأكبر لمتعددات الحدود ،
- خوارزمية العلاقة بين الأعداد الطبيعية ،
- خوارزمية ليهمر لحساب القاسم المشترك الأكبر .
Euclid's algorithm Book VII Proposition 2 3.png 300 طريقة أقليدس لإيجاد القاسم المشترك الأكبر لعددين ابتُدأ بهما ممثلين بالقطعتين AB و CD، عُرفا كل منهما على أنهما مضاعفين لوحدة طول مشتركة. بما أن طول CD أقصر من AB، ، استعمل لقياس AB، ولكنه قاسه مرة واحدة لأن الباقي EA أصغر قطعا من CD. الآن، EA تقيس (مرتين) الطول الأقصر DC، حيث الباقي FC أقصر من EA. إذن،FC تقيس (ثلاث مرات) الطولEA. لأنه لم يبق أي باق، تتوقف العملية مع كون FC القاسم المشترك الأكبر. في اليمين، مثال نيكوماكوس مع الأعداد 49 و 21 معطيا قاسمهما المشترك الأكبر مساويا لسبعة. (أُخذ من Heath 1908 300).
في نظرية الأعداد ،
خوارزمية إقليدس هي خوارزمية لحساب قاسم مشترك أكبر القاسم المشترك الأكبر عدد طبيعي لعددين طبيعيين ، تظهر أهميتها الأساسية في عدم الحاجة لتحليل العددين للتمكن من حساب قاسم مشترك أكبر قاسمهما المشترك الأكبر . تتميز بكونها إحدى أقدم الخوارزميات حيث ترجع إلى سنة 300 ق.م .
التعليقات
لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا