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

خوارزمية أقليدس لتحديد القاسم المشترك الأكبر

site lagrida الرياضيات بالعربية نظرية الأعداد Théorie des nombres خوارزمية أقليدس لتحديد القاسم المشترك الأكبر
ليكن $a$ و $b$ عددين صحيحين طبيعيين غير منعدمين بحيث $b$ لا يقسم $a$.

تنص خوارزمية أقليدس (Algorithme d'Euclide) لتحديد القاسم المشترك الأكبر على :

$\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}$

القاسم المشترك الأكبر للعددين $a$ و $b$ هو آخر باقي غير منعدم. لدينا $a \wedge b = r_n$.


1) بين أن $a \wedge b = b \wedge r_0$.

2) بين أنه يوجد $n$ من $\mathbb{N}$ بحيث $r_{n+1} = 0$.

3) استنتج أن $a \wedge b = r_n$.
لدينا : $a = b q_0 + r_0$.

نضع $d_1 = a \wedge b$ و $d_2 = b \wedge r_0$

لدينا :
$\left\{\begin{matrix}d_1 | a\\ d_1 | b\end{matrix}\right.\Rightarrow d_1 | a - bq_0=r_0$

لدينا اذن الآتي :
$\left\{\begin{matrix}d_1 | b\\ d_1 | r_0\end{matrix}\right.\Rightarrow d_1 | b \wedge r_0 = d_2$

وبالتالي : $d_1 | d_2$.

ولدينا أيضا :
$\left\{\begin{matrix}d_2 | b\\ d_2 | r_0\end{matrix}\right.\Rightarrow d_2 | r_0 + bq_0=a$

لدينا اذن الآتي :
$\left\{\begin{matrix}d_2 | b\\ d_2 | a\end{matrix}\right.\Rightarrow d_2 | a \wedge b = d_1$

وبالتالي : $d_2 | d_1$.

لدينا $d_1 | d_2$ و $d_2 | d_1$ والاعداد صحيحة طبيعية موجبة إذن : $d_1 = d_2$.

إذن : $a \wedge b = b \wedge r_0$


لدينا $(r_n)_{n \in \mathbb{N}}$ تناقصية قطعا وقيمها في $\mathbb{N}$ : $r_n \in \mathbb{N}$.

$r_n<r_{n-1}<...<r_2<r_1<r_0$

وبالتالي يوجد $n$ بحيث $\forall m > n \, : \, r_{m} = 0$.

إذن يوجد $n$ بحيث $r_{n+1} = 0$


لدينا : $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}$.

بما أن $r_{n+1} = 0$ فإن $r_n$ يقسم $r_{n-1}$.

إذن $r_{n-1} \wedge r_{n} = r_{n}$

وبالتالي : $a \wedge b = r_{n}$