المعادلات الديفونتية الخطية

Linear Diophantine Equations

 

المعادلات الديفونتية الخطية

أبسط انواع المعادلات الديفونتية الخطية ax+by=c حيث a, b, c أعداد صحيحة وتسمى معادلة خطية ذات مجهولين. المعادلة ax+by+cz=d تسمى معادلة ديفونتية خطية ذات ثلاثة مجاهيل, حيث a,b,c,d أعداد صحيحة.سيكون تركيزنا على المعادلة ذات المجهولين

 

حقيقة 1: يوجد للمعادلة الديفونتية ax+by=c حلول صحيحة إذا وفقط إذا كان(a,b) يقسم c.

الإثبات: لنفرض أن (a,b)=d إذا d|a, d|b. فإذا كان (x,y) حلا للمعادلة فإن d يقسم العدد الصحيح ax+by وعليه d يقسم c. لإثبات الشق الآخر افرض أن d يقسم c إذا c=qd حيث q عدد صحيح. بما أن (a,b)=d فهناك صحيحين r,s بحيث

 

ar+bs=d

بضرب طرفي المساواة في q نحصل على

a(rq)+b(sq)=dq=c

إذا (rq,sq) حلا للمعادلة ax+by=c وتثبت النظرية.

 

إذا وجدنا لمعادلة ديفونتية ax+by=c حلا واحد معين(x_0 ,y_0 ) فإن لها عدد لا نهائي من الحول جميعها توجد باستخدام العلاقة التالية

 

x_k = x_0 + \frac{b}{{(a,b)}}k,\quad \quad y_k = y_0 - \frac{a}{{(a,b)}}k

حيث k عدد صحيح.

 

للإثبات افرض أن m = \frac{a}{d},\;n = \frac{b}{d} حيث d القاسم المشترك الأكبر للعددين a,b. إذا m,n أوليان نسبيا. الآن ليكن (u,v) عبارة عن حل آخر للمعادلة ax+by=c. بالتعويض بالحلين في المعادلة نحصل على العلاقتين

 

\begin{gathered} ax_0 + by_0 = c \hfill \\ au + bv = c \hfill \\ \end{gathered}

 

وبالطرح والقسمة على d ينتج

 

m(x_0 - u) + n(y_0 - v) = 0 \Rightarrow m(x_0 - u) = - n(y_0 - v)

 

بالقسمة على m نستنتج أن m يقسم (y_0 - v) لأن m,n أوليان نسبيا. إذا يوجد عدد صحيح k بحيث

 

y_0 - v = mk \Rightarrow v = y_0 - mk

 

بالتعويض عن v المعادلة السابقة ينتج مباشرة أن

 

u = x_0 + nk

 

بقيى أن نثبت أن كل زوج على الصورة (x_0 + nk,y_0 - mk) هو حل للمعادلة الديفونتية. بالتعويض المباشر في المعادلة الديفونتية

 

a(x_0 + nk) + b(y_0 - mk) = ax_0 + by_0 + (an - bm)k = c

 

إذا الزوج المرتب أعلاه حل للمعادلة, حيث معامل k هنا an-bm=0 وبهذا ينتهي الإثبات.

 

من الناحية العملية حل معادلة ديفونتية ax+by=c يتم أولا بإيجاد حل (s,t) للمعادلة

 

ax+by=(a,b)

 

وذلك باستخدام طريقة خوارزمية اقليدس أو الطريقة الإقليدية الموسعة. بعد ذلك نوجد الحل (x_0 ,y_0 ) للمعادلة الأصل ax+by=c من العلاقة

 

x_0 = \frac{c}{{(a,b)}}s,\quad \quad y_0 = \frac{c}{{(a,b)}}t