الرياضيات🎓 هدف البكالوريا

الأعداد والحساب (تابع) مبرهنة بيزو - مبرهنة غوص

حل مسائل في الحساب: المعادلة ⁦ax + by = c⁩

🔊 المعلّمة تقرأ لك

افتح مجدولا و ابحث عن ثنائية من الأعداد الصحيحة تحقّق المعادلة ⁦6x − 8y = 9⁩. وسّع البحث كما تشاء: لن تجد ولا ثنائية واحدة. ثمّ ابحث عن حلول المعادلة ⁦5x − 8y = 3⁩، فتجد الثنائية ⁦(7;4)⁩ و بعدها ما لا نهاية من الثنائيات الأخرى. فما الذي يفصل بين معادلة لها حلول لا تُحصى و أخرى ليس لها ولا حلّ واحد؟

الجواب كلّه في القاسم المشترك الأكبر للمعاملين. في المعادلة الأولى المعاملان 6 و 8، و قاسمهما المشترك الأكبر 2، و العدد 2 لا يقسم الطرف الثاني 9: فالطرف الأيسر زوجيّ دائما و الطرف الأيمن فرديّ، و لا لقاء بينهما. و في المعادلة الثانية المعاملان 5 و 8 أوّليان فيما بينهما، فقاسمهما المشترك الأكبر 1، و 1 يقسم كلّ شيء. هذا الشرط الوحيد هو أوّل ما سنبرهن عليه، ثمّ سنتعلّم أن نحلّ فعليّا، بطريقتين.

🎓في نهاية هذا الدرس ستكون قادرا على:

معرفة الشرط الذي يجعل المعادلة ⁦ax + by = c⁩ تقبل حلولا في ℤ²، و البرهان عليه
حلّ المعادلة بطريقة الموافقات: تحويلها إلى ترديدة ذات مجهول واحد
إيجاد حلّ خاصّ بخوارزمية إقليدس صعودا، أي بتعيين معاملي بيزو
استنتاج مجموعة الحلول كاملة انطلاقا من حلّ خاصّ واحد بمبرهنة غوص
تحرير الحلّ كاملا: الاتّجاه المباشر ثمّ التحقّق العكسي، كما يُطلب في البكالوريا
معالجة تمرين بكالوريا محلول مبنيّ على المعادلة ⁦109x − 226y = 1⁩

🔑يفترض هذا الدرس أنّك تتقن:

الموافقات في ℤ و خواصّها الثماني
خوارزمية إقليدس لحساب القاسم المشترك الأكبر لعددين
مبرهنة بيزو: وجود معاملين صحيحين u و v حيث ⁦au + bv⁩ يساوي القاسم المشترك الأكبر
مبرهنة غوص و نتائجها

1. متى تقبل المعادلة حلولا؟

نعمل في المجموعة ℤ²: المجهول ثنائية ⁦(x;y)⁩ من الأعداد الصحيحة، لا من الأعداد الحقيقية. و هذا ما يغيّر كلّ شيء: في ℝ² لهذه المعادلة دائما ما لا نهاية من الحلول، لأنّها معادلة مستقيم؛ أمّا في ℤ² فالسؤال هو: هل يمرّ هذا المستقيم بنقطة إحداثياها عددان صحيحان؟

الشرط، و هو تكافؤ

⭐ احفظ هذا السطر: هو أوّل ما تكتبه أمام أيّ معادلة من هذا النوع، و هو الذي يقرّر إن كان هناك ما يُحلّ أصلا.

(∃ (x ; y) ∈ ℤ²) a x + b y = c ⟺ PGCD(a ; b) | c

aمعامل الفاصلة، عدد صحيح غير معدومbمعامل الترتيبة، عدد صحيح غير معدومcالطرف الثاني للمعادلة، عدد صحيح

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

🔹الخطوة 1: تسمية القاسم المشترك الأكبر

d = PGCD(a ; b)

🔹الخطوة 2: ما يعنيه ذلك

(d | a) ; (d | b)

🔹الخطوة 3: القاسم يقسم كلّ تركيب خطّي

إن قسم d العدد a قسم كذلك ax مهما كان x صحيحا، و كذلك في الطرف الثاني.

(d | a x) ; (d | b y)

✅النّتيجة الأولى

المجموع ⁦ax + by⁩ هو c بحكم المعادلة، إذن d يقسم c. و هذا يكفي لردّ أيّ معادلة لا تحقّق الشرط، دون أيّ حساب آخر.

d | (a x + b y) ⟹ d | c

البرهان، الاتّجاه العكسي. نفرض الآن أنّ القاسم المشترك الأكبر يقسم الطرف الثاني، و نبني حلّا صراحة. هذه الجهة هي التي ينساها التلاميذ، و هي التي تعطي الطريقة.

🔹الخطوة 1: ترجمة الفرضية

