Greatest Common Divisor

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

[tex]
\gcd (a,b) = \max \{ n \in \mathbb{Z}:n|a,n|b\}
[/tex]

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

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

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

[tex]\{ n \in \mathbb{Z}:n|a,n|b\} [/tex]

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

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

[tex]\gcd (a,b) = \gcd (b,a) = \gcd (a, - b) = \gcd ( - a, - b) = \gcd (\left| a \right|,\left| b \right|)[/tex]

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

[tex]\gcd (a, - b) = \gcd ( - b,a) = \gcd ( - b, - a) = \gcd ( - a, - b)[/tex]

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

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

[tex]\gcd (a,b) = \gcd (a,b + a) = \gcd (a,b - a)[/tex]

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

[tex]\gcd (a,b) = \gcd (a,b + a)[/tex]

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

[tex]\gcd (a,b) = \gcd (a,b - a)[/tex]

وبهذا يكتمل الإثبات.

مسائل

1. (تعميم لمعلومة سابقة) بين أنه لكل عدد طبيعي n , [tex]\gcd (a,b) = \gcd (a,b - na)[/tex].

2. إذا كان c يقسم كلا من a , b فإن c يقسم [tex]\gcd (a,b)[/tex].

3. إذا كانت [tex]m,n \in \mathbb{N}[/tex] فبين أن [tex]\gcd (2^m - 1,2^n - 1) = 2^{\gcd (m,n)} - 1[/tex].

نبذة عن كاتب الموضوع

الإسم: محترف

عضو مؤسس في شبكة الرياضيات رمز.