عمروعروق: معادلة Diophantine الخطية (في متغيرين)

الجمعة، 16 نوفمبر 2018

معادلة Diophantine الخطية (في متغيرين)

هي معادلة الشكل العام

(1)

حيث يتم إيجاد حلول لها

الأعداد الصحيحة . يمكن حل هذه المعادلات بشكل كامل ، وتم إنشاء أول حل معروف بواسطة Brahmagupta. النظر في المعادلة

(2)

الآن استخدام الاختلاف من الخوارزمية الإقليدية ، مما يتيح

			(3)
			(4)
			(5)
			(6)

ابتداء من القاع يعطي

			(7)
			(8)

وبالتالي

			(9)
			(10)

مواصلة هذا الإجراء على طول الطريق إلى القمة.

خذ على سبيل المثال المعادلة

(11)

وتطبيق الخوارزمية أعلاه للحصول عليها

1027 = 712 · 1+ 315؛ 712 = 315 · 2+ 82؛ 315 = 82 · 3+ 69؛ 82 = 69 · 1+ 13؛ 69 = 13 · 5+ 4؛ 13 = 4 · 3+ 1؛ |؛ |؛ |؛ |؛ |؛ الخامس؛ 1 = -165 · 1027+ 238 · 712؛ 1 = 73 · 712- 165 · 315 ؛ 1 = -19 · 315+ 73 · 82؛ 1 = 16 · 82- 19 · 69؛ 1 = -3 · 69+ 16 · 13؛ 1 = 1 · 13- 3 · 4؛ 1 = 0 · 4+ 1 · 1 ^؛ |؛ |؛ |؛ |؛ |؛ |

(12)

الحل هو

، لذلك

يمكن تبسيط الإجراء أعلاه من خلال ملاحظة أن الأعمدة في أقصى اليسار يقابلها إدخال واحد وإشارات بديلة ، كما يجب

			(13)
			(14)
			(15)

لذلك معاملات من

هي نفسها و

(16)

تكرار المثال أعلاه باستخدام هذه المعلومات يعطي بالتالي

1027 = 712 · 1+ 315؛ 712 = 315 · 2+ 82؛ 315 = 82 · 3+ 69؛ 82 = 69 · 1+ 13؛ 69 = 13 · 5+ 4؛ 13 = 4 · 3+ 1؛ |؛ |؛ |؛ |؛ |؛ الخامس؛ (-) 165 · 1+ 73 = 238؛ (+) 73 · 2+ 19 = 165؛ (-) 19 · 3+ 16 = 73؛ (+) 16 · 1+ 3 = 19؛ (-) 3 · 5+ 1 = 16؛ (+) 1 · 3+ 0 = 3؛ (-) 0 · 1+ 1 = 1 ^؛ |؛ |؛ |؛ |؛ |؛ |

(17)

ونستعيد الحل أعلاه.

استدعاء الحلول ل

(18)

. إذا كانت العلامات أمام

أو

هي سلبية ، ثم حل المعادلة المذكورة أعلاه واتخاذ علامات الحلول من الجدول التالي:

معادلة

في الواقع ، حل المعادلة

(19)

ما يعادل العثور على جزء المستمر ل

، مع

رئيس نسبيا (أولدز 1963). إذا كانت هناك

عبارات في الكسر ، فخذ

التقارب

. لكن

(20)

ذلك هو حل واحد

مع حل عام

			(21)
			(22)

مع عدد صحيح

عشوائي . يتم إعطاء الحل من حيث أصغر عدد صحيح موجب عن طريق اختيار المناسب .

الآن فكر في المعادلة العامة الأولى من النموذج

(23)

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

يمكن تقسيمها من خلال العائد

(24)

حيث

. إذا

، إذاً

ليس عددًا صحيحًا ولا يمكن أن تحتوي المعادلة على حل في الأعداد الصحيحة . ولذلك فإن الشرط الضروري والكافي لمعادلة الدرجة الأولى العامة لإيجاد حلول في الأعداد الصحيحة هو ذلك