الرياضيات بالعربية

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

لتكن $a,b,c$ أعدادا من $\mathbb{Z}^{*}$ :


المعادلة $a x + by = c$ ذات المجهولين $x$ و $y$ في $\mathbb{Z}$ تسمى المعادلة الديوفنتية الخطية

نسمي المعادلة $a x + by = c$ بـــ$(E)$


1) بين أن للمعادلة $(E)$ حل في $\mathbb{Z}^2$ $\iff$ $a \wedge b$ يقسم $c$.

2) بين أنه إذا كان الزوج $(x_0,y_0)$ حلا للمعادلة $(E)$ فإن مجموعة حلول المعادلة $(E)$ تكتب على الشكل :

$S = \left\{\left(x_0 + \frac{kb}{a \wedge b}, y_0 - \frac{ka}{a \wedge b}\right) \, \middle| \, k \in \mathbb{Z}\right\}$

3) باستعمال خوارزمية أقليدس, أحسب $54 \wedge 21$

4) حل في $\mathbb{Z}^2$ المعادلة : $(E) \quad 54x+21y=906$.

راجع درس الحسابيات في Z
نفترض ان $a \wedge b$ تقسم $c$.

نضع $d = a \wedge b$

إذن يوجد $k$ من $\mathbb{Z}$ بحيث $c = kd$

ولدينا حسب متساوية Bézout : $\exists (u, v) \in \mathbb{Z}^2 \, : \, d = au + bv$.

وبالتالي $c = kd = a (ku) + b (k v)$.

نضع $(x_0, y_0) = (ku, kv)$.

وبالتالي لدينا المعادلة $a x + b y = c$ تقبل حلول.

--------------------------------------------------

نفترض الآن أن المعادلة $ax + by = c$ تقبل حلا في $\mathbb{Z}^2$ وليكن $(x_0, y_0)$ أحدها.

لدينا $a x_0 + b y_0 = c$.

بما أن $a \wedge b | a$ و $a \wedge b | b$ فإن :

$a \wedge b | a x_0 + b y_0 = c$

إذن $a \wedge b | c$


لتكن $S$ مجموعة حلول المعادلة $(E) \quad a x + by = c$.

وليكن $(x_0, y_0)$ حلا خاصا للمعادلة $(E)$.

لنبين أن $S = \{(x_0 + \frac{kb}{a \wedge b}, y_0 - \frac{ka}{a \wedge b}) \, | \, k \in \mathbb{Z}\}$.

من أجل $(x, y) = (x_0 + \frac{kb}{a \wedge b}, y_0 - \frac{ka}{a \wedge b})$ بحيث $k \in \mathbb{Z}$. لدينا :

$\begin{array}{rcl}a x + b y & = & a x_0 + \dfrac{abk}{a \wedge b} + b y_0 - \dfrac{abk}{a \wedge b} \\ & = & a x_0 + b y_0 \\ & = & c\end{array}$

ومنه فإن الزوج $(x_0 + \frac{kb}{a \wedge b}, y_0 - \frac{ka}{a \wedge b})$ بحيث $k \in \mathbb{Z}$ حلول للمعادلة $(E)$.

--------------------------------------------------

الآن لنبين أن الحلول تكتب على شكل

$(x_0 + \frac{kb}{a \wedge b}, y_0 - \frac{ka}{a \wedge b})$ بحيث $k \in \mathbb{Z}$

لدينا :

$(x, y) \in S \Leftrightarrow a x + by = c = ax_0 + b y_0$

إذن : $a (x - x_0) = - b (y - y_0) \quad (\star) $

ولدينا :

$d = a \wedge b \iff \left\{\begin{matrix}\exists (\alpha, \beta) \in \mathbb{Z}^2 \, : \, a = \alpha d \quad b = \beta d\\ \alpha \wedge \beta = 1\end{matrix}\right.$

نعوض في $\star$

$\alpha d (x - x_0) = - \beta d (y - y_0)$

وبالتالي $\alpha (x - x_0) = - \beta (y - y_0)$

لدينا $\beta \, | \, \alpha (x - x_0)$ و $\alpha \wedge \beta = 1$ إذن حسب مبرهنة Gauss:

$\exists k \in \mathbb{Z} \quad k \beta = x - x_0$

$\alpha k \beta = \alpha (x - x_0) = - \beta (y - y_0)$

$\alpha k = y_0 - y$

وبالتالي :

$(x, y) \in S \implies \exists k \in \mathbb{Z} \, \left\{\begin{matrix}x = x_0 + k \beta \\ y = y_0 - k \alpha\end{matrix}\right.$

إذن :
$(x, y) \in S \implies \exists k \in \mathbb{Z} \, \left\{\begin{matrix}x = x_0 + k \dfrac{b}{a \wedge b} \\ \\y = y_0 - k \dfrac{a}{a \wedge b}\end{matrix}\right.$

خلاصة :

$S = \left\{\left(x_0 + \frac{kb}{a \wedge b}, y_0 - \frac{ka}{a \wedge b}\right) \, | \, k \in \mathbb{Z}\right\}$


لنحدد $54 \wedge 21$ باستعمال خوارزمية أقليدس :

$\begin{array}{rcl}54 & = & 21 \times 2 + 12 \\21 & = & 12 \times 1 + 9\\12 & = & 9 \times 1 + 3 \\9 & = & 3 \times 3 + 0\end{array}$

وبالتالي $54 \wedge 21 = 3$


نعتبر المعادلة $(E_1) \quad 54x+21y=906$

لدينا $54 \wedge 21 = 3$ ولدينا $3$ تقسم $906$.

إذن المعادلة $(E_1)$ تقبل حلولا في $\mathbb{Z}^2$.

نضع $b = 54$ و $a = 21$

من خلال السؤال السابق لدينا :
$\begin{array}{rcl}\rightarrow 12 & = & b - 2a \\\rightarrow 9 & = & a - 12\\& = & a - (b-2a) \\& = & 3a - b \\\rightarrow 3 & = & 12 - 9 \\& = & (b - 2a) - (3a - b) \\& = & 2b - 5a \\\end{array}$

إذن $2 b - 5a = 3$

نقوم بالضرب في $302$ لدينا :

$b \times 604 + a \times (-1510) = 906$

أي أن

$54 \times 604 + 21 \times (-1510) = 906$

إذن الزوج $(x_0, y_0) = (604, -1510)$ حل خاص للمعادلة $(E_1)$.

ومجموعة الحلول للمعادلة $(E_1)$ هي :

$S = \{(604 + 7k, -1510-18k) \, | \, k \in \mathbb{Z} \}$