مقالات

5.4: أكبر قواسم مشتركة - الرياضيات


بالنظر إلى أي عددين صحيحين (أ ) و (ب ) ، فإن العدد الصحيح (ج neq0 ) هو القاسم المشترك أو عامل مشترك من (أ ) و (ب ) إذا كان (ج ) يقسم كلا من (أ ) و (ب ). إذا كان ، بالإضافة إلى ذلك ، (أ ) و (ب ) لا يساويان صفرًا ، فإن القاسم المشترك الأكبر، يُشار إليه بـ ( gcd (a، b) ) ، يُعرَّف بأنه أكبر قاسم مشترك لـ (a ) و (b ). يجب أن يكون واضحًا أن ( gcd (a، b) ) يجب أن تكون موجبة.

مثال ( PageIndex {1} label {eg: gcd-01} )

القواسم المشتركة بين 24 و 42 هي ( pm1 ) و ( pm2 ) و ( pm3 ) و ( pm6 ). من بينها ، 6 هي الأكبر. لذلك ، ( gcd (24،42) = 6 ). القواسم المشتركة بين 12 و 32 هي ( pm1 ) و ( pm2 ) و ( pm4 ) ، ويتبع ذلك ( gcd (12،32) = 4 ).

تمرين عملي ( PageIndex {1} label {he: gcd-01} )

تحقق من أن [ gcd (5،35) = 5، quad gcd (-5،10) = 5، quad gcd (20، -10) = 10، quad mbox {and} quad gcd (20،70) = 10. nonumber ] اشرح لماذا ( gcd (3،5) = 1 )

مثال ( PageIndex {2} label {eg: gcd-02} )

هل يمكن أن توضح لماذا ( gcd (0،3) = 3 )؟ ماذا عن ( gcd (0، -3) = 3 )؟

حل

تذكر أن الرقم 0 قابل للقسمة على أي عدد صحيح غير صفري. ومن ثم ، فإن جميع القواسم على 3 هي أيضًا قواسم على 0. من الواضح أن 3 نفسها هي أكبر قواسم على 3. لذلك ، ( gcd (0،3) = 3 ).

تمرين عملي ( PageIndex {2} label {he: gcd-02} )

اشرح لماذا ( gcd (0، -8) = 8 ).

النظرية ( PageIndex {1} label {thm: gcd0b} )

لأي عدد صحيح غير صفري (b ) ، لدينا ( gcd (0، b) = | b | ).

دليل

أكبر قاسم موجب لـ (b ) هو (| b | ). نظرًا لأن (| b | ) يقسم أيضًا 0 ، نستنتج أن ( gcd (0، b) = | b | ).

تخبرنا النظرية 5.4.1 أن ( gcd (0، b) = | b | ) إذا كان (b ) غير صفري. من تعريف القاسم المشترك والمقسوم عليه الأكبر ، من الواضح أن ( gcd (a، b) = gcd (b، a) ) و ( gcd (a، b) = gcd ( م أ ، م ب) ). لذلك قد نفترض (1 leq a leq b ).

نظرية ( PageIndex {2} )

