الأعداد والحساب › Z القسمة في
القاسم المشترك الأكبر و خوارزمية إقليدس
الجواب في سطر، و بقيّة الدرس تبنيه. عدد الحاويات يجب أن يقسم عدد الطوابع المحلية و عدد الطوابع الأجنبية في آن واحد: و بما أنّ 4×18 = 72 و 4×24 = 96، فالمطلوب هو أكبر عدد يقسم 72 و 96 معا. هذا العدد له اسم — القاسم المشترك الأكبر — و له طريق قصير إليه لا يمرّ بكتابة كلّ القواسم: خوارزمية إقليدس.
- تعيين مجموعة قواسم عدد طبيعي و استخراج القواسم المشتركة لعددين
- تعريف القاسم المشترك الأكبر لعددين طبيعيين غير معدومين و حسابه في الحالات البسيطة
- البرهان على المساواة التي تربط القاسم المشترك الأكبر بباقي القسمة الإقليدية
- تطبيق خوارزمية إقليدس على عددين كبيرين و ترتيب قسماتها في جدول
- الصعود في سلسلة القسمات لكتابة القاسم المشترك الأكبر بدلالة العددين
- القسمة الإقليدية لعدد صحيح على عدد طبيعي غير معدوم
- معنى أنّ عددا صحيحا يقسم عددا صحيحا آخر
- خاصية: إذا قسم عدد عددين فإنّه يقسم كلّ مجموع من مضاعفيهما
① مجموعة قواسم عدد طبيعي
ليكن a عددا طبيعيا غير معدوم. نرمز بـ Dₐ إلى مجموعة قواسم العدد a، أي مجموعة الأعداد الطبيعية التي تقسمه. تعيينها لا يحتاج إلى أكثر ممّا تعرفه: نجرّب الأعداد الطبيعية واحدا واحدا و نحتفظ بتلك التي يكون باقي القسمة عليها معدوما.
② القاسم المشترك الأكبر لعددين طبيعيين
ليكن a و b عددين طبيعيين غير معدومين. تقاطع مجموعتي قواسمهما هو مجموعة القواسم المشتركة للعددين. هذه المجموعة ليست فارغة أبدا لأنّ العدد 1 يقسم كلّ عدد، و هي منتهية لأنّ كلّ قاسم لـ a أصغر من a أو يساويه. مجموعة منتهية و غير فارغة من الأعداد الطبيعية لها أكبر عنصر: هذا العنصر هو القاسم المشترك الأكبر للعددين.
أكبر قاسم للعدد a هو a نفسه؛ و العدد 1 ليس له سوى القاسم 1؛ و كلّ قاسم للعدد a يقسم 0، فالقواسم المشتركة للعددين 0 و a هي قواسم a، و أكبرها a.
نبقى في الأعداد الصغيرة حيث يمكن كتابة كلّ القواسم، لنرى التعريف يشتغل أمامنا قبل أن نستبدله بخوارزمية أسرع.
🎯المطلوب: عيّن مجموعة قواسم العدد 8 و مجموعة قواسم العدد 12، ثمّ استنتج قاسمهما المشترك الأكبر.
نبحث عن الأعداد التي تقسم 8 بكتابته جداء عاملين بكلّ الطرق الممكنة.
و نفعل الشيء نفسه مع العدد 12.
نجمع ما وجدناه في مجموعتين.
نحتفظ بالعناصر الموجودة في المجموعتين معا.
و نأخذ أكبر عنصر من هذا التقاطع.
③ الخاصية التي تسند الخوارزمية
كتابة كلّ القواسم طريقة صحيحة لكنّها بطيئة. الفكرة التي تغيّر كلّ شيء هي أنّ قسمة إقليدية واحدة تستبدل المسألة بمسألة أصغر منها، دون أن تغيّر الجواب.
البرهان. نبيّن أنّ للثنائيتين نفس مجموعة القواسم المشتركة؛ و إذا تساوت مجموعتان تساوى أكبر عنصر فيهما.
نفرض أنّ d يقسم a و يقسم b، فنكتب كلّا منهما جداء d في عدد صحيح. نعوّض في المساواة السابقة و نُخرج d عاملا مشتركا: يظهر أنّ d يقسم r.
و بالعكس، نفرض أنّ e يقسم b و يقسم r، و نعوّض في المساواة الأولى. يظهر أنّ e يقسم a. البرهان العكسي ضروري: لكي تتساوى مجموعتان يجب أن تُبرهن على الاحتواء في الاتجاهين.
④ خوارزمية إقليدس
ليكن a و b عددين طبيعيين غير معدومين حيث a > b. نطبّق الخاصية السابقة مرّة بعد مرّة: نقسم، ثمّ نُسقط المقسوم و نضع القاسم مكانه و الباقي مكان القاسم، و نعيد.
إذا انعدم الباقي فإنّ b يقسم a، و أكبر قاسم للعدد b هو b نفسه، فهو القاسم المشترك الأكبر للعددين.
كلّ باق أصغر تماما من القاسم الذي أنتجه، و كلّها أعداد طبيعية. فالسلسلة لا يمكن أن تطول إلى ما لا نهاية: لا بدّ أن تصل إلى الصفر.
مثال على الحالة الأولى، حيث تنتهي الخوارزمية من أوّل خطوة: نقسم 1500 على 250.
الترتيب في جدول. لتفادي الخلط بين المقسوم و القاسم و الباقي، نرتّب القسمات في جدول من ثلاثة صفوف يُقرأ من اليمين إلى اليسار: صفّ الحاصل، صفّ المقسوم و القاسم، صفّ الباقي. الجدول الموالي يبيّن هذا الترتيب على العددين 8700 و 9150.
هذان عددان لا تنفع معهما كتابة كلّ القواسم: 1631 و 932 كبيران، و لا تظهر بينهما أيّ علاقة بالنظر. ثلاث قسمات تكفي.
🎯المطلوب: عيّن القاسم المشترك الأكبر للعددين 1631 و 932 بخوارزمية إقليدس.
نقسم الأكبر على الأصغر. الحاصل 1 لأنّ 932 يدخل مرّة واحدة في 1631.
الباقي 699 غير معدوم و هو أصغر تماما من 932، فنواصل: القاسم يصير مقسوما و الباقي يصير قاسما.
نبحث عن حاصل قسمة 699 على 233: نجرّب المضاعفات.
الجداء ساوى المقسوم تماما، فالباقي معدوم و الخوارزمية تتوقّف.
آخر باق غير معدوم في السلسلة هو 233.
هذه هي الحالة الأولى من التمرين المحلول الأوّل في المنهاج: عددان كبيران متقاربان، و ثلاث قسمات فقط.
🎯المطلوب: احسب القاسم المشترك الأكبر للعددين 8700 و 9150، و رتّب القسمات في جدول.
نبدأ بالأكبر. الفرق أصغر من 8700، فالحاصل 1.
الحاصل الموالي ليس بديهيا: نؤطّر 8700 بمضاعفين متتابعين للعدد 450.
فالحاصل هو 19، و الباقي هو الفرق بين المقسوم و الجداء.
نقسم 450 على 150.
الباقي انعدم، فآخر باق غير معدوم هو 150.
هذه هي الحالة الثانية من التمرين المحلول نفسه، و هي أطول سلسلة في الدرس: سبع قسمات. اكتبها كلّها، فالتسرّع هنا هو الذي يضيّع النقطة.
🎯المطلوب: عيّن القاسم المشترك الأكبر للعددين 691 و 2007.
نقسم 2007 على 691: نؤطّر أوّلا.
فالحاصل 2 و الباقي هو الفرق.
نقسم 691 على 625: الحاصل 1.
نقسم 625 على 66: نؤطّر ثمّ نطرح.
نقسم 66 على 31.
نقسم 31 على 4: نؤطّر ثمّ نطرح.
نقسم 4 على 3.
و أخيرا نقسم 3 على 1، فينعدم الباقي.
آخر باق غير معدوم هو 1.
نعود إلى السؤال الذي فتح الدرس، و قد صار في متناولنا: عدد الحاويات يقسم 72 و يقسم 96، و نبحث عن أكبره.
🎯المطلوب: عيّن أكبر عدد من الحاويات يمكن استعماله، ثمّ عدّد كلّ التوزيعات الممكنة.
نحسب عدد الطوابع من كلّ نوع.
نقسم الأكبر على الأصغر: الفرق أصغر من 72، فالحاصل 1.
نقسم 72 على 24، فينعدم الباقي.
آخر باق غير معدوم هو 24، و هو أكبر عدد حاويات ممكن.
و القواسم المشتركة للعددين هي قواسم هذا العدد؛ نكتبها جداءات.
فالتوزيعات الممكنة بعدد قواسم 24.
⑤ الصعود في سلسلة إقليدس
إلى هنا استعملنا الخوارزمية نازلين: من العددين إلى قاسمهما المشترك الأكبر. لكنّ القسمات مكتوبة أمامنا، و كلّ واحدة منها تعطي الباقي بدلالة العددين اللذين فوقه. فإذا صعدنا فيها، معوّضين الباقي بما تعطيه القسمة السابقة، وصلنا إلى كتابة القاسم المشترك الأكبر بدلالة العددين الأوّلين. المخطّط الموالي يبيّن الحركتين.
خوارزمية إقليدس لا تعطي القاسم المشترك الأكبر فحسب. إذا صعدنا في قسماتها من الأسفل إلى الأعلى، معوّضين في كلّ مرّة الباقي بما تعطيه القسمة التي فوقه، كتبنا هذا القاسم بدلالة العددين الأوّلين.
🎯المطلوب: أوجد ثنائية (x ; y) من الأعداد الصحيحة حيث 150x + 108y = 6.
ننزل أوّلا: قسمة 150 على 108.
قسمة 108 على 42.
قسمة 42 على 24.
قسمة 24 على 18.
قسمة 18 على 6: الباقي معدوم، فالنزول انتهى.
آخر باق غير معدوم هو 6.
الآن نصعد. نقطة الانطلاق هي القسمة الرابعة، مكتوبة على شكل فرق.
العدد 18 ليس معطى: القسمة الثالثة تعطيه بدلالة 42 و 24. نعوّضه ثمّ نجمع الحدود المتشابهة.
و العدد 24 تعطيه القسمة الثانية بدلالة 108 و 42. نعوّض و ننشر: يظهر 42×4 ثمّ 42 فيجتمعان في 42×5.
و بقي 42، تعطيه القسمة الأولى بدلالة 150 و 108. نعوّض و ننشر: 108×2 و 108×5 يجتمعان في 108×7.
نتحقّق عدديا قبل أن نكتب الجواب.
و نرتّب المساواة على الصورة المطلوبة.
الصفحة 1/12
© مدرستي — هذا الدرس من تأليف مدرستي · madrassati.net