معادلة ديوفانتاين ax + by = c

المعادلة ax + by = c ، هي معادلة تكون فيها المعاملات a و b و c ثلاثة أعداد صحيحة نسبية ( a و b ليسا منعدمين على حد سواء) ومهما كان المجهولان x و y عددين نسبيين صحيحين، فهي واحدة من أبسط معادلات ديوفانتاين. يستند حلها إلى الخوارزمية الإقليدية، ومتطابقة بوزو (التي تتوافق مع هذه الحالة، وتسمى أيضًا نظرية Bézout، حيث c يساوي القاسم المشترك الأكبر لـ a و b ) ولنظرية Gauss أيضا.

في مجموعة الأعداد الصحيحة النسبية، مثل هذه المعادلة إما ليس لها حل أو لها ما لانهاية من الحلول. عندما تكون المعاملات والمجهولان أرقامًا طبيعية، فإن المعادلة بها عدد محدود من الحلول. تعطي نظرية باولي الرقم الأقرب إلى 1.

البحث عن الحلول في مجموعة الأعداد الصحيحة النسبية

المعادلة ax + by = 1 حيث a و b عددان أوليان فيما بينهما

تؤكد نظرية متطابقة بوزو أن هذه المعادلة تقبل دائمًا حل واحد على الأقل.

تتمثل الخطوة الأولى للحل في إيجاد حل خاص، أي إثنان من الأعداد الصحيحة النسبية (x₀, y₀) تحقق : ax₀ + by₀ = 1.

• تسمح خوارزمية إقليدس الممددة بعرض واحد. (يمكننا أن نلاحظ أن هذه الخوارزمية يتم تفسيرها على أنها حساب تمثيل الكسر المستمر a / b ؛ قبل هذا الأخير لدينا h _n–1/k_n–1 حلاً للمسألة، لأن k_n–1a– h_n–1b=(–1)ⁿ⁺¹.
• يمكننا الاشتغال على المعامل b، من خلال البحث أولاً عن عدد صحيح x₀ حيث ax₀ ≡ 1 (mod b). ثم حساب عدد صحيح y ₀ على أنه يساوي (1 – ax₀)/b.
  • للعثور على x₀ مقلوب a بالترديد b، ويمكن استخدامها في نظرية فيرما المعممة من قبل أويلر، التي تنص على ^φ(b) توافق 1 بالترديد b، حيث φ هو مؤشر أويلر : العدد الصحيح x ₀ = a ^φ(b)–1 مناسب. وبالمثل، فإن العدد الصحيح x ₀ = a ^λ(b)–1 مناسب، حيث λ هي دالة كارميشل.
  • ولكن يمكننا أيضًا، إذا لم يكن b كبيرًا للغاية، البحث عن حل بطريقة بسيطة، بالبحث عن عدد صحيح x ₀ محصور بين 1 وb| - 1| يحقق التطابق الخطي ax₀ ≡ 1 (mod b).