ماذا تحسب خوارزمية إقليدس الموسعة؟

تحسب gcd(a, b) تمامًا مثل خوارزمية إقليدس القياسية، لكنها تجد إضافيًا عددين صحيحين x وy (معاملات بيزو) يحققان a×x + b×y = gcd(a, b).

ما هي هوية بيزو؟

تنص هوية بيزو على أنه لأي عددين صحيحين a وb، يوجد عددان صحيحان x وy بحيث a×x + b×y = gcd(a, b) — خوارزمية إقليدس الموسعة هي الطريقة القياسية لإيجادهما.

هل معاملات بيزو فريدة؟

لا — إذا كانت (x, y) حلًا واحدًا، فإن (x + k×(b/gcd)، y − k×(a/gcd)) هو أيضًا حل لأي عدد صحيح k. تُرجع هذه الآلة الحاسبة الزوج المحدد الذي تنتجه الخوارزمية القياسية.

هل يمكن أن يكون a أو b سالبين؟

نعم، تتعامل الخوارزمية بشكل صحيح مع الأعداد الصحيحة السالبة؛ يُرجع المضاعف المشترك الأصغر المُبلغ عنه دائمًا كرقم غير سالب، مع تعديل x وy وفقًا لذلك.

ماذا لو كان a وb أوليين نسبيًا؟

إذا كان gcd(a, b) = 1، تصبح المعادلة a×x + b×y = 1، مما يعني أن x هو بالضبط المعكوس الضربي المعياري لـ a بترديد b (وy هو معكوس b بترديد a).

كيف يرتبط هذا بآلة حاسبة المعكوس الضربي المعياري؟

تُشغّل آلة حاسبة المعكوس الضربي المعياري هذه الخوارزمية بالضبط داخليًا وتستخرج x، مُختزلًا بترديد m، كإجابة — تعرض هذه الآلة الحاسبة المضاعف المشترك الأصغر الكامل وكلا المعاملين مباشرة.

ما مدى ضخامة a وb؟

تدعم هذه الآلة الحاسبة أعدادًا صحيحة حتى 100 رقم لكل منها، محسوبة بحساب BigInt دقيق حتى لا يكون هناك خطأ تقريب فاصلة عائمة حتى في المدخلات الضخمة.

أين تُستخدم خوارزمية إقليدس الموسعة في الحياة الواقعية؟

تُستخدم في توليد مفاتيح RSA، وحل معادلات ديوفانتين الخطية، وحساب المعكوسات المعيارية لبروتوكولات التشفير، وأي خوارزمية تحتاج شهادة صريحة لمضاعف مشترك أصغر محسوب.

آلة حاسبة خوارزمية إقليدس الموسعة — أوجد gcd(a,b) ومعاملات بيزو

تجد آلتنا الحاسبة لخوارزمية إقليدس الموسعة ليس فقط gcd(a, b)، بل أيضًا العددين الصحيحين x وy — معاملات بيزو — اللذين يحققان الهوية a×x + b×y = gcd(a, b)، محسوبة بدقة BigInt لمدخلات كبيرة تعسفيًا. إنها المحرك المباشر خلف آلة حاسبة المعكوس الضربي المعياري الخاصة بالموقع وعدد لا يُحصى من خوارزميات نظرية الأعداد الأخرى.

إجابة سريعة

تجد هذه الآلة الحاسبة gcd(a, b) بالإضافة إلى العددين الصحيحين x وy اللذين يحققان a×x + b×y = gcd(a, b)، باستخدام خوارزمية إقليدس الموسعة بدقة BigInt دقيقة.

أدخل a وb، ثم انقر على احسب.

كيفية استخدام آلة حاسبة خوارزمية إقليدس الموسعة — المضاعف المشترك الأصغر + معاملات بيزو

1
أدخل عددين صحيحين، a وb.
2
انقر على 'احسب' لإيجاد gcd(a, b) ومعاملات بيزو x وy.
3
تحقق من النتيجة: a × x + b × y يساوي دائمًا المضاعف المشترك الأصغر المحسوب.

لماذا تستخدم آلة حاسبة خوارزمية إقليدس الموسعة — المضاعف المشترك الأصغر + معاملات بيزو؟

تجد خوارزمية إقليدس العادية gcd(a, b) بالقسمة المتكررة، لكن النسخة الموسعة تتتبع سجلات إضافية في كل خطوة بحيث، عند الانتهاء، تكون قد عبّرت أيضًا عن ذلك المضاعف المشترك الأصغر كتركيبة خطية من a وb الأصليين — عددين صحيحين x وy مع a×x + b×y = gcd(a, b)، نتيجة مضمونة الوجود بهوية بيزو. هذا ليس مجرد فضول رياضي: هذان المعاملان بالضبط ما هو مطلوب لحساب المعكوسات الضربية المعيارية، وحل معادلات ديوفانتين الخطية، وتنفيذ توليد مفاتيح RSA.

الأسئلة الشائعة

أدوات ذات صلة

آلة حاسبة المعكوس الضربي المعياري — حل ax ≡ 1 (mod m)

أوجد المعكوس الضربي المعياري لـ a بترديد m باستخدام خوارزمية إقليدس الموسعة. آلة حاسبة مجانية بدقة BigInt وفحص وجود.

آلة حاسبة نظرية الباقي الصيني — حل الأنظمة المعيارية

حل نظامًا من التطابقات x ≡ aᵢ (mod mᵢ) لمعاملات أولية نسبيًا زوجيًا باستخدام نظرية الباقي الصيني. آلة حاسبة مجانية بدقة BigInt.

آلة حاسبة الأس المعياري — bᵉ mod m سريع عبر الإنترنت

احسب bᵉ mod m لأسس كبيرة تعسفيًا باستخدام الأس السريع بطريقة التربيع والضرب. آلة حاسبة مجانية بدقة BigInt، أساسية للتشفير.

آلة حاسبة الكسور المتصلة — وسّع وقيّم عبر الإنترنت

وسّع أي رقم عشري أو كسر إلى حدود الكسر المتصل [a₀; a₁, a₂, ...] وشاهد كل متقارب. آلة حاسبة مجانية بدقة BigInt الدقيقة.