دع (أ ) و (ب ) عددًا صحيحًا مثل (1 ليك أ ليك ب ). إذا (b = aq + r ) ، حيث (0 leq r

دليل

لتسهيل حجتنا ، دع (d = gcd (b، a) ) و (e = gcd (a، r) ). بحكم التعريف ، (د ) هو قاسم لكل من (ب ) و (أ ). لذلك ، (b = dx ) و (a = dy ) لبعض الأعداد الصحيحة (x ) و (y ). ثم [r = b-aq = dx-dy cdot q = d (x-yq) ، nonumber ] حيث (x-yq ) عدد صحيح. ومن ثم ، (د منتصف r ). هذا يجعل (d ) قاسمًا مشتركًا لكل من (r ) و (أ ). نظرًا لأن (e ) هو القاسم المشترك الأكبر لـ (a ) و (r ) ، فإننا نحدد ذلك (d leq e ).

وبالمثل ، (e = gcd (a، r) ) هو قاسم لكل من (a ) و (r ). وبالتالي ، (a = eu ) و (r = ev ) لبعض الأعداد الصحيحة (u ) و (v ). ثم [b = aq + r = a cdot eu + ev = e (au + v) ، nonumber ] حيث (au + v ) هو عدد صحيح. ومن ثم ، (e mid b ). هذا يجعل (هـ ) قاسمًا مشتركًا لكل من (ب ) و (أ ). نظرًا لأن (d ) هو القاسم المشترك الأكبر لـ (b ) و (أ ) ، فإننا نستنتج ذلك (e leq d ). جنبًا إلى جنب مع (d leq e ) ، نستنتج أن (d = e ).

مثال ( PageIndex {3} label {eg: gcd-03} )

من (997 = 996 cdot1 + 1 ) ، نحصل على ( gcd (997،996) = gcd (996،1) = 1 ).

تؤكد النظرية أن ( gcd (b، a) = gcd (a، r) ). يمكننا تطبيق النظرية مرة أخرى على ( gcd (a، r) ). ينتج عن قسمة (a ) على (r ) حاصل قسمة جديد وباقي جديد. إذا لزم الأمر ، كرر العملية حتى يصبح الباقي صفراً. إذا أشرنا إلى (b = r_0 ) و (a = r_1 ) ، إذن [ ابدأ {array} {rcl @ { qquad qquad} l} r_0 & = & r_1 q_1 + r_2، & 0 leq r_2 آخر باقي غير صفري هو ( gcd (a، b) ). تسمى هذه الطريقة لإيجاد القاسم المشترك الأكبر الخوارزمية الإقليدية.

مثال ( PageIndex {4} label {eg: gcd-04} )

ابحث عن ( gcd (426،246) ).

حل

من خلال تطبيق النظرية بشكل متكرر ، نجد [ start {array} {rcl @ { qquad qquad} lcl} 426 & = & 246 cdot1 + 180، & gcd (426،246) & = & gcd (246،180) 246 & = & 180 cdot1 + 66، & gcd (246،180) & = & gcd (180، 66) 180 & = & 66 cdot2 + 48، & gcd (180، 66) & = & gcd (66، 48) 66 & = & 48 cdot1 + 18، & gcd (66، 48) & = & gcd (48، 18) 48 & = & 18 cdot2 + 12، & gcd ( 48، 18) & = & gcd (18، 12) 18 & = & 12 cdot1 + 6، & gcd (18، 12) & = & gcd (12، 6) 12 & = & 6 cdot2 + 0، & gcd (12، 6) & = & gcd (6، 0) = 6. end {array} nonumber ] لذلك ، ( gcd (426،246) = 6 ).

تمرين عملي ( PageIndex {3} label {he: gcd-03} )

حدد ( gcd (732،153) ).

تمرين عملي ( PageIndex {4} label {he: gcd-04} )

حدد ( gcd (6958،2478) ).

يدويًا ، يكون استخدام تنسيق من عمودين أكثر كفاءة. أولاً ، ضع العددين 426 و 246 في عمودين منفصلين ، مع وضع الرقم الأكبر على اليسار. قم بإجراء قسمة قصيرة ، واكتب حاصل القسمة على اليسار: [ start {array} {r | r | r | r} 1 & 426 & 246 & & 246 & & cline {2-2 } & 180 & & end {array} nonumber ]

في الجولة التالية ، قم بإجراء قسمة قصيرة أخرى على العددين 246 و 180 في الأسفل. نظرًا لأن الرقم الأكبر موجود الآن في العمود الأيمن ، اترك حاصل القسمة على يمينه:

[ start {array} [t] {r | r | r | r} 1 & 426 & 246 & 1 & 246 & 180 & hline & 180 & 66 & end {array} nonumber ]

استمر بهذه الطريقة حتى يصبح الباقي 0. الإدخال الأخير غير الصفري في الأسفل هو القاسم المشترك الأكبر. يمكننا أيضًا ترك كل حاصل القسمة على اليسار:

[ start {array} [c] {r | r | r | r} 1 & 426 & 246 & 1 & 246 & 180 & hline 2 & 180 & 66 & 1 & 132 & 48 & hline 2 & 48 & 18 & 1 & 36 & 12 & hline 2 & 12 & 6 & & 12 & & hline & 0 & end {array} hskip0. 5in mbox {or} hskip0.5in start {array} [c] {r | r | r | r} 1 & 426 & 246 & 1 & 246 & 180 & hline 2 & 180 & 66 & 1 & 132 & 48 & hline 2 & 48 & 18 & 1 & 36 & 12 & hline 2 & 12 & 6 & & 12 & & hline & 0 & نهاية {مجموعة} غير رقم ]

تمرين عملي ( PageIndex {5} label {he: gcd-05} )

استخدم التنسيق المكون من عمودين لحساب ( gcd (153،732) ).

تمرين عملي ( PageIndex {6} label {eg: gcd-06} )

استخدم التنسيق المكون من عمودين لحساب ( gcd (6958،2478) ).

بالنظر إلى أي أعداد صحيحة (m ) و (n ) ، فإن أرقام النموذج (ms + nt ) ، حيث (s ، t ) هي أعداد صحيحة ، تسمى تركيبات خطية من (م ) و (ن ). يلعبون دورًا مهمًا في دراسة ( gcd (m، n) ) ، كما هو موضح في النظرية التالية.

نظرية ( PageIndex {3} )

لأي أعداد صحيحة غير صفرية (a ) و (b ) ، توجد أعداد صحيحة (s ) و (t ) مثل ( gcd (a ، b) = as + bt ).

دليل

إن إثبات هذه النظرية طويل ومعقد. نترك الأمر ، إلى جانب النتائج الأخرى ذات الصلة ، والكثير منها تقني إلى حد ما ، في القسم التالي.

نظرية ( PageIndex {4} )

كل تركيبة خطية من (أ ) و (ب ) هي مضاعف ( gcd (أ ، ب) ).

نتيجة طبيعية ( PageIndex {5} )

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

من المهم أن نفهم ما تقوله هذه النتائج الثلاث. يعطينا العثور على تركيبة خطية من (أ ) و (ب ) فقط مضاعفات ( gcd (أ ، ب) ). فقط مجموعة خطية خاصة ستنتج القيمة الدقيقة لـ ( gcd (a، b) ).

مثال ( PageIndex {5} label {eg: gcd-05} )

لنفترض (n ) و (n + 1 ) أن يكونا رقمين صحيحين موجبين متتاليين. ثم يشير [n cdot (-1) + (n + 1) cdot1 = 1 nonumber ] إلى أن 1 هو أحد مضاعفات القاسم المشترك الأكبر لـ (n ) و (n + 1 ). هذا يعني أن القاسم المشترك الأكبر يجب أن يكون 1. لذلك ، ( gcd (n، n + 1) = 1 ) لجميع الأعداد الصحيحة (n ).

تعريف

يُقال أن رقمين صحيحين (أ ) و (ب ) رئيس نسبيا إذا ( gcd (أ ، ب) = 1 ). لذلك ، (أ ) و (ب ) عدد أولي نسبيًا إذا لم يكن لديهما قواسم مشتركة باستثناء ( مساء 1 ).

مثال ( PageIndex {6} label {eg: gcd-06} )

أثبت أنه إذا ( gcd (a، b) = 1 ) ، فإن ( gcd (a + b، a-b) ) يساوي 1 أو 2.

حل

من التركيبات الخطية [ start {align} (a + b) cdot1 + (ab) cdot1 & = & 2a، (a + b) cdot1 + (ab) cdot (-1) & = & 2b ، end {align} nonumber ] نعلم أن ( gcd (a + b، ab) ) يقسم كلا من (2a ) و (2b ). بما أن ( gcd (a، b) = 1 ) ، نستنتج أن ( gcd (a + b، ab) ) يقسم 2. وبالتالي ، ( ( gcd (a + b، ab) ) هو إما 1 أو 2.

مثال ( PageIndex {7} label {eg: gcd-07} )

أظهر أنه إذا كان ( gcd (a، b) = 1 ) ، فإن ( gcd (2a + b، a + 2b) ) يساوي إما 1 أو 3.

حل

من التركيبات الخطية [ start {align} (2a + b) cdot 2 + (a + 2b) cdot (-1) & = & 3a ، (2a + b) cdot (-1) + (a + 2b) cdot 2 & = & 3b، end {align} nonumber ] نعلم أن ( gcd (2a + b، a + 2b) ) يقسم كلاهما (3a ) و ( 3 ب). بما أن ( gcd (a، b) = 1 ) ، نستنتج أن ( gcd (2a + b، a + 2b) ) يقسم 3. وهكذا ، ( gcd (a + b، ab) ) هي 1 أو 3.

تمرين عملي ( PageIndex {7} label {he: gcd-07} )

ما هي القيم المحتملة لـ ( gcd (5m + 7n ، 7m + 5n) ) إذا كان العددان الصحيحان الموجبان (m ) و (n ) أوليان نسبيًا؟

مثال ( PageIndex {8} label {eg: gcd-08} )

أوجد الأعداد الصحيحة (s ) و (t ) بحيث (6 = gcd (426،246) = 246s + 426t ).

حل

درسنا سابقًا كيفية إيجاد ( gcd (426،246) = 6 ). في كل قسم ، نريد أن نعبر عن الباقي كمجموعة خطية من 246 و 426. هذه هي الطريقة التي يتم بها الحساب:

[ start {array} {lrcl} 426 = 246 cdot1 + 180، & 180 & = & 246 cdot (-1) +426 cdot1 [3pt] 246 = 180 cdot1 + 66، & 66 & = & 246 cdot1 + 180 cdot (-1) & & = & 246 cdot1 + [246 cdot (-1) +426 cdot1] cdot (-1) & & = & 246 cdot2 +426 cdot (-1) [3pt] 180 = 66 cdot2 + 48، & 48 & = & 180 cdot1 + 66 cdot (-2) & & = & [246 cdot (-1 ) +426 cdot1] cdot1 + [246 cdot2 + 426 cdot (-1)] cdot (-2) & & = & 246 (-5) +426 cdot3 66 = 48 cdot1 +18، & 18 & = & 66 cdot1 + 48 cdot (-1) & & = & [246 cdot2 + 426 cdot (-1)] cdot1 + [246 (-5) +426 cdot3] cdot (-1) & & = & 246 cdot7 + 426 cdot (-4) [3pt] 48 = 18 cdot2 + 12، & 12 & = & 48 cdot1 + 18 cdot (-2) & & = & [246 (-5) +426 cdot3] cdot1 + [246 cdot7 + 426 cdot (-4)] cdot (-2) & & = & 246 cdot (-19) +426 cdot11 [3pt] 18 = 12 cdot1 + 6، & 6 & = & 18 cdot1 + 12 cdot (-1) & & = & [246 cdot7 + 426 cdot (-4)] cdot1 + [246 cdot (-19) +426 cdot11] cdot (-1) & & = & 246 cdot26 + 426 cdot (-15) end { مجموعة} عدد ]

الإجابة هي (6 = 246 cdot26 + 426 cdot (-15) ).

الحساب ممل! ال تمديد الخوارزمية الإقليدية يوفر الراحة. إنه يتتبع تسلسلين من الأعداد الصحيحة (s_k ) و (t_k ) جنبًا إلى جنب مع (r_k ) ، مثل [r_k = a s_k + b t_k. nonumber ] هذا يعبر عن كل الباقي كمجموعة خطية من (أ ) و (ب ). نظرًا لأن الباقي الأخير غير الصفري هو ( gcd (a، b) ) ، فإن التركيبة الخطية المقابلة ستكون هي الإجابة التي نبحث عنها.

يتم تلخيص قيم (s_k ) و (t_k ) للمثال الأخير أدناه:

[ ابدأ {مجموعة} {| c | r | r | r | } hline k & r_k & s_k & t_k hline 2 & 180 & -1 & 1 3 & 60 & 2 & -1 4 & 48 & -5 & 3 5 & 18 & 7 & -4 6 & 12 & -19 & 11 7 & 6 & 26 & -15 hline end {array} nonumber ]

القضية الرئيسية هي: كيف يمكننا حساب هذه القيم بكفاءة؟

يبدأ الجدول أعلاه بـ (ك = 2 ). ماذا عن (ك = 0 ) و (ك = 1 )؟ من [b = r_0 = a s_0 + b t_0، nonumber ] نحدد أن (s_0 = 0 ) و (t_0 = 1 ). بصورة مماثلة،

[a = r_1 = أ s_1 + ب t_1 غير رقم ]

يعني أن (s_1 = 1 ) و (t_1 = 0 ). ومن ثم ، فإن قائمة قيم (s_k ) و (t_k ) تبدأ بما يلي:

[ start {array} {ccc} k & s_k & t_k 0 & 0 & 1 1 & 1 & 0 end {array} nonumber ]

بشكل عام ، قبل تنفيذ التقسيم (r_ {k-1} div r_k ) ، يجب أن نكون قد أنشأنا بالفعل (s_0 ) من خلال (s_k ) ، و (t_0 ) من خلال (t_k ). بعد التقسيم ، نحصل على (q_k ) و (r_ {k + 1} ) كما في

[r_ {k-1} = r_k q_k + r_ {k + 1}. لا يوجد رقم]

بعد ذلك ، نحسب (s_ {k + 1} ) و (t_ {k + 1} ) قبل الانتقال إلى القسمة التالية. نجد

[ start {array} {rcl} r_ {k + 1} & = & r_ {k-1} - r_k q_k & = & (a s_ {k-1} + bt_ {k-1}) - (a s_k + b t_k) q_k & = & a (s_ {k-1} - s_k q_k) + b (t_ {k-1} - t_k q_k). نهاية {مجموعة} غير رقم ]

لذلك نحن بحاجة

[ start {array} {r c l} s_ {k + 1} & = & s_ {k-1} - s_k q_k، t_ {k + 1} & = & t_ {k-1} - t_k q_k. نهاية {مجموعة} غير رقم ]

بكلمات:

[ displaylines { mbox {next $ s $ -value} = mbox {previous-previous $ s $ -value} - mbox {previous $ s $ -value} times mbox {المقابل $ q $} ، cr mbox {next $ t $ -value} = mbox {previous-previous $ t $ -value} - mbox {previous $ t $ -value} times mbox {المقابل $ q $}. cr} nonumber ]

على سبيل المثال ، افترض في مرحلة معينة أن قيم (s ) و (t ) و (q ) هي كما يلي:

[ start {array} {ccc} k & s_k & t_k & q_k ​​ 0 & 0 & 1 & 1 & 1 & 0 & 1 2 & -1 & 1 & 1 3 & 2 & -1 & 2 & & & 1 & & & 2 & & & 1 & & & 2 end {array} nonumber ] ثم [ displaylines { mbox {next $ s $ -value} = -1-2 cdot2 = -5 ، cr mbox {next $ t $ -value} = 1 - (- 1) cdot2 = 3. cr} nonumber ] الآن تصبح القائمة [ ابدأ {مجموعة} {ccc} k & s_k & t_k & q_k ​​ 0 & 0 & 1 & 1 & 1 & 0 & 1 2 & -1 & 1 & 1 3 & 2 & - 1 & 2 4 & -5 & 3 & 1 & & & 2 & & & 1 & & & 2 end {array} nonumber ]

يمكن إجراء الحساب بالكامل بتنسيق معدل من عمودين.

مثال ( PageIndex {9} label {eg: gcd-09} )

أوجد الأعداد الصحيحة (s ) و (t ) بحيث يكون ( gcd (246،426) = 246s + 426t ).

حل

أولاً ، انسخ حاصل القسمة من العمود الموجود في أقصى اليمين وأدخلها بين حاصلات القسمة في العمود الموجود في أقصى اليسار:

[ start {array} [c] {r | r | r | r} 1 & 426 & 246 & 1 & 246 & 180 & cline {2-3} 2 & 180 & 66 & 1 & 132 & 48 & cline {2-3} 2 & 48 & 18 & 1 & 36 & 12 & cline {2-3} 2 & 12 & 6 & & 12 & & & cline {2-2} & 0 & end {array} qquad mbox {يصبح} qquad start {array} [c] {r | r | r | r} 1 & 426 & 246 & 1 1 & 246 & 180 & cline {2-3} 2 & 180 & 66 & 1 1 & 132 & 48 & cline {2-3} 2 & 48 & 18 & 1 1 & 36 & 12 & cline {2-3} 2 & 12 & 6 & & 12 & & cline {2-2} & 0 & end {array} nonumber ]

بعد ذلك ، احسب (s_k ) و (t_k ) جنبًا إلى جنب مع هذه القسمة (لا نحتاج إلى تسجيل قيم (ك )):

[ start {array} [t] {rr @ { qquad} r | r | r | r} s_k & t_k & multicolumn {1} {r} {q_k} 0 & 1 1 & 0 & 1 & 426 & 246 & 1 -1 & 1 & 1 & 246 & 180 & cline {4-5} 2 & -1 & 2 & 180 & 66 & 1 -5 & 3 & 1 & 132 & 48 & cline {4-5} 7 & -4 & 2 & 48 & 18 & 1 -19 & 11 & 1 & 36 & 12 & cline {4-5} 26 & -15 & 2 & 12 & 6 & & & 12 & & cline {4-4} & & & 0 & end {array} nonumber ] الباقي الأخير غير الصفري هو القاسم المشترك الأكبر ، وتعطي المجموعة الخطية الأخيرة الإجابة المطلوبة. نجد ( gcd (246،426) = 6 = 26 cdot246-15 cdot426 ).

لاحظ أنه بدءًا من (k = 2 ) ، فإن علامات (s_k ) و (t_k ) بديلة. يوفر هذا فحصًا سريعًا لعلاماتهم. بالإضافة إلى ذلك ، فإن علامتي (s_k ) و (t_k ) متعاكستان لكل (k geq2 ).

تمرين عملي ( PageIndex {8} label {he: gcd-08} )

استخدم التنسيق المكون من عمودين للعثور على التركيبة الخطية التي تنتج ( gcd (153،732) ).

تمرين عملي ( PageIndex {9} label {he: gcd-09} )

استخدم التنسيق المكون من عمودين للعثور على التركيبة الخطية التي تنتج ( gcd (2478،6958) ).

ملخص ومراجعة

  • القاسم المشترك الأكبر لعددين صحيحين ، وليس كلاهما صفر ، هو أكبر عدد صحيح (ومن ثم يجب أن يكون موجبًا) يقسم كليهما.
  • استخدم الخوارزمية الإقليدية لإيجاد القاسم المشترك الأكبر. يمكن تنفيذه بتنسيق من عمودين.
  • باستخدام إصدار موسع يحتوي على عمودين إضافيين لحساب (s_k ) و (t_k ) ، يمكننا العثور على مجموعة خطية خاصة من عددين صحيحين ينتج عنه القاسم المشترك الأكبر بينهما.
  • بشكل عام ، تعطي التركيبة الخطية المكونة من عددين صحيحين مضاعف القاسم المشترك الأكبر.

تمرين ( PageIndex {1} label {ex: gcd-01} )

ابحث عن التركيبة الخطية التي تساوي القاسم المشترك الأكبر لكل زوج من أزواج الأعداد الصحيحة التالية.

  1. 27, 81
  2. 24, 84
  3. 1380, 3020

تمرين ( PageIndex {2} label {ex: gcd-02} )

ابحث عن التركيبة الخطية التي تساوي القاسم المشترك الأكبر لكل زوج من أزواج الأعداد الصحيحة التالية.

  1. 120, 615
  2. 412, 936
  3. 1122, 3672

تمرين ( PageIndex {3} label {ex: gcd-03} )

ما هي القيم الممكنة لـ ( gcd (2a + 5b، 5a-2b) ) إذا كان العددين الصحيحين الموجبين aa و bb أوليان نسبيًا؟

تمرين ( PageIndex {4} label {ex: gcd-04} )

إثبات أن أي أعداد صحيحة فردية موجبة متتالية أولية نسبيًا.

تمرين ( PageIndex {5} label {ex: gcd-05} )

دع (m ) و (n ) من الأعداد الصحيحة الموجبة. أثبت ذلك ( gcd (m، m + n) mid n ).

تمرين ( PageIndex {6} label {ex: gcd-06} )

دع (أ ) و (ب ) عددًا صحيحًا مثل (1 <أ <ب ) و ( جسد (أ ، ب) = 1 ). أثبت أن ( gcd (a + b، ab) = 1 ).

تمرين ( PageIndex {7} label {ex: gcd-07} )

ما هي القيم المحتملة لـ ( gcd (3m-5n ، 5m + 3n) ) إذا كان العددان الصحيحان الموجبان (m ) و (n ) أوليان نسبيًا؟

تمرين ( PageIndex {8} label {ex: gcd-08} )

ما هي القيم الممكنة لـ ( gcd (4p + 7q، 7p-4q) ) إذا كان العددان الصحيحان الموجبان (p ) و (q ) أوليان نسبيًا؟


5.4: أكبر قواسم مشتركة - الرياضيات

كما رأينا ، من أجل تحديد ما إذا كان من الممكن حل مشكلة قسمة ، نحتاج إلى معرفة ما إذا كان القاسم المشترك الأكبر للعدد الذي نقسم عليه هو 1. ويسمى عمومًا القاسم المشترك الأكبر لعددين القاسم المشترك الأكبر بين العددين. من السهل إيجاد القاسم المشترك الأكبر للأعداد الصغيرة عن طريق الفحص. النظر إلى جميع القواسم على رقم واحد ومعرفة ما إذا كانت تقسم الرقم الآخر أم لا ، واختيار أكبر قاسم يفعله. ومع ذلك ، عندما تكون الأرقام كبيرة ، فقد يستغرق ذلك وقتًا طويلاً. من المحتمل أن تبحث لفترة طويلة قبل أن تكتشف أن القاسم المشترك الأكبر بين 378 و 3465 هو 63. لحسن الحظ ، هناك طريقة لإيجاد القاسم المشترك الأكبر لعددين صحيحين ، والذي لا يتطلب أي تخمين. هذه الطريقة قديمة جدًا وتسمى الخوارزمية الإقليدية. سميت على اسم عالم الرياضيات اليوناني إقليدس الذي عاش حوالي 200 قبل الميلاد. اشتهر إقليدس بعمله في الهندسة ، لكنه قام أيضًا بالكثير من العمل مع الأرقام. كلمة "الخوارزمية" هي مجرد طريقة رائعة لقول الطريقة. لذا فإن الخوارزمية الإقليدية هي مجرد طريقة إقليدس لإيجاد أكبر القواسم المشتركة.

لوصف هذه الطريقة ، لنتذكر المصطلحات التي نستخدمها عند حل مسألة قسمة (في الحساب العادي). الرقم (المقسوم) عند قسمة الرقم الثاني (القاسم) يعطي إجابة صحيحة (حاصل القسمة) بالإضافة إلى جزء كسري (الباقي / المقسوم عليه): إذن في القسمة 25/7 لدينا: و 25 هو المقسوم ، 7 القاسم ، 3 حاصل القسمة و 4 الباقي. تتضمن طريقة إقليدس الآن إجراء سلسلة من التقسيمات. لإيجاد القاسم المشترك الأكبر لرقمين ، قسّم أولًا الأكبر على الأصغر ، واكتب المسألة على النحو الوارد أعلاه. القسمة التالية التي يجب القيام بها هي التي تحصل عليها عن طريق "قلب" الجزء الكسري من القسمة الأخيرة - وهذا هو المقسوم الجديد هو المقسوم عليه القديم والمقسوم عليه الجديد هو الباقي القديم. عندما يتم ذلك ، كرر العملية (على سبيل المثال ، اقلب الجزء الكسري الجديد للحصول على القسمة التالية). استمر في فعل هذا حتى تضطر إلى التوقف لأن الباقي يصبح 0. والباقي الأخير غير الصفري هو القاسم المشترك الأكبر للعددين الأصليين. على سبيل المثال ، دعنا نستخدم هذه الطريقة لإيجاد القاسم المشترك الأكبر للعددين 7 و 25 (والذي يمكننا رؤيته بسهولة هو 1). تم القيام بالخطوة الأولى أعلاه. التقسيم التالي هو 7/4 (قلب 4/7). هذا يعطينا 7/4 = 1 + 3/4. بعد ذلك ، 4/3 = 1 + 1/3. بعد ذلك ، 3/1 = 3 + 0 ، لذلك نتوقف هنا. الباقي الأخير غير الصفري هو 1 غامق من الخطوة التالية إلى الأخيرة ، وهذا هو القاسم المشترك الأكبر. يا له من عمل كثير للحصول على إجابة عرفناها منذ البداية! ربما يقنعك هذا المثال التالي بأن هذا قد يستحق الجهد المبذول. دعنا نستخدم طريقة إقليدس لإيجاد القاسم المشترك الأكبر بين 378 و 3465.

3465/378 = 9 + 63 /378
378/63 = 6 + 0.
إذن ، القاسم المشترك الأكبر هو 63. الآن كان هذا سهلاً!

استخدم طريقة إقليدس لإيجاد القاسم المشترك الأكبر لأزواج الأرقام هذه.

هناك شيئان يجب أن نقولهما عن هذه الطريقة. إذا لم يكن هناك باقي في الخطوة الأولى ، فإن القاسم المشترك الأكبر هو الأصغر بين العددين. الأمر الثاني هو ملاحظة أن حاصل القسمة التي تم الحصول عليها في كل خطوة قسمة لا تلعب أي دور في إيجاد القاسم المشترك الأكبر. لكن لا تتجاهلهم ، سنستخدمهم لاحقًا.

عندما نحاول إجراء قسمة حسابية على مدار الساعة ، مثل إيجاد (5 وقسمة 7) mod 25 ، فإننا نفعل ذلك على خطوتين منذ (5 & قسمة 7) mod 25 = 5 & times (1 & divide 7) mod 25. وهذا يعني أننا يمكن أولاً العثور على قيمة (1 وقسمة 7) mod 25 ثم ضربها في 5 (mod 25). في هذا المثال ، (5 & قسمة 7) تعديل 25 هو الجواب على السؤال 7 & مرات؟ = 5 تعديل 25. إذا علمنا أن (1 وقسمة 7) نموذج 25 = 18 ، فسنحصل على إجابة سؤالنا بحساب 5 مرات و 18 تعديل 25 = 90 تعديل 25 = 15. لاحظ أن 7 مرات 15 تعديل 25 = 105 mod 25 = 5 ، إذن 15 هي الإجابة الصحيحة لمسألة القسمة. هذا يعني أنه عندما نقوم بقسمة حسابية على مدار الساعة ، يمكننا دائمًا إجراء القسمة باستخدام المقسوم 1 بدلاً من العائد الفعلي ، ثم الضرب في العائد الحقيقي للمشكلة. كما سنرى ، فإن طريقتنا في القيام بهذه التقسيمات لا تصلح إلا إذا قمنا بمعالجة مشاكل القسمة بهذه الطريقة.

استخدم المعلومات المقدمة للعثور على إجابات لمشكلات القسمة هذه.

  1. (6 & قسمة 9) mod 17 ، إذا كنت تعلم أن (1 & قسمة 9) mod 17 = 2.
  2. (12 & قسمة 5) mod 24 ، إذا كنت تعلم أن (1 & قسمة 5) mod 24 = 5.
  3. (8 & قسمة 6) mod 35 ، إذا كنت تعلم أن (1 & قسمة 6) mod 35 = 6.
  • 17/9 = 1 + 8/9.
  • 9/8 = 1 + 1 /8.
  • 8/1 = 8 + 0.
  • 17 = 1 × 9 + 8 ، 8 = 17 - 1 × 9.
  • 9 = 1 × 8 + 1 ، لذا 1 = 9-1 × 8.
  • 25/7 = 3 + 4/7 === & gt 4 = 25-3 مرات 7
  • 7/4 = 1 + 3/4 === & gt 3 = 7-1 & مرات 4
  • 4/3 = 1 + 1/3 === & GT 1 = 4-1 & مرات 3
  • 3/1 = 3 + 0

استخدم هذه الطريقة للعثور على إجابات لمشاكل القسمة هذه.

  • 21/9 = 2 + 3/9 === & GT 3 = 21-2 & مرات 9
  • 9/3 = 3 + 0
  • 25/9 = 2 + 7/9 === & GT 7 = 25-2 & مرات 9
  • 9/7 = 1 + 2/7 === & gt 2 = 9-1 & مرات 7
  • 7/2 = 3 + 1/2 === & GT 1 = 7 - 3 & مرات 2

استخدم هذه الطريقة للعثور على إجابات لمشاكل القسمة هذه.

  1. (2 & قسمة 3) تعديل 5 =
  2. (5 وقسمة 3) تعديل 6 =
  3. (2 وقسمة 5) تعديل 6 =
  4. (13 & قسمة 6) تعديل 18 =
  5. (12 وقسمة 7) تعديل 25 =

في القسم التالي ، سنرى كيف يمكننا استخدام حساب الساعة (بما في ذلك القسمة) لإنشاء رسائل سرية. إجابات لأكبر أسئلة المقسومات المشتركة

  1. 1 102/25 = 4 + 2/25 25/2 = 12 + 1 /2 2/1 = 2 + 0.
  2. 9 243/198 = 1 + 45/198 198/45 = 4 + 18/45 45/18 = 2 + 9 /18 18/9 = 2 + 0.
  3. 77 7469/2464 = 3 + 77 /2464 2464/77 = 32 + 0.
  4. 1 4999/1109 = 4 + 563/1109 1109/563 = 1 + 546/563 563/546 = 1 + 17/546 546/17 = 32 + 2/17 17/2 = 8 + 1 /2 2/1 = 2 + 0.
  1. 12 منذ 6 مرات 2 تعديل 17 = 12. تحقق: 9 مرات 12 تعديل 17 = 108 تعديل 17 = 6.
  2. 12 منذ 12 مرة 5 تعديل 24 = 60 تعديل 24 = 12. تحقق: 5 مرات و 12 تعديل 24 = 60 تعديل 24 = 12.
  3. 13 منذ 8 مرات و 6 تعديل 35 = 48 تعديل 35 = 13. تحقق: 6 مرات و 13 تعديل 35 = 78 تعديل 35 = 8.

    2
    17/9 = 1 + 8/9 === & GT 8 = 17 - (1 × 9)
    9/8 = 1 + 1/8 === & GT 1 = 9 - (1 × 8)
    1 = 9 - (1 مرات (17 - (1 مرات 9))) = 9-17 + 9 = 9 مرات 2 - 17 مرات 1.

    4
    5/3 = 1 + 2/3 === & gt 2 = 5 - (1 × 3)
    3/2 = 1 + 1/2 === & GT 1 = 3 - (1 × 2)
    1 = 3 - (1 مرات (5 - (1 مرات 3))) = 3-5 + 3 = 3 مرات 2-5 مرات 1.
    لذلك ، (1 & قسمة 3) mod 5 = 2 وبالتالي (2 & divide 3) mod 5 = 2 & times 2 mod 5 = 4.


عن المؤلف

دونالد بيندر ، دكتوراه ، أستاذ مساعد في قسم الرياضيات وعلوم الكمبيوتر في جامعة ولاية ترومان.

مارتن جيه إيريكسون ، دكتوراه ، أستاذ الرياضيات في قسم علوم الكمبيوتر في جامعة ولاية ترومان ومؤلف أو شارك في تأليف العديد من الكتب حول مواضيع رياضية.

جو هيميتر ، دكتوراه ، مطور برامج مستقل وأستاذ سابق للرياضيات في كل من جامعة ديلاوير وجامعة ترومان.


أرشيف المدونة

الكسور هي أصدقاء الجميع ، أو على الأقل يمكن أن يكونوا كذلك. قد تبدو مخيفة بعض الشيء ، لكنها ليست كذلك حقًا. تُعرف الكسور على أنها كسور عشرية. تمثل الكسور (والأرقام العشرية) المسافات بين الأعداد الصحيحة (أو أرقام العد) على خط الأعداد. على سبيل المثال ، الأعداد الصحيحة هي مجموعة الأرقام السالبة والأرقام الموجبة والصفر (& # 8230-2 ، -1 ، 0 ، 1 ، 2 & # 8230) الكسور (والأرقام العشرية هي القيم بين هذه الأرقام (مثل 1.5 أو -1.5 ).

تمثل الكسور (والأرقام العشرية) كميات جزئية. فهمتك؟

تحتوي الكسور على رقمين بينهما خط بينهما. الرقم العلوي يسمى البسط ، والرقم السفلي يسمى المقام. يعني الخط الذي يفصل بينهما & # 8220 مقسومًا على. & # 8221 لذا فإن الكسور تمثل مقدارًا مقسومًا على مبلغ آخر.

على سبيل المثال ، خذ 1/2. هذا يعني واحدًا مقسومًا على اثنين.

كمثال آخر ، خذ 5/7. هذا يعني خمسة على سبعة.

يقول بعض الناس ، & # 8220 يمكنك & # 8217t القيام بذلك لأن الرقم الأول أصغر من الرقم الثاني ، & # 8221 لكن نعم يمكنك ذلك. تضيف فاصلة عشرية وبعض الأصفار وتبدأ في القسمة كالمعتاد. ثم ستحصل على رقم عشري كإجابة.

فقط إذا كان البسط أكبر من المقام ، فسينتهي بك الأمر بمبلغ أكبر من واحد.

للتوافق مع الكسور بشكل جيد ، كل ما عليك فعله هو تعلم القواعد لجميع العمليات الأربع. مستعد؟

الجمع والطرح: يجب أن تحتوي الكسور على قواسم مشتركة. إذا لم يكن هناك & # 8217t ، فيجب عليك إيجاد المضاعف المشترك الأصغر (LCM) وجعله في أقل القاسم المشترك (LCD). حول الكسور إلى كسور متكافئة باستخدام LCD بضرب كل من البسط والمقام في نفس العدد. بعد ذلك ، ما عليك سوى جمع البسط أو طرحه (تظل القواسم كما هي).

4 هو المضاعف المشترك الأصغر للعدد 4 و 2 ، لذا يمكن أن يظل الكسر الثاني كما هو ، لكن علينا ضرب الكسر الأول في 2/2 لعمل كسر مكافئ (1/2 * 2/2 = 2/4)

يمكننا الآن إضافة: 2/4 + 3/4 = 5/4 (هذا & # 8217s كسر غير فعلي لأن البسط أكبر من المقام ، لذلك نريد اختزاله باستخدام القسمة 5/4 = 1 و 1/4

ضرب: اضرب البسط في البسط والمقام بالمقام

على سبيل المثال ، 1/2 * 3/4 ​​= 3/8 سهل!

الفاصل: اضرب المقلوب (معكوس الكسر الثاني & # 8211 اقلبه رأسًا على عقب & # 8211 أسمي هذا & # 8220 keep و change و flip & # 8221 لأنك تحتفظ بالكسر الأول وتغير القسمة إلى الضرب ثم تقلب الكسر الثاني .

على سبيل المثال ، 1/2 مقسومًا على 3/4

1/2 * 4/3 = 4/6 (مما يبسط إلى 2/3)

احصل عليه؟ انظر لقد أخبرتك أنه & # 8217s ليس كل هذا السوء.

اللغة الإنجليزية: عرض يظهر الكسور. (رصيد الصورة: ويكيبيديا)

يجب التعبير عن جميع الكسور في أبسط صورة. هذا يعني قسمة كل من البسط والمقام على العامل المشترك الأكبر (GCF). في المسألة الأخيرة ، كل من 4 و 6 يقبلان القسمة على 2. لذلك ، قمنا بتبسيط 4/6 بالقسمة على 2/2 ، وحصلنا على 2/3. لا يوجد عامل آخر غير 1 يمكننا قسمة كل من 2 و 3 على ، لذلك قل أنه & # 8217s في أبسط صورة.

في مثال الإضافة ، حصلنا على كسر غير فعلي ، لذلك قسمنا 5 على 4. 4 تنقسم إلى 5 مرة واحدة مع باقي 1 ، لذلك نسميها 1 و 1/4. يسمى هذا & # 8217s عددًا كسريًا لأنه يحتوي على عدد صحيح (1) ورقم كسري (1/4). # 8217s مختلطة.

أخيرًا وليس آخرًا ، للذهاب في الاتجاه المعاكس من رقم مختلط إلى غير صحيح (وهو ما عليك القيام به عند إجراء جميع العمليات الأربع بأرقام مختلطة) ، كل ما عليك فعله هو ضرب المقام في العدد الصحيح ثم إضافة البسط. ثم عبر عن هذا المقدار في البسط واحتفظ بنفس المقام.

على سبيل المثال ، 1 و 1/4. اضرب 4 * 1 ثم أضف 1. الإجابة هي 5/4.

لا تنسى الفرق بين أ عامل (يستخدم للتبسيط) و أ مضاعف (تستخدم عند الجمع والطرح). يشير العامل إلى القسمة والمضاعف يشير إلى الضرب.


الرياضيات 321 ملاحظات الفصل

ثم ( gcd (a، b) = r_n text <،> ) الباقي الأخير غير الصفري.

مثال 3.3.7.

إليك مثال كامل يوضح كيفية تشغيل الخوارزمية للعثور على ( gcd (7592، 5913) )

وفقًا للخوارزمية الإقليدية ، فإن الباقي غير الصفري الأخير هو gcd ، وهكذا ( gcd (7592، 5913) = 73 text <.> )

مثال 3.3.8.
الاقتراح 3.3.9. ليما بيزوت.

إذا كان (a و b ) عددًا صحيحًا موجبًا ، فهناك أعداد صحيحة (s و t ) مثل (< gcd (a، b) = as + bt> )

التعريف 3.3.10.

نسمي (s و t ) في النظرية فوق (أ وب نص <.> )

مثال 3.3.11. عودة البديل.

يمكننا عكس الخوارزمية الإقليدية لإيجاد معاملات بيزوت ، وهي العملية التي سنسميها. نحل كل معادلة في الخوارزمية الإقليدية للباقي ، ونستبدل المصطلحات المتشابهة ونجمعها بشكل متكرر حتى نصل إلى gcd مكتوبًا على أنه a من العددين الأصليين ، في هذه الحالة ، (73 = 7592s + 5913t )

الاستبدال والجمع بين المصطلحات المتشابهة:

مثال 3.3.12.

عبر عن gcd 168 و 525 كمجموعة خطية من هذين الرقمين.

مثال 3.3.13.
  1. استخدم الخوارزمية الإقليدية للعثور على ( gcd (4147، 10672) text <.> )
  2. استخدم التعويض العكسي (عكس خطوات الخوارزمية الإقليدية) لكتابة القاسم المشترك الأكبر بين 4147 و 10672 كمجموعة خطية من هذه الأرقام.

تمارين 3.3.1 تمارين

ابحث عن gcd عبر الخوارزمية الإقليدية ثم استخدم الاستبدال الخلفي لكتابة gcd كمجموعة خطية من هذه الأرقام:

  1. (displaystyle gcd (36، 48))
  2. (displaystyle gcd (21، 724))
  3. (displaystyle gcd (60، 97))
  4. (displaystyle gcd (5، 26))

استخدم أي طريقة لإيجاد القاسم المشترك الأكبر للعددين 412 و 32.

( gcd (412، 32) = 4 نص <.> ) يمكننا تصحيحه كمجموعة خطية: (4 = 412 (-1) + 32 (13) )

استخدم أي طريقة لإيجاد القاسم المشترك الأكبر للعددين 780 و 150.

( gcd (780، 150) = 30 نص <.> ) يمكننا تصحيح gcd كمجموعة خطية (30 = 780 (1) + 150 (-5) )


تمثيل الأرقام بأشكال قابلة للتحلل

تعريف.

الشكل الثنائي التربيعي F(س ، ص) = فأس 2 + Bxy + ساي 2 مع معاملات عدد صحيح منطقي يسمى بدائي إذا كان القاسم المشترك الأكبر للمعاملات هو 1. العدد الصحيح ب 2 – 4تيار متردد يسمى مميز من الشكل البدائي F.

ومن ثم فإن تمييز الشكل البدائي يختلف عن محدده تيار متردد – (ب 2/4) بمعامل من -4.

من السهل ملاحظة أن أي شكل مكافئ للشكل البدائي هو أيضًا بدائي. تحت التغيير الخطي للمتغيرات مع المصفوفة ج يتم ضرب محدد الشكل التربيعي في (det ج) 2 ، وبالتالي لا يتغير إذا det ج = ± 1. وبالتالي فإن الأشكال الأولية المكافئة لها نفس المُميِّز.


أعظم العوامل المشتركة

العامل المشترك الأكبر (GCF) لرقمين هو أكبر رقم مقسوم عليهما. يطلق عليه أحيانًا القاسم المشترك الأكبر. يمكن استخدامه لتبسيط (أو تقليل) الكسور. لا تدع "الأعظم" في الاسم يخدعك - الصندوق الأخضر للمناخ ليس أكبر من أصغر الأرقام.

COMMON هو شيء مشترك أو مشترك.

العوامل هي أجزاء حقائق الضرب.

مثال:
أوجد العامل المشترك الأكبر (GCF) للعددين 6 و 10.

6 = 2 * 3 يمكنك قسمة 6 على 2 أو 3

6 = 1 * 6 يمكنك قسمة 6 على 1 أو 6

إذن 1 و 2 و 3 و 6 كلها عوامل من ستة.

10 = 2 * 5 يمكنك قسمة 10 على 2 أو على 5

10 = 1 * 10 يمكنك قسمة 10 على 1 أو على 10

إذن 1 و 2 و 5 و 10 كلها عوامل من عشرة.

يمكن قسمة كل من 6 و 10 على 1 و 2 2 أكبر من 1 ، لذا فإن 2 هي العامل المشترك الأكبر (GCF) للعددين 6 و 10.

يمكنك أيضًا استخدام طريقة التحليل الأولي للعثور على العامل المشترك الأكبر:


محتويات

تحرير التعريف

ال القاسم المشترك الأكبر (GCD) من عددين صحيحين غير صفري a و b هو أكبر عدد صحيح موجب d بحيث يكون d مقسومًا على كل من a و b أي أن هناك أعداد صحيحة e و f مثل ذلك أ = دي و ب = مدافع ، و d هو أكبر عدد صحيح من هذا القبيل. يشار إلى GCD لـ a و b بشكل عام gcd (أ, ب) . [9]

ينطبق هذا التعريف أيضًا عندما يكون أحد a و b صفرًا. في هذه الحالة ، GCD هي القيمة المطلقة للعدد الصحيح غير الصفري: gcd (أ، 0) = gcd (0 ، أ) = | أ | . هذه الحالة مهمة كخطوة إنهاء للخوارزمية الإقليدية.

لا يمكن استخدام التعريف أعلاه لتعريف gcd (0 ، 0) ، منذ 0 × ن = 0 ، وبالتالي ليس للصفر قاسم أكبر. ومع ذلك ، فإن الصفر هو القاسم الأكبر إذا أعظم يُفهم في سياق علاقة القابلية للقسمة ، لذلك يُعرّف gcd (0 ، 0) عمومًا على أنه 0. هذا يحافظ على الهويات المعتادة لـ GCD ، وعلى وجه الخصوص هوية Bézout ، أي gcd (أ, ب) يولد نفس المثل الأعلى مثل <أ, ب>. [10] [11] [12] This convention is followed by many computer algebra systems. [13] Nonetheless, some authors leave gcd(0, 0) undefined. [14]

The GCD of a and b is their greatest positive common divisor in the preorder relation of divisibility. This means that the common divisors of a and b are exactly the divisors of their GCD. This is commonly proved by using either Euclid's lemma, the fundamental theorem of arithmetic, or the Euclidean algorithm. This is the meaning of "greatest" that is used for the generalizations of the concept of GCD.

Example Edit

The number 54 can be expressed as a product of two integers in several different ways:

54 × 1 = 27 × 2 = 18 × 3 = 9 × 6.

Of these, the greatest is 6, so it is the greatest common divisor:

Computing all divisors of the two numbers in this way is usually not efficient, especially for large numbers that have many divisors. Much more efficient methods are described in § Calculation.

Coprime numbers Edit

Two numbers are called relatively prime, or coprime, if their greatest common divisor equals 1. [15] For example, 9 and 28 are relatively prime.

A geometric view Edit

For example, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24 and 60. A 24-by-60 rectangular area can thus be divided into a grid of 12-by-12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).

Reducing fractions Edit

The greatest common divisor is useful for reducing fractions to the lowest terms. [16] For example, gcd(42, 56) = 14, therefore,

Least common multiple Edit

The greatest common divisor can be used to find the least common multiple of two numbers when the greatest common divisor is known, using the relation, [1]

Using prime factorizations Edit

Greatest common divisors can be computed by determining the prime factorizations of the two numbers and comparing factors. For example, to compute gcd(48, 180), we find the prime factorizations 48 = 2 4 · 3 1 and 180 = 2 2 · 3 2 · 5 1 the GCD is then 2 min(4,2) · 3 min(1,2) · 5 min(0,1) = 2 2 · 3 1 · 5 0 = 12, as shown in the Venn diagram. The corresponding LCM is then 2 max(4,2) · 3 max(1,2) · 5 max(0,1) = 2 4 · 3 2 · 5 1 = 720.

In practice, this method is only feasible for small numbers, as computing prime factorizations takes too long.

Euclid's algorithm Edit

The method introduced by Euclid for computing greatest common divisors is based on the fact that, given two positive integers a and b such that أ & GT ب , the common divisors of a and b are the same as the common divisors of أب and b .

So, Euclid's method for computing the greatest common divisor of two positive integers consists of replacing the larger number by the difference of the numbers, and repeating this until the two numbers are equal: that is their greatest common divisor.

For example, to compute gcd(48,18) , one proceeds as follows:

This method can be very slow if one number is much larger than the other. So, the variant that follows is generally preferred.

Euclidean algorithm Edit

A more efficient method is the Euclidean algorithm, a variant in which the difference of the two numbers a and b is replaced by the remainder of the Euclidean division (also called division with remainder) of a by b .

Denoting this remainder as أ عصري ب , the algorithm replaces (أ, ب) by (ب, أ عصري ب) repeatedly until the pair is (د, 0) , where d is the greatest common divisor.

For example, to compute gcd(48,18), the computation is as follows:

This again gives gcd(48, 18) = 6 .

Lehmer's GCD algorithm Edit

Lehmer's algorithm is based on the observation that the initial quotients produced by Euclid's algorithm can be determined based on only the first few digits this is useful for numbers that are larger than a computer word. In essence, one extracts initial digits, typically forming one or two computer words, and runs Euclid's algorithms on these smaller numbers, as long as it is guaranteed that the quotients are the same with those that would be obtained with the original numbers. Those quotients are collected into a small 2-by-2 transformation matrix (that is a matrix of single-word integers), for using them all at once for reducing the original numbers [ clarification needed ]. This process is repeated until numbers are small enough that the binary algorithm (see below) is more efficient.

This algorithm improves speed, because it reduces the number of operations on very large numbers, and can use hardware arithmetic for most operations. In fact, most of the quotients are very small, so a fair number of steps of the Euclidean algorithm can be collected in a 2-by-2 matrix of single-word integers. When Lehmer's algorithm encounters a quotient that is too large, it must fall back to one iteration of Euclidean algorithm, with a Euclidean division of large numbers.

Binary GCD algorithm Edit

The binary GCD algorithm uses only subtraction and division by 2. The method is as follows: Let أ و ب be the two non-negative integers. Let the integer د be 0. There are five possibilities:

As gcd(أ, أ) = أ, the desired GCD is أ × 2 د (as أ و ب are changed in the other cases, and د records the number of times that أ و ب have been both divided by 2 in the next step, the GCD of the initial pair is the product of أ and 2 د ).

Then 2 is a common divisor. Divide both أ و ب by 2, increment د by 1 to record the number of times 2 is a common divisor and continue.

Then 2 is not a common divisor. Divide أ by 2 and continue.

Then 2 is not a common divisor. Divide ب by 2 and continue.

As gcd(أ,ب) = gcd(ب,أ), if أ & lt ب then exchange أ و ب. الرقم ج = أب is positive and smaller than أ. Any number that divides أ و ب must also divide ج so every common divisor of أ و ب is also a common divisor of ب و ج. بصورة مماثلة، أ = ب + ج and every common divisor of ب و ج is also a common divisor of أ و ب. So the two pairs (أ, ب) and (ب, ج) have the same common divisors, and thus gcd(أ,ب) = gcd(ب,ج). Moreover, as أ و ب are both odd, ج is even, the process can be continued with the pair (أ, ب) replaced by the smaller numbers (ج/2, ب) without changing the GCD.

Each of the above steps reduces at least one of أ و ب while leaving them non-negative and so can only be repeated a finite number of times. Thus eventually the process results in أ = ب, the stopping case. Then the GCD is أ × 2 د .

Example: (أ, ب, د) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) the original GCD is thus the product 6 of 2 د = 2 1 and أ= ب= 3.

The binary GCD algorithm is particularly easy to implement on binary computers. Its computational complexity is

The computational complexity is usually given in terms of the length n of the input. Here, this length is n = log ⁡ a + log ⁡ b , and the complexity is thus

Other methods Edit

إذا أ و ب are both nonzero, the greatest common divisor of أ و ب can be computed by using least common multiple (LCM) of أ و ب:

but more commonly the LCM is computed from the GCD.

which generalizes to أ و ب rational numbers or commensurable real numbers.

Keith Slavin has shown that for odd أ ≥ 1:

which is a function that can be evaluated for complex ب. [18] Wolfgang Schramm has shown that

is an entire function in the variable ب for all positive integers أ أين جد(ك) is Ramanujan's sum. [19]

Complexity Edit

The computational complexity of the computation of greatest common divisors has been widely studied. [20] If one uses the Euclidean algorithm and the elementary algorithms for multiplication and division, the computation of the greatest common divisor of two integers of at most n bits is O ( n 2 ) . ).> This means that the computation of greatest common divisor has, up to a constant factor, the same complexity as the multiplication.

However, if a fast multiplication algorithm is used, one may modify the Euclidean algorithm for improving the complexity, but the computation of a greatest common divisor becomes slower than the multiplication. More precisely, if the multiplication of two integers of n bits takes a time of تي(ن) , then the fastest known algorithm for greatest common divisor has a complexity O ( T ( n ) log ⁡ n ) . This implies that the fastest known algorithm has a complexity of O ( n ( log ⁡ n ) 2 ) . ight).>

Previous complexities are valid for the usual models of computation, specifically multitape Turing machines and random-access machines.

The computation of the greatest common divisors belongs thus to the class of problems solvable in quasilinear time. A fortiori, the corresponding decision problem belongs to the class P of problems solvable in polynomial time. The GCD problem is not known to be in NC, and so there is no known way to parallelize it efficiently nor is it known to be P-complete, which would imply that it is unlikely to be possible to efficiently parallelize GCD computation. Shallcross et al. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC-equivalent to the problem of integer linear programming with two variables if either problem is in NC or is P-complete, the other is as well. [21] Since NC contains NL, it is also unknown whether a space-efficient algorithm for computing the GCD exists, even for nondeterministic Turing machines.

Although the problem is not known to be in NC, parallel algorithms asymptotically faster than the Euclidean algorithm exist the fastest known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve the problem in ا(ن/log ن) time with ن 1+ε processors. [22] Randomized algorithms can solve the problem in ا((log ن) 2 ) time on exp ⁡ ( O ( n log ⁡ n ) ) > ight) ight)> processors [ clarification needed ] (this is superpolynomial). [23]

  • Every common divisor of أ و ب is a divisor of gcd(أ, ب) .
  • gcd(أ, ب) , where أ و ب are not both zero, may be defined alternatively and equivalently as the smallest positive integer د which can be written in the form د = أص + بف ، أين ص و ف are integers. This expression is called Bézout's identity. Numbers ص و ف like this can be computed with the extended Euclidean algorithm.
  • gcd(أ, 0) = | أ | , for أ ≠ 0 , since any number is a divisor of 0, and the greatest divisor of أ is | أ |. [3][6] This is usually used as the base case in the Euclidean algorithm.
  • إذا أ divides the product بج, and gcd(أ, ب) = د ، ومن بعد أ/د divides ج.
  • إذا م is a non-negative integer, then gcd(مأ, مب) = م⋅gcd(أ, ب) .
  • إذا م is any integer, then gcd(أ + مب, ب) = gcd(أ, ب) .
  • إذا م is a positive common divisor of أ و ب, then gcd(أ/م, ب/م) = gcd(أ, ب)/م .
  • The GCD is a multiplicative function in the following sense: if أ1 و أ2 are relatively prime, then gcd(أ1أ2, ب) = gcd(أ1, ب)⋅gcd(أ2, ب) . In particular, recalling that GCD is a positive integer valued function we obtain that gcd(أ, بج) = 1 if and only if gcd(أ, ب) = 1 and gcd(أ, ج) = 1 .
  • The GCD is a commutative function: gcd(أ, ب) = gcd(ب, أ) .
  • The GCD is an associative function: gcd(أ, gcd(ب, ج)) = gcd(gcd(أ, ب), ج) . Thus gcd(أ, ب, ج, . ) can be used to denote the GCD of multiple arguments.
  • gcd(أ, ب) is closely related to the least common multiple lcm(أ, ب) : we have gcd(أ, ب)⋅lcm(أ, ب) = | أب | .
  • The following versions of distributivity hold true: gcd(أ, lcm(ب, ج)) = lcm(gcd(أ, ب), gcd(أ, ج)) lcm(أ, gcd(ب, ج)) = gcd(lcm(أ, ب), lcm(أ, ج)) .
  • If we have the unique prime factorizations of أ = ص1ه1ص2ه2 ⋅⋅⋅ صمهم و ب = ص1F1ص2F2 ⋅⋅⋅ صمFم أين هأنا ≥ 0 و Fأنا ≥ 0 , then the GCD of أ و ب is gcd(أ,ب) = ص1 min(ه1,F1) ص2 min(ه2,F2) ⋅⋅⋅ صم min(هم,Fم) .
  • It is sometimes useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a completedistributive lattice with GCD as meet and LCM as join operation. [24] This extension of the definition is also compatible with the generalization for commutative rings given below.
  • In a Cartesian coordinate system, gcd(أ, ب) can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points (0, 0) and (أ, ب) .
  • For non-negative integers أ و ب، أين أ و ب are not both zero, provable by considering the Euclidean algorithm in base ن: [25] gcd(نأ − 1, نب − 1) = ن gcd(أ,ب) − 1 .
  • An identity involving Euler's totient function: gcd ( a , b ) = ∑ k | a and k | b φ ( k ) . >k|b>varphi (k).>

