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

Greatest Common Divisor

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

$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|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)$

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

مسائل

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

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

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

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

$User picture$

الإسم: محترف

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

علِّق

التعليق: *

Every instance heading tags will be modified to include an id attribute for anchor linking.
Every instance of "" in the input text will be replaced with a collapsible mediawiki-style table of contents. Accepts options for title, list style, minimum heading level, and maximum heading level as follows: . All arguments are optional and defaults are shown.
LaTeX formulas are automatically converted into images.
وسوم html المسموح بها: <a> <i> <p> <b> <em> <center> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <div> <dir> <span> <style> <br> <br /> <blockquote> <h1> <h2> <h3> <h4> <h5> <h6> <hr> <img> <sub> <sup> <table> <tbody> <tfoot> <th> <thead> <tr> <td> <dd>
بإمكانك استخدام وسوم BBCode في النصوص URLs will automatically be converted to links.
تتحول مسارات مواقع وب و عناوين البريد الإلكتروني إلى روابط آليا.
Use [fn]...[/fn] (or <fn>...</fn>) to insert automatically numbered footnotes.
Use [# ...] to insert automatically numbered footnotes. Textile variant.
Web page addresses and e-mail addresses turn into links automatically. (Better URL filter.)
Link to content with [[some text]], where "some text" is the title of existing content or the title of a new piece of content to create. You can also link text to a different title by using [[link to this title|show this text]]. Link to outside URLs with [[http://www.example.com|some text]], or even [[http://www.example.com]].
Glossary terms will be automatically marked with links to their descriptions. If there are certain phrases or sections of text that should be excluded from glossary marking and linking, use the special markup, [no-glossary] ... [/no-glossary]. Additionally, these HTML elements will not be scanned: a, abbr, acronym, code, pre.
Images can be added to this post.

معلومات أكثر عن خيارات التنسيق

كلمة التحقق

This question is for testing whether you are a human visitor and to prevent automated spam submissions.