معادلة ديوفانتاين ax + by = c
المعادلة Ax + By = C: معادلةٌ معاملاتها: a، و b، و c أعداد صحيحة نسبية ( a و b ليسا معدومين كلاهما)، ومهما كان المجهولان x و y عددين نسبيين صحيحين، فهي واحدة من أيسر المعادلات الديفونتية. يستند حلها إلى خوارزمية إقليدس، ومتطابقة بوزو (التي تلائم هذه الحال، وتسمى أيضًا نظرية بيزو، حيث c يساوي القاسم المشترك الأكبر لـ a و b ) ولنظرية جاوس أيضًا.
وأشباه هذه المعادلة، في مجموعة الأعداد الصحيحة النسبية، إما لا حل لها، وإما أن لها ما لا ينتهي من الحلول. وإذا كانت المعاملات والمجهولان أرقامًا طبيعية، فإن للمعادلة عددًا محدودًا من الحلول. تعطي نظرية باولي الرقم الأقرب إلى 1.
البحث عن الحلول في مجموعة الأعداد الصحيحة النسبية
المعادلة ax + by = 1 حيث a و b عددان أوليان فيما بينهما
تؤكد نظرية متطابقة بوزو أن هذه المعادلة تقبل دائمًا حل واحد على الأقل.
تتمثل الخطوة الأولى للحل في إيجاد حل خاص، أي إثنان من الأعداد الصحيحة النسبية (x0, y0) تحقق : ax0 + by0 = 1.
- تسمح خوارزمية إقليدس الممددة بعرض واحد. (يمكننا أن نلاحظ أن هذه الخوارزمية يتم تفسيرها على أنها حساب تمثيل الكسر المستمر a / b ؛ قبل هذا الأخير لدينا h n–1/kn–1 حلاً للمسألة، [1] لأن kn–1a– hn–1b=(–1)n+1.
- يمكننا الاشتغال على المعامل b، من خلال البحث أولاً عن عدد صحيح x0 حيث ax0 ≡ 1 (mod b). ثم حساب عدد صحيح y 0 على أنه يساوي (1 – ax0)/b.
- للعثور على x0 مقلوب a بالترديد b، ويمكن استخدامها في نظرية فيرما المعممة من قبل أويلر، التي تنص على φ(b) توافق 1 بالترديد b، حيث φ هو مؤشر أويلر : العدد الصحيح x 0 = a φ(b)–1 مناسب.[2] وبالمثل، فإن العدد الصحيح x 0 = a λ(b)–1 مناسب، حيث λ هي دالة كارميشل.
- ولكن يمكننا أيضًا، إذا لم يكن b كبيرًا للغاية، البحث عن حل بطريقة بسيطة، بالبحث عن عدد صحيح x 0 محصور بين 1 وb| - 1| يحقق التطابق الخطي ax0 ≡ 1 (mod b).
مراجع
- ↑ Eugène Cahen (1900). Éléments de la théorie des nombres. Gauthier-Villars. ص. 60-61. مؤرشف من الأصل في 2022-04-13..
- ↑ Cahen 1900.