Number Theory: The Division Algorithm

اثبات مبرهنة (طريقة اثبات خوارزمية القسمة ببساطة)

خوارزمية القسمة

اذا كان $https://latex.codecogs.com/svg.image?a,b\in \mathbb{Z}, \ \ \ a> 0$ فهناك عددان وحيدان $https://latex.codecogs.com/svg.image?q,r\in \mathbb{Z}$ بحيث

$https://latex.codecogs.com/svg.image?b=qa+r, \ \ \ \ \ 0\leqslant r< a$

تمهيد للبرهان لاحظ ما يلي
العدد 13 يمكن كتابته بعدة طرق كحاصل ضرب عدديين مضافا له الباقي كما يلي
$https://latex.codecogs.com/svg.image?\\ 13=2(6)+{\color{Red} 1} \ \ \Rightarrow {\color{Red} 1}=13-2(6)\\ 13=2(5)+{\color{Red} 3} \ \ \Rightarrow {\color{Red} 3}=13-2(5)\\13=2(4)+{\color{Red} 5} \ \ \Rightarrow {\color{Red} 5}=13-2(4)\\ 13=2(3)+{\color{Red} 7} \ \ \Rightarrow {\color{Red} 7}=13-2(3)\\ 13=2(2)+{\color{Red} 9} \ \ \Rightarrow {\color{Red} 9}=13-2(2)\\...............................................\\...............................................\\$
لتكن المجموعة S هي مجموعة البواقي الموجبة ، اذا
$https://latex.codecogs.com/svg.image?\\S=\left\{1,3,5,7,9,.. \right\}\\or\\S= \left\{ 13-2(6),13-2(5),13-2(4),13-2(3),13-2(2),..\right\}$
سنقوم بتعميم المجموعة S على جميع الاعداد الصحيحة وليس فقط العدد 13 اذا سنفرض ان S على الصورة التالية

$https://latex.codecogs.com/svg.image?\\ let \ \ S=\left\{x\geqslant 0 \ | \ x=b-ta \ , \ t\in \mathbb{Z} \right\}$

اي ان عناصر S هي كل عدد x يحقق b-ta حيث t عدد صحيح (b : المقسوم ، a : المقسوم عليه اذن x هي باقي القسمة )
نفرض عنصر r ينتمي للمجموعة S بحيث ان r هو اصغر عنصر في المجموعة كما يلي
$https://latex.codecogs.com/svg.image?\\ let \ \ r\in S\\\Rightarrow \ \ r=b-ta, \ \ r\geqslant 0, \ t\in \mathbb{Z}$
نستبدل t بالرمز q حيث ان q عدد صحيح
$https://latex.codecogs.com/svg.image? \\ \ \ r=b-qa, \ \ r\geqslant 0, \\\Rightarrow {\color{Red} b= qa+r, \ \ r\geqslant 0}, .......(1)$
لنفترض ان العنصر r والمعرف كعنصر اصغر في المجموعة S اكبر من المقسوم عليه a
$https://latex.codecogs.com/svg.image?\\ \ \ {\color{Red} r}=b-qa \\let \ \ \ r\geq a \ \ \Rightarrow \ \ {\color{Red} r}-a\geqslant 0\\$
بالتعويض عن قيمة r كما هي معرفة من المجموعة S
$https://latex.codecogs.com/svg.image?\\ \Rightarrow \ \ {b-qa-a\geqslant 0} \\ \Rightarrow \ b-a(q+1)\geqslant 0$
لاحظ ان q عدد صحيح وبالتالي q+1 أيضا عدد صحيح وبذلك فان
$https://latex.codecogs.com/svg.image?\\ \Rightarrow \ b-a(q+1) \in S$
العدد السابق ينتمي للمجموعة S ، هذا الاستنتاج يقود الى ان هذا العدد اقل من العدد r وذلك لان هذا العدد يمثل r-a من الفرض بان r اكبر من المقسوم عليه a
$https://latex.codecogs.com/svg.image?\\ \Rightarrow \ r-a< r$
اذن يوجد عنصر في المجموعة S وهذا يناقض الفرض بان r هو اصغر عنصر في المجموعة وبالتالي يكون الفرض بان r اكبر من a غير صحيح ، اي يجب ان يكون
$https://latex.codecogs.com/svg.image?r< a \ ............(2)$
من (1) & (2) نستنتج ان r اكبر من وتساوي 0 واقل من a
$https://latex.codecogs.com/svg.image?b=aq+r, \ \ \ \ \ 0\leqslant r< a$
قمنا بإثبات الجزء الأول من المبرهنة ، والان نريد اثبات بان q, r وحيدان
نفرض وجود عددين r',r وعددين q',q يحققان خوارزمية القسمة
اذن b تكتب بطريقتين
$https://latex.codecogs.com/svg.image?\\b=aq+r, \ \ \ \ \ 0\leqslant r< a\\ and\\ b=aq' +r'\ \ \ \ \ 0\leqslant r'< a$
ومن التساوي بين طرفي المعادلتين
$https://latex.codecogs.com/svg.image?\\qa+r =q'a +r' \\qa-aq' =r' -r\\a(q-q')=r' -r\\a(q'-q)=r -r'\geqslant 0\\ \Rightarrow \ \ a(q'-q) \geqslant 0\\$
ومنها
$https://latex.codecogs.com/svg.image?\\0\leq {\color{Red} a}(q'-q)< {\color{Red} a} \\0\leq (q'-q)< 1 \\\Rightarrow \ \ q'=q$
ومن تعريف r والمساواه بين q و 'q نجد ان
$https://latex.codecogs.com/svg.image?\\r=b-{\color{Red} q}a=b-{\color{Red} q'}a=r'\\\Rightarrow \ \ r=r'$
اذن r و q وحيدان