In 1972, James E. Nymann showed that ك integers, chosen independently and uniformly from <1, . ن>, are coprime with probability 1/ζ(ك) as ن goes to infinity, where ζ refers to the Riemann zeta function. [26] (See coprime for a derivation.) This result was extended in 1987 to show that the probability that ك random integers have greatest common divisor د هو د −k /ζ(ك). [27]

Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when ك = 2. In this case the probability that the GCD equals د هو د −2 /ζ(2), and since ζ(2) = π 2 /6 we have

This last summation is the harmonic series, which diverges. However, when ك ≥ 3, the expected value is well-defined, and by the above argument, it is

ل ك = 3, this is approximately equal to 1.3684. ل ك = 4, it is approximately 1.1106.

The notion of greatest common divisor can more generally be defined for elements of an arbitrary commutative ring, although in general there need not exist one for every pair of elements.

If R is a commutative ring, and a and b are in R , then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that د·x = أ و د·ذ = ب). If d is a common divisor of a and b , and every common divisor of a and b divides d , then d is called a greatest common divisor of a and ب.

With this definition, two elements a and b may very well have several greatest common divisors, or none at all. If R is an integral domain then any two GCD's of a and b must be associate elements, since by definition either one must divide the other indeed if a GCD exists, any one of its associates is a GCD as well. Existence of a GCD is not assured in arbitrary integral domains. However, if R is a unique factorization domain, then any two elements have a GCD, and more generally this is true in GCD domains. If R is a Euclidean domain in which euclidean division is given algorithmically (as is the case for instance when ص = F[X] where F is a field, or when R is the ring of Gaussian integers), then greatest common divisors can be computed using a form of the Euclidean algorithm based on the division procedure.