d | c ⟹ (∃ c' ∈ ℤ) c = d c'

🔹الخطوة 2: ما تعطيه مبرهنة بيزو

هذه هي الخاصية 1 من درس مبرهنة بيزو: القاسم المشترك الأكبر لعددين يكتب دائما تركيبا خطّيّا لهما.

(∃ u ∈ ℤ)(∃ v ∈ ℤ) a u + b v = d

🔹الخطوة 3: نضرب المساواة في c'

a(u c') + b(v c') = d c'

✅النّتيجة الثانية: حلّ صريح

الطرف الأيمن هو c بحكم الخطوة 1، إذن الثنائية ⁦(uc' ; vc')⁩ حلّ للمعادلة، و هي ثنائية من أعداد صحيحة. البرهان لا يكتفي بالوجود: هو يعطي الحلّ.

a(u c') + b(v c') = c

⚠️ صيغة تُكتب أحيانا في نسختين، و النسخة الواحدة تكفي: يقال «إذا كان a و b أوّليين فيما بينهما أو كان c يقبل القسمة على القاسم المشترك الأكبر». الحالة الأولى داخلة في الثانية: إن كانا أوّليين فيما بينهما فقاسمهما المشترك الأكبر 1، و 1 يقسم كلّ عدد. ⟸ اكتب شرطا واحدا: القاسم المشترك الأكبر للمعاملين يقسم الطرف الثاني.

و من المعادلة نفسها تخرج قراءتان بالموافقات، و هما مفتاح الطريقة الأولى للحلّ.

القراءة الأولى

ننقل by إلى الطرف الآخر: ⁦ax − c = −by⁩، فالفرق ⁦ax − c⁩ مضاعف للعدد b، و هذا هو معنى الترديدة بالضبط.

a x + b y = c ⟹ a x ≡ c [b]

القراءة الثانية

بنفس الحركة، و لكن بنقل ax: الفرق ⁦by − c⁩ مضاعف للعدد a.

a x + b y = c ⟹ b y ≡ c [a]

⭐ أيّ القراءتين تختار؟ القراءتان صحيحتان معا، و الفرق عمليّ فقط: عدد الحالات التي ستفحصها يساوي الترديد بالضبط. في المعادلة ⁦5x − 8y = 3⁩، القراءة الأولى ترديدها 8 و تعطيك الفاصلة بعد فحص ثماني حالات، و القراءة الثانية ترديدها 5 و تعطيك الترتيبة بعد فحص خمس حالات. ⚖️ خذ الترديد الأصغر إن كان الفارق كبيرا، ثمّ عُد إلى المجهول الآخر بالتعويض: النتيجة النهائية واحدة.

2. الطريقة الأولى: الحلّ بالموافقات

الفكرة: المعادلة فيها مجهولان، و الترديدة فيها مجهول واحد. فنحوّل المعادلة إلى ترديدة، نحلّها بفحص كلّ البواقي الممكنة — و هي قليلة جدّا — ثمّ نعود إلى المجهول الثاني بالتعويض.

مثال 1: المعادلة ⁦5x − 8y = 3⁩ بالموافقات

نعتبر في المجموعة ℤ² المعادلة ذات المجهول الثنائي المكتوبة أعلاه.

🎯المطلوب: أثبت أنّ كلّ حلول المعادلة من الشكل ⁦(8k + 7 ; 5k + 4)⁩ حيث k عدد صحيح.

📌المعطى

نتحقّق أوّلا من الشرط: المعاملان 5 و 8 أوّليان فيما بينهما.

5 x − 8 y = 3

🔹الخطوة 1: الشرط

القاسم المشترك الأكبر يساوي 1، و 1 يقسم 3، فالمعادلة تقبل حلولا.

PGCD(5 ; 8) = 1

🔹الخطوة 2: حلّ خاصّ

نتحقّق من الثنائية المقترحة في نصّ التمرين، بالحساب المباشر.

5 × 7 − 8 × 4=35 − 32=3

🔹الخطوة 3: الترتيب يهمّ

⭐ انتبه إلى الترتيب: الفاصلة 7 و الترتيبة 4. لو قلبتهما لوجدت ⁦20 − 56 = −36⁩.

5 × 4 − 8 × 7=20 − 56=−36

🔹الخطوة 4: عزل الحدّ الذي فيه x

ننقل الحدّ الذي فيه y إلى الطرف الآخر.

5 x = 3 + 8 y

🔹الخطوة 5: الانتقال إلى ترديدة

الفرق ⁦5x − 3⁩ مضاعف للعدد 8، و هذا هو تعريف الترديدة.

5 x ≡ 3 [8]

🔹الخطوة 6: الباقي الوحيد الذي يصلح

نفحص البواقي الثمانية الممكنة للفاصلة، و لا شيء غيرها.

x ≡ 7 [8]

🔹الخطوة 7: عبارة الفاصلة

نترجم الترديدة إلى كتابة صريحة، و k يمسح كلّ الأعداد الصحيحة.

x = 8 k + 7 ; k ∈ ℤ

🔹الخطوة 8: التعويض

نعوّض في المعادلة الأصلية لنستخرج الترتيبة.

5(8 k + 7) − 8 y = 3

🔹الخطوة 9: النشر

ننشر الطرف الأيسر.

40 k + 35 − 8 y = 3

🔹الخطوة 10: عزل الترتيبة

نعزل الحدّ الذي فيه y.

8 y = 40 k + 32

🔹الخطوة 11: عبارة الترتيبة

نقسم الطرفين على 8، و العددان 40 و 32 مضاعفان له.

y = 5 k + 4

🔹الخطوة 12: التحقّق العكسي

و عكسيّا: نعوّض الثنائية المحصّلة في المعادلة و ننشر.

5(8 k + 7) − 8(5 k + 4)=40 k + 35 − 40 k − 32

✅النّتيجة

الحدّان اللذان فيهما k يتلاشيان، و يبقى الطرف الثاني مهما كان k.

S = {(8 k + 7 ; 5 k + 4) , k ∈ ℤ}

⭐ الخطوة 6 هي التي يجب أن تُكتب، لا أن تُخمّن: تُنجز بجدول البواقي الذي يليها مباشرة. و التحقّق العكسي في الخطوة 12 ليس زينة: بدونه أثبتّ فقط أنّ كلّ حلّ من هذا الشكل، لا أنّ كلّ ثنائية من هذا الشكل حلّ.

الخطوة السادسة أعلاه تُنجز بجدول: نضرب في 5 كلّ باقٍ ممكن، و نقرأ أين يظهر الباقي 3.

✅النّتيجة: بواقي جداء الفاصلة في 5، بترديد 8

باقي الفاصلة	0	1	2	3	4	5	6	7
باقي جدائها في 5 بترديد 8	0	5	2	7	4	1	6	3

⭐ الباقي 3 لا يظهر إلّا في العمود الأخير، أي عندما يكون باقي الفاصلة 7 — و هو يظهر مرّة واحدة، لأنّ 5 و 8 أوّليان فيما بينهما.

⛔ الترديد يجب أن يكون المعامل الآخر، لا عددا تختاره كما تشاء. في ⁦5x − 8y = 3⁩، الترديد المشروع هو 8 (لتحصل على ترديدة في x) أو 5 (لتحصل على ترديدة في y). أيّ ترديد آخر لن يُلغي أحد المجهولين، و ستبقى بمجهولين اثنين.

مستقيم في المستوي تقع عليه نقاط إحداثياها أعداد صحيحة، متباعدة بانتظام: من كلّ نقطة ننتقل إلى التي تليها بزيادة 8 على الفاصلة و 5 على الترتيبة، و النقطة ⁦(7;4)⁩ هي الحلّ الخاصّ المحاط بدائرة. — ⭐ حلول المعادلة ليست متناثرة: هي نقاط **منتظمة التباعد** على مستقيم واحد. و العددان 8 و 5 اللذان تقفز بهما من حلّ إلى الذي يليه هما معاملا المعادلة، مقسومين على قاسمهما المشترك الأكبر.

3. ثلاث معادلات، و ثلاثة مصائر مختلفة

الكتاب يقترح ثلاث معادلات للتطبيق. لا تتشابه إلّا في الشكل: الأولى معاملاها أوّليان فيما بينهما، و الثانية لهما قاسم مشترك يقسم الطرف الثاني، و الثالثة لهما قاسم مشترك لا يقسمه.

مثال 2: معاملان أوّليان فيما بينهما

نعمل دائما في ℤ²، و المعادلة هذه المرّة مجموع لا فرق.

🎯المطلوب: حلّ في المجموعة ℤ² المعادلة ذات المجهول الثنائي المكتوبة أعلاه.

📌المعطى

نفحص الشرط قبل كلّ شيء.

7 x + 12 y = 5

🔹الخطوة 1: الشرط

القاسم المشترك الأكبر يساوي 1، و هو يقسم كلّ عدد، فالمعادلة تقبل حلولا.

PGCD(7 ; 12) = 1

🔹الخطوة 2: الانتقال إلى ترديدة

نعزل الحدّ الذي فيه x و ننتقل إلى ترديدة بترديد المعامل الآخر.

7 x ≡ 5 [12]

🔹الخطوة 3: الباقي الوحيد

نفحص البواقي الاثني عشر الممكنة، فنجد باقيا واحدا يعطي 5.

x ≡ 11 [12]

🔹الخطوة 4: عبارة الفاصلة

نترجم إلى كتابة صريحة.

x = 12 k + 11 ; k ∈ ℤ

🔹الخطوة 5: التعويض

نعوّض في المعادلة.

7(12 k + 11) + 12 y = 5

🔹الخطوة 6: النشر

ننشر.

84 k + 77 + 12 y = 5

🔹الخطوة 7: عزل الترتيبة

نعزل الحدّ الذي فيه y.

12 y = − 84 k − 72

🔹الخطوة 8: عبارة الترتيبة

نقسم على 12.

y = − 7 k − 6

🔹الخطوة 9: التحقّق العكسي

نتحقّق عكسيّا بالنشر.

7(12 k + 11) + 12(− 7 k − 6)=84 k + 77 − 84 k − 72

✅النّتيجة

مجموعة الحلول تامّة.

S = {(12 k + 11 ; − 7 k − 6) , k ∈ ℤ}

⭐ جرّب ⁦k = −1⁩: تجد الثنائية ⁦(−1 ; 1)⁩، و هي أبسط حلّ للمعادلة ⁦(7 × (−1) + 12 × 1 = 5)⁩. كتابة مجموعة الحلول ليست وحيدة: الشكل ⁦(12k − 1 ; − 7k + 1)⁩ يصف نفس المجموعة، و الجوابان صحيحان معا.

مثال 3: معاملان لهما قاسم مشترك يقسم الطرف الثاني

نعمل في ℤ²، و المعاملان هذه المرّة ليسا أوّليين فيما بينهما.

🎯المطلوب: حلّ في المجموعة ℤ² المعادلة ذات المجهول الثنائي المكتوبة أعلاه.

📌المعطى

نفحص الشرط: القاسم المشترك الأكبر ليس 1 هذه المرّة.

20 x − 45 y = 5

🔹الخطوة 1: الشرط

العدد 5 يقسم الطرف الثاني الذي هو 5 نفسه، فالمعادلة تقبل حلولا.

PGCD(20 ; 45) = 5

🔹الخطوة 2: الاختزال

⭐ الحركة الأولى: نقسم المعادلة كلّها على القاسم المشترك الأكبر.

4 x − 9 y = 1

🔹الخطوة 3: المعادلة المختزلة

المعادلة المختزلة معاملاها أوّليان فيما بينهما، و هي تكافئ الأولى تماما.

PGCD(4 ; 9) = 1

🔹الخطوة 4: الانتقال إلى ترديدة

ننتقل إلى ترديدة بترديد 9.

4 x ≡ 1 [9]

🔹الخطوة 5: الباقي الوحيد

نفحص البواقي التسعة الممكنة.

x ≡ 7 [9]

🔹الخطوة 6: عبارة الفاصلة

نترجم إلى كتابة صريحة.

x = 9 k + 7 ; k ∈ ℤ

🔹الخطوة 7: التعويض

نعوّض في المعادلة المختزلة، لا في الأصلية: الحساب أخفّ و النتيجة واحدة.

4(9 k + 7) − 9 y = 1

🔹الخطوة 8: النشر

ننشر.

36 k + 28 − 9 y = 1

🔹الخطوة 9: عبارة الترتيبة

نعزل ثمّ نقسم على 9.

y = 4 k + 3

🔹الخطوة 10: التحقّق العكسي

نتحقّق عكسيّا في المعادلة الأصلية، لا في المختزلة.

20(9 k + 7) − 45(4 k + 3)=180 k + 140 − 180 k − 135

✅النّتيجة

مجموعة الحلول تامّة.

S = {(9 k + 7 ; 4 k + 3) , k ∈ ℤ}

⛔ لا تنس الاختزال. لو انتقلت مباشرة إلى ترديدة بترديد 45 لوجدت نفسك أمام 45 حالة بدل 9، و لوجدت أنّ الترديدة ⁦20x ≡ 5 [45]⁩ لها خمسة بواقي حلّ لا واحد. الاختزال على القاسم المشترك الأكبر هو ما يعيد الوحدانية.

مثال 4: معادلة بلا حلّ، و البرهان في سطرين

نعمل في ℤ²، و ليس المطلوب هذه المرّة إيجاد الحلول بل الحكم على وجودها.

🎯المطلوب: بيّن أنّ المعادلة المكتوبة أعلاه لا تقبل أيّ حلّ في المجموعة ℤ².

📌المعطى

نفحص الشرط، و هو هنا كلّ ما يلزم.

6 x − 8 y = 9

🔹الخطوة 1: القاسم المشترك الأكبر

القاسم المشترك الأكبر للمعاملين يساوي 2.

PGCD(6 ; 8) = 2

🔹الخطوة 2: الشرط ساقط

نقسم 9 على 2: الباقي ليس معدوما، فالشرط ساقط.

9 = 2 × 4 + 1

🔹الخطوة 3: القراءة بالزوجية

⭐ و القراءة الملموسة لنفس الشيء: الطرف الأيسر يكتب دائما جداءً فيه العامل 2.

6 x − 8 y = 2(3 x − 4 y)

✅النّتيجة

فمهما كانت x و y صحيحتين، الطرف الأيسر زوجيّ و الطرف الأيمن فرديّ.

S = { }

⭐ هذا هو المثال الذي يُختبر به فهمك للشرط: لا تبدأ الحساب قبل فحصه. و الحجّة بالزوجية في الخطوة 3 هي نفس الحجّة، مكتوبة بلغة يفهمها كلّ تلميذ — احتفظ بها، فهي أسرع ما يُكتب في ورقة الامتحان.

✅النّتيجة: أربع معادلات، و الشرط وحده يفصل بينها

المعادلة	القاسم المشترك الأكبر للمعاملين	هل يقسم الطرف الثاني؟	الحلول
⁦5x − 8y = 3⁩	1	نعم	ما لا نهاية
⁦7x + 12y = 5⁩	1	نعم	ما لا نهاية
⁦20x − 45y = 5⁩	5	نعم	ما لا نهاية
⁦6x − 8y = 9⁩	2	لا	لا يوجد أيّ حلّ

⛔ لاحظ السطر الثالث: القاسم المشترك الأكبر ليس 1، و مع ذلك للمعادلة حلول. ما يهمّ ليس أن يكون المعاملان أوّليين فيما بينهما، بل أن يقسم قاسمهما المشترك الأكبر الطرف الثاني.

4. من أين يأتي الحلّ الخاصّ؟ معاملا بيزو

في كلّ ما سبق كان الحلّ الخاصّ يُعطى أو يُقرأ بالبواقي. لكن أمام معاملين كبيرين، فحص البواقي يصير طويلا: ترديد من رتبة المئتين يعني مئتي حالة. الطريقة الثانية تعطي حلّا خاصّا بحساب مباشر، و أداتها خوارزمية إقليدس مقروءة صعودا.

نعتبر عددين طبيعيّين a و b حيث a أكبر تماما من b و b غير معدوم، و نكتب سلسلة القسمات الإقليدية المتتابعة: نقسم a على b، ثمّ b على الباقي، ثمّ كلّ باقٍ على الذي يليه.

القسمة الأولى

a = q₁ b + r₁

القسمة الثانية

b = q₂ r₁ + r₂

القسمة الثالثة

r₁ = q₃ r₂ + r₃

القسمة العامّة

⚠️ دليل الحاصل يتحرّك مع رتبة القسمة: لكلّ قسمة حاصلها الخاصّ بها. لو كان الحاصل واحدا في كلّ السطور لتساوت كلّ الحواصل، و هو ما لا يقع: في المثال العددي الموالي تجدها 1 ثمّ 1 ثمّ 14 ثمّ 2 ثمّ 2، و هي ليست كلّها متساوية.

r_n=q_n+2 r_n+1 + r_n+2

الفكرة الآن: نكتب كلّ باقٍ تركيبا خطّيّا للعددين a و b، و نتتبّع المعاملين خطوة خطوة. نسمّيهما uₙ و vₙ. و البداية بديهية.

البداية: العدد الأوّل بدلالة نفسه

a=1 × a + 0 × b

البداية: العدد الثاني بدلالة نفسه

b=0 × a + 1 × b

الثنائيتان الأوليان

(u₀ ; v₀) = (1 ; 0) ; (u₁ ; v₁) = (0 ; 1)

الباقي الأوّل بدلالة العددين

نقرأ القسمة الأولى بالعكس: الباقي هو المقسوم ناقص الحاصل في القاسم.

r₁ = a − q₁ b

الثنائية الثالثة

(u₂ ; v₂) = (1 ; − q₁)

الباقي الثاني بدلالة العددين

r₂ = b − q₂ r₁

الثنائية الرابعة

نعوّض r₁ بعبارته: ⁦b − q₂(a − q₁b) = − q₂ a + (1 + q₁q₂) b⁩.

(u₃ ; v₃) = (− q₂ ; 1 + q₁ q₂)

الثنائية الخامسة

(u₄ ; v₄) = (1 + q₂ q₃ ; − q₁ − q₃(1 + q₁ q₂))

نلاحظ في الثنائيات الأربع قانونا واحدا يتكرّر، و هو الذي يُطلب تخمينه ثمّ البرهان عليه.

قانون التراجع على المعامل الأوّل

u_n+1 = u_n−1 − q_n u_n

قانون التراجع على المعامل الثاني

⭐ نفس القانون بالضبط للمعاملين: هو ينسخ حرفيّا العلاقة بين البواقي، التي كتبناها في القسمة العامّة أعلاه. كلّ باقٍ يُكتب تركيبا خطّيّا للعددين، فتنتقل العلاقة من البواقي إلى المعاملات بالتطابق.

v_n+1 = v_n−1 − q_n v_n

مثال 5: معاملا بيزو للعددين 745 و 385

ليكن العددان 745 و 385. نريد كتابة قاسمهما المشترك الأكبر تركيبا خطّيّا لهما.

🎯المطلوب: عيّن عددين صحيحين u و v حيث يكون المجموع ⁦745u + 385v⁩ مساويا للقاسم المشترك الأكبر.

📌المعطى

نبدأ بخوارزمية إقليدس: نقسم الأكبر على الأصغر.

a = 745 ; b = 385

🔹الخطوة 1: القسمة الأولى

القسمة الأولى: الحاصل 1 و الباقي 360.

745 = 1 × 385 + 360

🔹الخطوة 2: القسمة الثانية

نقسم القاسم على الباقي.

385 = 1 × 360 + 25

🔹الخطوة 3: القسمة الثالثة

و هكذا، كلّ مرّة نقسم الباقي السابق على الباقي الجديد.

360 = 14 × 25 + 10

🔹الخطوة 4: القسمة الرابعة

القسمة الرابعة.

25 = 2 × 10 + 5

🔹الخطوة 5: القسمة الخامسة

القسمة الخامسة: الباقي ينعدم، فنتوقّف.

10 = 2 × 5 + 0

🔹الخطوة 6: القاسم المشترك الأكبر

آخر باقٍ غير معدوم هو القاسم المشترك الأكبر — و هذه هي خوارزمية إقليدس.

PGCD(745 ; 385) = 5

🔹الخطوة 7: الحواصل

الحواصل الخمسة، بالترتيب، هي ما سيغذّي قانون التراجع.

(q₁ ; q₂ ; q₃ ; q₄ ; q₅) = (1 ; 1 ; 14 ; 2 ; 2)

🔹الخطوة 8: المعاملات الأولى

نطبّق القانون على المعامل الأوّل، رتبة بعد رتبة، انطلاقا من 1 و 0.

u₂=u₀ − q₁ u₁=1 − 1 × 0=1

🔹الخطوة 9: الرتبة الثالثة

الرتبة الموالية.

u₃=u₁ − q₂ u₂=0 − 1 × 1=− 1

🔹الخطوة 10: الرتبة الرابعة

الرتبة الموالية، و هنا يدخل الحاصل الكبير 14.

u₄=u₂ − q₃ u₃=1 − 14 × (− 1)=15

🔹الخطوة 11: الرتبة الخامسة

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

u₅=u₃ − q₄ u₄=− 1 − 2 × 15=− 31

🔹الخطوة 12: المعامل الثاني عند الرتبة الخامسة

نفعل الشيء نفسه على المعامل الثاني، انطلاقا من 0 و 1.

v₅=v₃ − q₄ v₄=2 − 2 × (− 29)=60

🔹الخطوة 13: التحقّق

نتحقّق: الجداءان متقاربان جدّا و فرقهما هو القاسم المشترك الأكبر.

(− 31) × 745 = − 23095 ; 60 × 385 = 23100

✅النّتيجة

و هذه هي مساواة بيزو للعددين 745 و 385.

(− 31) × 745 + 60 × 385=5

⭐ رتّب حسابك في جدول عموديّ، كما في الجدول الموالي: عمود للبواقي، عمود للحواصل، ثمّ عمودان للمعاملين. هكذا لا تخطئ في الرتب، و هو الخطأ الأوّل في هذا التمرين.

✅النّتيجة: خوارزمية إقليدس و معاملا بيزو، في جدول واحد

الرتبة	0	1	2	3	4	5	6
الباقي	745	385	360	25	10	5	0
الحاصل	—	1	1	14	2	2	—
المعامل الأوّل	1	0	1	⁦−1⁩	15	⁦−31⁩	77
المعامل الثاني	0	1	⁦−1⁩	2	⁦−29⁩	60	⁦−149⁩
التركيب الخطّي	745	385	360	25	10	5	0

⭐ السطر الأخير محسوب من السطرين اللذين قبله: هو حاصل 745 × المعامل الأوّل زائد 385 × المعامل الثاني، و هو يعيد السطر الأوّل بالضبط. العمود الذي فيه الباقي 5 يحمل معاملي بيزو المطلوبين.

⚠️ السطر الأخير من الجدول هو تحقّقك الذاتي: إن لم يعد إليك سطر البواقي، فقد أخطأت في رتبة ما. ⛔ و لاحظ الرتبة السادسة: الباقي فيها معدوم، فهي لا تعطي معاملي بيزو — المعاملان المطلوبان هما اللذان في عمود آخر باقٍ غير معدوم.

⭐ و بمعاملي بيزو تحلّ أيّ معادلة: إن كان ⁦PGCD(a ; b) = d⁩ و كان ⁦c = d c'⁩، فاضرب مساواة بيزو ⁦au + bv = d⁩ في c'، فتحصل مباشرة على الحلّ الخاصّ ⁦(uc' ; vc')⁩. ⚖️ لا حاجة بعدها إلى فحص أيّ باقٍ.

5. تمرين بكالوريا: المعادلة ⁦109x − 226y = 1⁩

ننهي الدرس بتمرين من البكالوريا، و هو النموذج الكامل: شرط الوجود، حلّ خاصّ، مجموعة الحلول بمبرهنة غوص، ثمّ استعمال هذه المجموعة في سؤال آخر تماما. و هو يجمع كلّ ما في هذا المحور.

مثال 6: مجموعة حلول المعادلة ⁦109x − 226y = 1⁩

نعتبر في ℤ² المعادلة ⁦(E)⁩ المكتوبة أعلاه، و هي معادلة تمرين بكالوريا.

🎯المطلوب: عيّن القاسم المشترك الأكبر للعددين 109 و 226، ثمّ برهن أنّ مجموعة حلول المعادلة هي مجموعة الثنائيات من الشكل ⁦(226k + 141 ; 109k + 68)⁩.

📌المعطى

نبدأ بخوارزمية إقليدس على المعاملين.

109 x − 226 y = 1

🔹الخطوة 1: القسمة الأولى

القسمة الأولى.

226 = 2 × 109 + 8

🔹الخطوة 2: القسمة الثانية

القسمة الثانية.

109 = 13 × 8 + 5

🔹الخطوة 3: القسمة الثالثة

القسمة الثالثة.

8 = 1 × 5 + 3

🔹الخطوة 4: القسمة الرابعة

القسمة الرابعة.

5 = 1 × 3 + 2

🔹الخطوة 5: القسمة الخامسة

القسمة الخامسة.

3 = 1 × 2 + 1

🔹الخطوة 6: القاسم المشترك الأكبر

القسمة السادسة: الباقي ينعدم، و آخر باقٍ غير معدوم هو 1.

PGCD(226 ; 109) = 1

🔹الخطوة 7: وجود الحلول

الشرط محقّق: 1 يقسم الطرف الثاني، فللمعادلة حلول — و هذه هي مبرهنة بيزو.

PGCD(226 ; 109) = 1 ⟹ S ≠ { }

🔹الخطوة 8: الصعود، السطر الأوّل

⭐ نصعد الآن في السلسلة: نبدأ من القسمة الخامسة و نعوّض كلّ باقٍ بعبارته.

1 = 3 − 2

🔹الخطوة 9: الصعود، السطر الثاني

نعوّض 2 بعبارته المستخرجة من القسمة الرابعة.

1=3 − (5 − 3)=2 × 3 − 5

🔹الخطوة 10: الصعود، السطر الثالث

نعوّض 3 بعبارته المستخرجة من القسمة الثالثة.

1=2(8 − 5) − 5=2 × 8 − 3 × 5

🔹الخطوة 11: الصعود، السطر الرابع

نعوّض 5 بعبارته المستخرجة من القسمة الثانية.

1=2 × 8 − 3(109 − 13 × 8)=41 × 8 − 3 × 109

🔹الخطوة 12: الصعود، السطر الأخير

نعوّض 8 بعبارته المستخرجة من القسمة الأولى: انتهى الصعود.

1=41(226 − 2 × 109) − 3 × 109=41 × 226 − 85 × 109

🔹الخطوة 13: حلّ خاصّ

نرتّب المساواة على شكل المعادلة المطروحة.

109 × (− 85) − 226 × (− 41)=1

🔹الخطوة 14: حلّ خاصّ آخر

⚖️ الكتاب يقترح حلّا خاصّا آخر، أبسط في الكتابة، و نتحقّق منه.

109 × 141 = 15369 ; 226 × 68 = 15368

🔹الخطوة 15: التحقّق

الفرق بين الجداءين يساوي 1 بالضبط.

109 × 141 − 226 × 68=1

🔹الخطوة 16: تجميع الحدود

نطرح المساواتين طرفا بطرف، فيختفي الطرف الثاني.

109(x − 141) = 226(y − 68)

🔹الخطوة 17: قاسم ظاهر

العدد 226 يقسم الطرف الأيمن، إذن يقسم الطرف الأيسر.

226 | 109(x − 141)

🔹الخطوة 18: تطبيق غوص

⭐ الشرط محقّق، فمبرهنة غوص تمرّ القسمة إلى العامل الآخر.

(226 | 109(x − 141) ; PGCD(226 ; 109) = 1) ⟹ 226 | (x − 141)

🔹الخطوة 19: عبارة الفاصلة

نترجم القسمة إلى كتابة.

x = 226 k + 141 ; k ∈ ℤ

🔹الخطوة 20: عبارة الترتيبة

نعوّض في مساواة الخطوة 16 ثمّ نقسم على 226.

y = 109 k + 68

🔹الخطوة 21: التحقّق العكسي

التحقّق العكسي بالنشر: الحدّان اللذان فيهما k يتلاشيان.

109(226 k + 141) − 226(109 k + 68)=1

✅النّتيجة

مجموعة الحلول تامّة.

S = {(226 k + 141 ; 109 k + 68) , k ∈ ℤ}

⭐ الحلّان الخاصّان اللذان وجدتهما هما في نفس المجموعة: خذ ⁦k = −1⁩ في الصيغة النهائية، تجد الفاصلة ⁦−85⁩ و الترتيبة ⁦−41⁩، أي بالضبط ما أعطاه الصعود في خوارزمية إقليدس. ⚖️ فالحلّ الخاصّ ليس وحيدا، و اختيار أحدهما لا يغيّر مجموعة الحلول.

و ماذا نفعل بهذه المجموعة؟

سؤال التمرين الموالي يبيّن لماذا تُطلب المجموعة كاملة: يُبحث فيها عن حلّ يحقّق شرطا إضافيّا، و الشرط يعيّن قيمة واحدة للعدد k.

🔹الخطوة 1: إعادة كتابة الشرط المطروح

ننقل الحدّ 226e إلى الطرف الآخر: صار الشرط هو المعادلة نفسها، بمجهولين سمّيناهما هذه المرّة d و e.

109 d = 1 + 226 e ⟺ 109 d − 226 e = 1

🔹الخطوة 2: قراءة الحلول

d = 226 k + 141 ; e = 109 k + 68

🔹الخطوة 3: ترجمة الحصر المطلوب

0 < 226 k + 141 ≤ 226

🔹الخطوة 4: حلّ الحصر

− 141 < 226 k ≤ 85

✅النّتيجة: قيمة وحيدة

القيمة ⁦k = 0⁩ هي الوحيدة التي تحقّق الحصر بين الأعداد الصحيحة، لأنّ 226 أكبر من 85 و أكبر من 141. ⟹ الثنائية ⁦(d ; e)⁩ وحيدة، و هو ما كان مطلوبا.

k = 0 ⟹ d = 141 ; e = 68

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

🔹الخطوة 1: الجذر

15² = 225 ; 16² = 256

🔹الخطوة 2: حصر الجذر

نحصر العدد بين مربّعين تامّين متتاليين، فنعرف الأعداد الأولية التي يجب فحصها: هي الأصغر من 16.

15 < √227 < 16

🔹الخطوة 3: الأعداد الأولية التي تُفحص

p ∈ {2 ; 3 ; 5 ; 7 ; 11 ; 13}

✅النّتيجة: لا باقي معدوم، إذن 227 عدد أوّلي

القاسم الأوّلي المفحوص	2	3	5	7	11	13
باقي قسمة 227 عليه	1	2	2	3	7	6

⭐ يكفي فحص الأعداد الأولية الأصغر من جذر العدد: لو كان للعدد قاسم أوّلي أكبر من جذره لكان له قاسم آخر أصغر منه، و هو ما فحصناه.

⛔ تنبيه الكتاب نفسه في هامش هذا التمرين: «المطلوب البرهان على أنّ العدد أوّلي، و بالتالي برنامج الحاسبة غير كافٍ». الحاسبة تعطي جوابا، لا برهانا: البرهان هو الجدول أعلاه، مكتوبا كاملا.

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

المبرهنة الصغيرة لفيرما، حيث p عدد أوّلي

بعبارة الموافقات: إن كان p أوّليّا و لم يقسم a، فإنّ a مرفوعا إلى الأسّ ⁦p − 1⁩ يوافق 1 بترديد p.

p ∤ a ⟹ p | (a^p−1 − 1)

تطبيقها على العدد الأوّلي 227

العدد 227 أوّلي، فهو أوّلي مع كلّ عدد أصغر منه تماما و غير معدوم، أي لا يقسمه. و ⁦227 − 1 = 226⁩، و هو الأسّ الذي ظهر في المعادلة منذ البداية — و ليست هذه مصادفة.

(0 < a < 227) ⟹ a²²⁶ ≡ 1 [227]

🔹الخطوة: العدد الذي بنيناه

109 × 141 = 1 + 226 × 68

✅النّتيجة: الرفع إلى الأسّين يعيد العدد

⭐ نعوّض الأسّ بكتابته: a مرفوعا إلى ⁦1 + 226 × 68⁩ هو a في (a مرفوعا إلى 226) مرفوعا إلى 68. و القوس الداخلي يوافق 1، فيبقى a. العددان 109 و 141 يعكس أحدهما مفعول الآخر، و هذا هو مبدأ التشفير بمفتاحين.

a^{109 × 141} = a × (a²²⁶)⁶⁸ ≡ a [227]

خذ العدد 2. باقي قسمة 2 مرفوعا إلى الأسّ 109 على 227 يساوي 156. ثمّ خذ 156 و ارفعه إلى الأسّ 141: باقي قسمته على 227 يعود إلى 2 بالضبط. الرقم شُفّر ثمّ فُكّ تشفيره.

التشفير

2¹⁰⁹ ≡ 156 [227]

✅النّتيجة: فكّ التشفير

156¹⁴¹ ≡ 2 [227]

⛔ أمام معادلة ⁦ax + by = c⁩ في البكالوريا، الترتيب مفروض و النقاط موزّعة عليه: ① احسب ⁦PGCD(a ; b)⁩ و قل إن كان يقسم c — بدون هذا السطر لا تُحسب البقيّة؛ ② أعطِ حلّا خاصّا، إمّا بالقراءة إن كانت الأعداد صغيرة، و إمّا بخوارزمية إقليدس صعودا؛ ③ اطرح المساواتين و طبّق مبرهنة غوص مع ذكر شرطها؛ ④ أنهِ بالتحقّق العكسي المكتوب. ⚖️ و إن طُلب حلّ يحقّق حصرا، فاكتب الحصر على k و حلّه في ℤ: هذه هي النقطة الأخيرة، و أكثر ما يُنسى.

الخلاصة: المعادلة ⁦ax + by = c⁩ تقبل حلولا في ℤ² إذا و فقط إذا كان ⁦PGCD(a ; b)⁩ يقسم c — و هذا السطر وحده يردّ معادلات كاملة مثل ⁦6x − 8y = 9⁩. و متى وُجد الحلّ، فالطريق واحد: حلّ خاصّ واحد، بالموافقات إن كانت الأعداد صغيرة أو بخوارزمية إقليدس صعودا إن كانت كبيرة، ثمّ طرح المساواتين، ثمّ مبرهنة غوص التي تعطي قسمة الفاصلة، ثمّ التعويض و التحقّق العكسي. الحلول ليست متناثرة: هي متتالية حسابية من الثنائيات، تقفز من واحدة إلى التي تليها بالمعاملين مقسومين على قاسمهما المشترك الأكبر.

الصفحة 1/10

📍 خلال السنة

🟦 ف1 · 🟩 ف2 · 🟪 ف3 · 📝 امتحانات الأسابيع 14/27/36 · 🎓 بكالوريا

📌 لتتذكّر

الخلاصة: المعادلة ⁦ax + by = c⁩ تقبل حلولا في ℤ² إذا و فقط إذا كان ⁦PGCD(a ; b)⁩ يقسم c — و هذا السطر وحده يردّ معادلات كاملة مثل ⁦6x − 8y = 9⁩. و متى وُجد الحلّ، فالطريق واحد: حلّ خاصّ واحد، بالموافقات إن كانت الأعداد صغيرة أو بخوارزمية إقليدس صعودا إن كانت كبيرة، ثمّ طرح المساواتين، ثمّ مبرهنة غوص التي تعطي قسمة الفاصلة، ثمّ التعويض و التحقّق العكسي. الحلول ليست متناثرة: هي متتالية حسابية من الثنائيات، تقفز من واحدة إلى التي تليها بالمعاملين مقسومين على قاسمهما المشترك الأكبر.

الشرط، و هو تكافؤ

(∃ (x ; y) ∈ ℤ²) a x + b y = c ⟺ PGCD(a ; b) | c

aمعامل الفاصلة، عدد صحيح غير معدومbمعامل الترتيبة، عدد صحيح غير معدومcالطرف الثاني للمعادلة، عدد صحيح

القراءة الأولى

a x + b y = c ⟹ a x ≡ c [b]

القراءة الثانية

a x + b y = c ⟹ b y ≡ c [a]

القسمة الأولى

a = q₁ b + r₁

القسمة الثانية

b = q₂ r₁ + r₂

القسمة الثالثة

r₁ = q₃ r₂ + r₃

القسمة العامّة

r_n = q_n+2 r_n+1 + r_n+2

البداية: العدد الأوّل بدلالة نفسه

a = 1 × a + 0 × b