ليكن $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ عددين صحيحين طبيعيين غير منعدمين بحيث $\displaystyle{\displaylines{b}}$ لا يقسم $\displaystyle{\displaylines{a}}$.
تنص خوارزمية أقليدس (Algorithme d'Euclide) لتحديد القاسم المشترك الأكبر على :
$\displaystyle{\displaylines{\begin{array}{rcl}a=bq_0+r_0 & & 0 \leq r_0 < b \\b=r_0q_1+r_1 & & 0 \leq r_1 < r_0 \\r_0=r_1q_2+r_2 & & 0 \leq r_2 < r_1 \\.. & & \\.. & & \\r_{n-2}=r_{n-1}q_{n}+r_{n} & & 0 \leq r_{n} < r_{n-1} \\r_{n-1}=r_{n}q_{n+1}+0 & & \end{array}}}$
القاسم المشترك الأكبر للعددين $\displaystyle{\displaylines{a}}$ و $\displaystyle{\displaylines{b}}$ هو آخر باقي غير منعدم. لدينا $\displaystyle{\displaylines{a \wedge b = r_n}}$.
1) بين أن $\displaystyle{\displaylines{a \wedge b = b \wedge r_0}}$
2) بين أنه يوجد $\displaystyle{\displaylines{n}}$ من $\displaystyle{\displaylines{\mathbb{N}}}$ بحيث $\displaystyle{\displaylines{r_{n+1} = 0}}$
3) استنتج أن $\displaystyle{\displaylines{a \wedge b = r_n}}$لدينا : $\displaystyle{\displaylines{a = b q_0 + r_0}}$
نضع $\displaystyle{\displaylines{d_1 = a \wedge b}}$ و $\displaystyle{\displaylines{d_2 = b \wedge r_0}}$
لدينا :
$\displaystyle{\displaylines{\left\{\begin{matrix}d_1 | a\\ d_1 | b\end{matrix}\right.\implies d_1 | a - bq_0=r_0}}$
لدينا اذن الآتي :
$\displaystyle{\displaylines{\left\{\begin{matrix}d_1 | b\\ d_1 | r_0\end{matrix}\right.\implies d_1 | b \wedge r_0 = d_2}}$
وبالتالي : $\displaystyle{\displaylines{d_1 | d_2}}$
ولدينا أيضا :
$\displaystyle{\displaylines{\left\{\begin{matrix}d_2 | b\\ d_2 | r_0\end{matrix}\right.\implies d_2 | r_0 + bq_0=a}}$
لدينا اذن الآتي :
$\displaystyle{\displaylines{\left\{\begin{matrix}d_2 | b\\ d_2 | a\end{matrix}\right.\Rightarrow d_2 | a \wedge b = d_1}}$
وبالتالي : $\displaystyle{\displaylines{d_2 | d_1}}$
لدينا $\displaystyle{\displaylines{d_1 | d_2}}$ و $\displaystyle{\displaylines{d_2 | d_1}}$ والاعداد صحيحة طبيعية موجبة إذن : $\displaystyle{\displaylines{d_1 = d_2}}$.
إذن : $\displaystyle{\displaylines{a \wedge b = b \wedge r_0}}$
لدينا $\displaystyle{\displaylines{(r_n)_{n \in \mathbb{N}}}}$ تناقصية قطعا وقيمها في $\displaystyle{\displaylines{\mathbb{N}}}$
$\displaystyle{\displaylines{r_n<r_{n-1}<...<r_2<r_1<r_0}}$
وبالتالي يوجد $\displaystyle{\displaylines{n}}$ بحيث $\displaystyle{\displaylines{\forall m > n \, : \, r_{m} = 0}}$
إذن يوجد $\displaystyle{\displaylines{n}}$ بحيث $\displaystyle{\displaylines{r_{n+1} = 0}}$
لدينا : $\displaystyle{\displaylines{a \wedge b = b \wedge r_0 = r_0 \wedge r_1 = ... = r_{n-2} \wedge r_{n-1} = r_{n-1} \wedge r_{n}}}$
ولدينا : $\displaystyle{\displaylines{r_{n-1}=r_{n}q_{n+1}+r_{n+1} }}$
بما أن $\displaystyle{\displaylines{r_{n+1} = 0}}$ فإن $\displaystyle{\displaylines{r_n}}$ يقسم $\displaystyle{\displaylines{r_{n-1}}}$
إذن $\displaystyle{\displaylines{r_{n-1} \wedge r_{n} = r_{n}}}$
وبالتالي : $\displaystyle{\displaylines{a \wedge b = r_{n}}}$