The following is an example of an integral domain with two elements that do not have a GCD:

The elements 2 and 1 + √ −3 are two maximal common divisors (that is, any common divisor which is a multiple of 2 is associated to 2, the same holds for 1 + √ −3 , but they are not associated, so there is no greatest common divisor of a and ب.

Corresponding to the Bézout property we may, in any commutative ring, consider the collection of elements of the form pa + qb, where p and q range over the ring. This is the ideal generated by a and b , and is denoted simply (أ, ب). In a ring all of whose ideals are principal (a principal ideal domain or PID), this ideal will be identical with the set of multiples of some ring element د then this d is a greatest common divisor of a and ب. But the ideal (أ, ب) can be useful even when there is no greatest common divisor of a and ب. (Indeed, Ernst Kummer used this ideal as a replacement for a GCD in his treatment of Fermat's Last Theorem, although he envisioned it as the set of multiples of some hypothetical, or ideal, ring element d , whence the ring-theoretic term.)


How to Find the Greatest Common Factor of Decimal Numbers?

The largest decimal that is a factor of two or more decimal points that divide evenly is known as the Greatest common factor of decimals (In short, GCF of Decimals).

To find the GCD of Decimals, you have to follow the below instructions carefully and make your Greatest common factor of decimal numbers calculations easy by hand. They are as under

  • First and foremost, you need to change the given decimal points into integers with the help of multiplication of 10, 100, 1000.
  • After that, find the decimal which is having more digits after decimal points. For suppose, it has two digits after decimal point then multiply the given numbers with 100 and convert into integers.
  • Now you have to perform finding the Greatest common factor(GCF) of the integers you get in step 1.
  • Once you find the GCF of integers then convert the result into a decimal by dividing with 100 (the number that you multiplied the given decimals in step 1).
  • Finally, you will get the Greatest Common Factor of given decimals easily by hand.

Have a look at the worked-out example presented here and understand the concept behind the Finding GCF of Decimals to get a good grip on it.

Find the GCF of 3.09 and 0.6?

Given decimals are 3.09, 0.6.

In the given decimals, the highest digits having after the decimal point is 3.09, it has two digits so we have to multiply the both given decimals ie., 3.09 and 0.6 with 100.

After multiplying by 100, we get the decimals in integers as 309 and 60

Now we need to find the GCF of 309 and 60, to get the GCF of decimals

Here we are using a common division method to find the GCF of two numbers 309, 60.

Later, convert the GCF of integer result into decimals to get the Greatest Common Factor of decimals 3.09 and 0.6

In the final step, we need to divide the GCF of 309 and 60 with 100 (which is used in converting decimals to integers in step 1)

Once you divide, GCF/100 = 3/100, we get 0.03 the greatest factor that divides given decimals exactly.


أمثلة

Greatest Common Divisors of Double Values

gcd returns positive values, even when the inputs are negative.

Greatest Common Divisors of Unsigned Integers

Solution to Diophantine Equation

Solve the Diophantine equation, 3 0 x + 5 6 y = 8 for x and y .

Find the greatest common divisor and a pair of Bézout coefficients for 30 and 56 .

u and v satisfy the Bézout's identity, (30*u) + (56*v) = g .

Rewrite Bézout's identity so that it looks more like the original equation. Do this by multiplying by 4 . Use == to verify that both sides of the equation are equal.

Calculate the values of x and y that solve the problem.


Logic and Discrete Mathematics: A Concise Introduction

This book features a unique combination of comprehensive coverage of logic with a solid exposition of the most important fields of discrete mathematics, presenting material that has been tested and refined by the authors in university courses taught over more than a decade.

The chapters on logic - propositional and first-order - provide a robust toolkit for logical reasoning, emphasizing the conceptual understanding of the language and the semantics of classical logic as well as practical applications through the easy to understand and use deductive systems of Semantic Tableaux and Resolution. The chapters on set theory, number theory, combinatorics and graph theory combine the necessary minimum of theory with numerous examples and selected applications. Written in a clear and reader-friendly style, each section ends with an extensive set of exercises, most of them provided with complete solutions which are available in the accompanying solutions manual.

  • Suitable for a variety of courses for students in both Mathematics and Computer Science.
  • Extensive, in-depth coverage of classical logic, combined with a solid exposition of a selection of the most important fields of discrete mathematics
  • Concise, clear and uncluttered presentation with numerous examples.
  • Covers some applications including cryptographic systems, discrete probability and network algorithms.

Logic and Discrete Mathematics: A Concise Introduction is aimed mainly at undergraduate courses for students in mathematics and computer science, but the book will also be a valuable resource for graduate modules and for self-study.


شاهد الفيديو: القواسم المشتركة - رياضيات الصف الخامس الفصل الثاني (شهر اكتوبر 2021).