القاسم المشترك الأكبر (الأعظم)

Greatest Common Divisor

تعريف 1: ليكن a, b عددين صحيحين ليس كلاهما صفرا , نعرف القاسم المشترك الأكبر لهما Greatest Common Divisor ورمزه $\gcd (a,b)$ على النحو التالي :

$\gcd (a,b) = \max \{ n \in \mathbb{Z}:n|a,n|b\}$

يتضح من التعريف أن القاسم المشترك الأكبر عبارة عن أكبر القواسم المشتركة للعددين . أحيانا نستخدم الرمز $(a,b)$ للدلالة على القاسم المشترك الأكبر بدلا من $\gcd (a,b)$ . مثلا

( 4, 10)=2 , (6,8)=2 , (15,5)=5 , (7, 12)=1 , (3, 0)=1

وجود ووحدانية القاسم المشترك الأكبر لعددين:بما أن العدد 1 هو قاسم مشترك لأي عددين فإن المجموعة التي في التعريف غير خالية وبالتالي $\gcd (a,b)$ أكبر من أو يساوى الواحد. كذلك المجموعة

$\{ n \in \mathbb{Z}:n|a,n|b\}$

مجموعة منتهية وبذلك فإن لها عنصر أكبر ونظرا لأن العنصر الأكبر لمجموعة (إن وجد) هو عنصر وحيد فإن القاسم المشترك الأكبر لعددين هو عدد وحيد.

حقيقة 1: لأي عددين $a,b \in \mathbb{Z}$ ليس كلاهما صفرا فإن

$\gcd (a,b) = \gcd (b,a) = \gcd (a, - b) = \gcd ( - a, - b) = \gcd (\left| a \right|,\left| b \right|)$

البرهان :المساواة $\gcd (a,b) = \gcd (b,a)$ بديهية. لإثبات أن $\gcd (a,b) = \gcd (a, - b)$ افرض أن $d = \gcd (a,b)$ . إذا d هو أيضا القاسم المشترك الأكبر لكلا من a, -b لأن خلاف هذا يعني وجود عدد أكبر من d وليكن g بحيث يقسم كلا من a, -b . وهذا يقتضي أن يكون g قاسم لكلا من a, b وبالتالي لم يعد d هو القاسم المشترك الأكبر وهذا تناقض. إذا $\gcd (a,b) = \gcd (a, - b)$ . يمكن الاستفادة مما سبق إثباته لبيان أن $\gcd (a, - b) = \gcd ( - a, - b)$ حيث:

$\gcd (a, - b) = \gcd ( - b,a) = \gcd ( - b, - a) = \gcd ( - a, - b)$

والمساواة $\gcd (a,b) = \gcd (\left| a \right|,\left| b \right|)$ نثبتها من خلال $\gcd (a,b) = \gcd ( - a, - b)$ إذا كان a, b سالبين أو من خلال $\gcd (a,b) = \gcd (a, - b)$ إذا كان احد العددين a, b فقط موجب . أما إذا كان a, b موجبين فلا يوجد ما نثبته.

حقيقة 2: لأي عددين $a,b \in \mathbb{Z}$ ليس كلاهما صفرا فإن

$\gcd (a,b) = \gcd (a,b + a) = \gcd (a,b - a)$

سنثبت أولا أن $\gcd (a,b) = \gcd (a,b + a)$ . ليكن $d = \gcd (a,b)$ . بما أن d يقسم كلا من العددين a, b فإنه يقسم مجموعهما. إذا d قاسم مشترك للعددين a, a+b . لنفرض أنه ليس القاسم المشترك الأكبر لهما, هذا يعني وجود عدد أكبر منه وليكن g بحيث يقسم كلا من a, a+b . إذا g يقسم الفرق بينهما b وبالتالي لم يعد d هو القاسم المشترك الأكبر وهذا تناقض. إذا

$\gcd (a,b) = \gcd (a,b + a)$

وبالمثل نثبت الجزء الآخر. فإذا كان d القاسم المشترك الأكبر للعددين a, b فإنه يقسم الفرق a - b. إذا d قاسم مشترك للعددين a, a - b . لنفرض أنه ليس القاسم المشترك الأكبر لهما, هذا يعني وجود عدد أكبر منه وليكن g بحيث يقسم كلا من a, a - b . إذا g يقسم الفرق بينهما ) a - (a - b , أي يقسم b وبالتالي لم يعد d هو القاسم المشترك الأكبر وهذا تناقض. إذا

$\gcd (a,b) = \gcd (a,b - a)$