تمرين إثبات القسمة الأقليدية

لدينا : $\displaystyle{\displaylines{A = \{ n \in \mathbb{Z} \, | \, nb > a \}}}$

نضع : $\displaystyle{\displaylines{k = (1+|a|)}}$ لدينا $\displaystyle{\displaylines{k \in A}}$ وبالتالي المجموعة $\displaystyle{\displaylines{A}}$ غير فارغة

إذا أخذنا $\displaystyle{\displaylines{m}}$ بحيث $\displaystyle{\displaylines{m < -|a|}}$ وحيث أن $\displaystyle{\displaylines{1 \leq b}}$ لدينا :

$\displaystyle{\displaylines{mb < -|a|b \leq -|a| \leq a}}$

إذن لدينا $\displaystyle{\displaylines{m \notin A}}$ وبالتالي المجموعة $\displaystyle{\displaylines{A}}$ مصغورة بـ$\displaystyle{\displaylines{-|a|}}$

---

بما أن $\displaystyle{\displaylines{A \subset \mathbb{Z}}}$ و $\displaystyle{\displaylines{A}}$ مصغورة إذن يوجد $\displaystyle{\displaylines{n \in A}}$ بحيث : $\displaystyle{\displaylines{ n = \min A}}$.

لدينا : $\displaystyle{\displaylines{a < nb}}$

ولدينا $\displaystyle{\displaylines{(n-1)b \leq a}}$ لأن $\displaystyle{\displaylines{n = \min A}}$ إذن $\displaystyle{\displaylines{(n-1) \notin A}}$

وبالتالي : $\displaystyle{\displaylines{(n-1)b \leq a < nb}}$

نضع $\displaystyle{\displaylines{q = n-1}}$. لدينا : $\displaystyle{\displaylines{qb \leq a < qb+b}}$

وبالتالي : $\displaystyle{\displaylines{0 \leq a - qb < b}}$

نضع $\displaystyle{\displaylines{r = a - qb}}$. لدينا :

$\displaystyle{\displaylines{a = bq + r }}$ بحيث $\displaystyle{\displaylines{0 \leq r < b}}$

---

من أجل $\displaystyle{\displaylines{b<0}}$ نضع $\displaystyle{\displaylines{c = -b}}$

لدينا $\displaystyle{\displaylines{c > 0}}$ إذن يوجد $\displaystyle{\displaylines{(q,r) \in \mathbb{Z} \times \mathbb{N}}}$ بحيث : $\displaystyle{\displaylines{a = c q + r}}$ مع $\displaystyle{\displaylines{0 \leq r < c}}$.

$\displaystyle{\displaylines{a = (-b) q + r}}$ مع $\displaystyle{\displaylines{0 \leq r < |-b|}}$.

أي أن $\displaystyle{\displaylines{a = b (-q) + r}}$ مع $\displaystyle{\displaylines{0 \leq r < |b|}}$.

---

نفرض أنه توجد ثنائيتين $\displaystyle{\displaylines{(q_1,r_1),(q_2,r_2)\in\mathbb{Z}\times\mathbb{N}}}$ بحيث $\displaystyle{\displaylines{0\leqslant r_1,r_2<|b|}}$ تحققان:

$\displaystyle{\displaylines{a=bq_1+r_1=bq_2+r_2}}$

$\displaystyle{\displaylines{\implies b(q_1-q_2)=r_2-r_1 \quad \cdots(1)}}$

وبما أن $\displaystyle{\displaylines{0\leqslant r_1,r_2<|b|}}$ فإن:

$\displaystyle{\displaylines{\begin{align*}-|b|<r_2-r_1<|b| & \implies -|b|<b(q_1-q_2)<|b| \\ & \implies -1<q_1-q_2<1 \\ & \implies q_1-q_2=0 \\ & \implies q_1=q_2\end{align*}}}$

وبالعودة إلى المعادلة $\displaystyle{\displaylines{(1)}}$ نجد:

$\displaystyle{\displaylines{r_2-r_1=0\implies r_2=r_1}}$
ومنه وحدانية الثنائية $\displaystyle{\displaylines{(q,r)}}$ .

---

البرهان الذي قمنا به من أجل $\displaystyle{\displaylines{(a,b) \in \mathbb{Z} \times \mathbb{Z}^{*}}}$.

إذا كان $\displaystyle{\displaylines{(a,b) \in \mathbb{N} \times \mathbb{N}^{*}}}$. يمكننا استخدام نفس البرهان بأخذ : $\displaystyle{\displaylines{A = \{n \in \mathbb{N} \, | \, nb > a\}}}$ و استخدام نفس الخطوات من أجل $\displaystyle{\displaylines{b > 0}}$.

لاحظ أنه بوضع : $\displaystyle{\displaylines{n = \min A > 0}}$ لدينا : $\displaystyle{\displaylines{q = n-1 \geq 0}}$ إذن $\displaystyle{\displaylines{q \in \mathbb{N}}}$.

و $\displaystyle{\displaylines{0 \leq r = a - bq < b}}$