القاسم المشترك الأكبر (الأعظم)
Greatest Common Divisor
تعريف 1: ليكن a, b عددين صحيحين ليس كلاهما صفرا , نعرف القاسم المشترك الأكبر لهما Greatest Common Divisor ورمزه على النحو التالي :
يتضح من التعريف أن القاسم المشترك الأكبر عبارة عن أكبر القواسم المشتركة للعددين . أحيانا نستخدم الرمز للدلالة على القاسم المشترك الأكبر بدلا من . مثلا
( 4, 10)=2 , (6,
=2 , (15,5)=5 , (7, 12)=1 , (3, 0)=1
وجود ووحدانية القاسم المشترك الأكبر لعددين:بما أن العدد 1 هو قاسم مشترك لأي عددين فإن المجموعة التي في التعريف غير خالية وبالتالي أكبر من أو يساوى الواحد. كذلك المجموعة
مجموعة منتهية وبذلك فإن لها عنصر أكبر ونظرا لأن العنصر الأكبر لمجموعة (إن وجد) هو عنصر وحيد فإن القاسم المشترك الأكبر لعددين هو عدد وحيد.
حقيقة 1: لأي عددين ليس كلاهما صفرا فإن
البرهان :المساواة بديهية. لإثبات أن افرض أن . إذا d هو أيضا القاسم المشترك الأكبر لكلا من a, -b لأن خلاف هذا يعني وجود عدد أكبر من d وليكن g بحيث يقسم كلا من a, -b . وهذا يقتضي أن يكون g قاسم لكلا من a, b وبالتالي لم يعد d هو القاسم المشترك الأكبر وهذا تناقض. إذا . يمكن الاستفادة مما سبق إثباته لبيان أنحيث:
والمساواة نثبتها من خلال إذا كان a, b سالبين أو من خلال إذا كان احد العددين a, b فقط موجب . أما إذا كان a, b موجبين فلا يوجد ما نثبته.
حقيقة 2: لأي عددين ليس كلاهما صفرا فإن
سنثبت أولا أن . ليكن. بما أن d يقسم كلا من العددين a, b فإنه يقسم مجموعهما. إذا d قاسم مشترك للعددين a, a+b . لنفرض أنه ليس القاسم المشترك الأكبر لهما, هذا يعني وجود عدد أكبر منه وليكن g بحيث يقسم كلا من a, a+b . إذا g يقسم الفرق بينهما b وبالتالي لم يعد d هو القاسم المشترك الأكبر وهذا تناقض. إذا
وبالمثل نثبت الجزء الآخر. فإذا كان d القاسم المشترك الأكبر للعددين a, b فإنه يقسم الفرق a - b. إذا d قاسم مشترك للعددين a, a - b . لنفرض أنه ليس القاسم المشترك الأكبر لهما, هذا يعني وجود عدد أكبر منه وليكن g بحيث يقسم كلا من a, a - b . إذا g يقسم الفرق بينهما ) a - (a - b , أي يقسم b وبالتالي لم يعد d هو القاسم المشترك الأكبر وهذا تناقض. إذا
وبهذا يكتمل الإثبات.
مسائل
1. (تعميم لمعلومة سابقة) بين أنه لكل عدد طبيعي n , .
2. إذا كان c يقسم كلا من a , b فإن c يقسم .
3. إذا كانت فبين أن
Greatest Common Divisor
تعريف 1: ليكن a, b عددين صحيحين ليس كلاهما صفرا , نعرف القاسم المشترك الأكبر لهما Greatest Common Divisor ورمزه على النحو التالي :
يتضح من التعريف أن القاسم المشترك الأكبر عبارة عن أكبر القواسم المشتركة للعددين . أحيانا نستخدم الرمز للدلالة على القاسم المشترك الأكبر بدلا من . مثلا
( 4, 10)=2 , (6,
=2 , (15,5)=5 , (7, 12)=1 , (3, 0)=1وجود ووحدانية القاسم المشترك الأكبر لعددين:بما أن العدد 1 هو قاسم مشترك لأي عددين فإن المجموعة التي في التعريف غير خالية وبالتالي أكبر من أو يساوى الواحد. كذلك المجموعة
مجموعة منتهية وبذلك فإن لها عنصر أكبر ونظرا لأن العنصر الأكبر لمجموعة (إن وجد) هو عنصر وحيد فإن القاسم المشترك الأكبر لعددين هو عدد وحيد.
حقيقة 1: لأي عددين ليس كلاهما صفرا فإن
البرهان :المساواة بديهية. لإثبات أن افرض أن . إذا d هو أيضا القاسم المشترك الأكبر لكلا من a, -b لأن خلاف هذا يعني وجود عدد أكبر من d وليكن g بحيث يقسم كلا من a, -b . وهذا يقتضي أن يكون g قاسم لكلا من a, b وبالتالي لم يعد d هو القاسم المشترك الأكبر وهذا تناقض. إذا . يمكن الاستفادة مما سبق إثباته لبيان أنحيث:
والمساواة نثبتها من خلال إذا كان a, b سالبين أو من خلال إذا كان احد العددين a, b فقط موجب . أما إذا كان a, b موجبين فلا يوجد ما نثبته.
حقيقة 2: لأي عددين ليس كلاهما صفرا فإن
سنثبت أولا أن . ليكن. بما أن d يقسم كلا من العددين a, b فإنه يقسم مجموعهما. إذا d قاسم مشترك للعددين a, a+b . لنفرض أنه ليس القاسم المشترك الأكبر لهما, هذا يعني وجود عدد أكبر منه وليكن g بحيث يقسم كلا من a, a+b . إذا g يقسم الفرق بينهما b وبالتالي لم يعد d هو القاسم المشترك الأكبر وهذا تناقض. إذا
وبالمثل نثبت الجزء الآخر. فإذا كان d القاسم المشترك الأكبر للعددين a, b فإنه يقسم الفرق a - b. إذا d قاسم مشترك للعددين a, a - b . لنفرض أنه ليس القاسم المشترك الأكبر لهما, هذا يعني وجود عدد أكبر منه وليكن g بحيث يقسم كلا من a, a - b . إذا g يقسم الفرق بينهما ) a - (a - b , أي يقسم b وبالتالي لم يعد d هو القاسم المشترك الأكبر وهذا تناقض. إذا
وبهذا يكتمل الإثبات.
مسائل
1. (تعميم لمعلومة سابقة) بين أنه لكل عدد طبيعي n , .
2. إذا كان c يقسم كلا من a , b فإن c يقسم .
3. إذا كانت فبين أن
