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

1) الإتجاه $\displaystyle{\displaylines{\Longrightarrow)}}$

نفترض ان $\displaystyle{\displaylines{a \wedge b}}$ تقسم $\displaystyle{\displaylines{c}}$.

نضع $\displaystyle{\displaylines{d = a \wedge b}}$

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

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

وبالتالي $\displaystyle{\displaylines{c = kd = a (ku) + b (k v)}}$

نضع $\displaystyle{\displaylines{(x_0, y_0) = (ku, kv)}}$.

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

2) الإتجاه $\displaystyle{\displaylines{\Longleftarrow)}}$

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

لدينا $\displaystyle{\displaylines{a x_0 + b y_0 = c}}$.

نضع $\displaystyle{\displaylines{d = a \wedge b}}$

بما أن $\displaystyle{\displaylines{d | a}}$ و $\displaystyle{\displaylines{d | b}}$ فإن : $\displaystyle{\displaylines{d | a x_0 + b y_0 = c}}$

إذن $\displaystyle{\displaylines{d | c}}$

وبالتالي لدينا :

$\displaystyle{\displaylines{(E)}}$ تقبل حل في $\displaystyle{\displaylines{\mathbb{Z}^2}}$ $\displaystyle{\displaylines{\iff}}$ $\displaystyle{\displaylines{a \wedge b}}$ يقسم $\displaystyle{\displaylines{c}}$

---

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

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

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

1) لنبين أن $\displaystyle{\displaylines{\left\{\left(x_0 + \frac{kb}{a \wedge b}, y_0 - \frac{ka}{a \wedge b}\right) \ \middle| \ k \in \mathbb{Z}\right\} \subset S}}$

من أجل $\displaystyle{\displaylines{\left\{ \begin{array}{cl}x & = \ x_0 + \dfrac{kb}{a \wedge b} \\y & = \ y_0 - \dfrac{ka}{a \wedge b}\end{array} \right.}}$ بحيث $\displaystyle{\displaylines{k \in \mathbb{Z}}}$. لدينا :

$\displaystyle{\displaylines{\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}}}$

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

إذن :

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

2) لنبين أن $\displaystyle{\displaylines{S \subset \left\{\left(x_0 + \frac{kb}{a \wedge b}, y_0 - \frac{ka}{a \wedge b}\right) \ \middle| \ k \in \mathbb{Z}\right\}}}$

لدينا :

$\displaystyle{\displaylines{(x, y) \in S \iff a x + by = c = ax_0 + b y_0}}$

إذن : $\displaystyle{\displaylines{(\star) \qquad a (x - x_0) = - b (y - y_0) }}$

ولدينا :

$\displaystyle{\displaylines{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.}}$

نعوض في $\displaystyle{\displaylines{\star}}$

$\displaystyle{\displaylines{\alpha d (x - x_0) = - \beta d (y - y_0)}}$

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

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

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

$\displaystyle{\displaylines{\alpha k \beta = \alpha (x - x_0) = - \beta (y - y_0)}}$

إذن $\displaystyle{\displaylines{\alpha k = y_0 - y}}$ و $\displaystyle{\displaylines{\beta k = x-x_0}}$

وبالتالي :

$\displaystyle{\displaylines{(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.}}$

إذن :
$\displaystyle{\displaylines{(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.}}$

إذن :

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

خلاصة :

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

---

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


وبالتالي $\displaystyle{\displaylines{54 \wedge 21 = 3}}$

---

نضع $\displaystyle{\displaylines{b = 54}}$ و $\displaystyle{\displaylines{a = 21}}$

من خلال السؤال السابق لدينا :


إذن $\displaystyle{\displaylines{2 b - 5a = 3}}$

وبالتالي لدينا : $\displaystyle{\displaylines{54\times 2 + 21 \times (-5) = 3}}$

---

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

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

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

حسب السؤال السابق لدينا : $\displaystyle{\displaylines{54\times 2 + 21 \times (-5) = 3}}$

بما أن $\displaystyle{\displaylines{906=3\times 302}}$, نقوم بالضرب في $\displaystyle{\displaylines{302}}$ :

$\displaystyle{\displaylines{54 \times 604 + 21 \times (-1510) = 906}}$

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

ومجموعة الحلول للمعادلة $\displaystyle{\displaylines{(E_1)}}$ هي :

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