نظرية الباقي الصينية: عدد واحد يحقق باقيين

الخلاصة السريعة

في مثالنا، العدد 11 يترك باقيًا 2 عند القسمة على 3، وباقيًا 1 عند القسمة على 5. جميع الحلول هي x = 11 + 15k، حيث k عدد صحيح.

• الرمز x ≡ r (mod m) يعني أن x − r يقبل القسمة على m. نستخدم مقسومًا عليه موجبًا وباقيًا غير سالب أصغر منه. [2]
• للشرطين x ≡ 2 (mod 3) وx ≡ 1 (mod 5)، نجد 11 وحده بين 0 و 14.
• إذا كان المقسومان عليهما موجبين وقاسمهما المشترك الأكبر 1، تضمن نظرية الباقي الصينية فئة حل واحدة بترديد حاصل ضربهما. [1]
• الشرطان x ≡ 1 (mod 4) وx ≡ 3 (mod 6) متوافقان: جميع الحلول x = 9 + 12k؛ لا يكفي x = 9 + 24k.
• الشرطان x ≡ 1 (mod 4) وx ≡ 2 (mod 6) متناقضان: الأول يجعل العدد فرديًا، والثاني يجعله زوجيًا.
• في الصيغتين، k أي عدد صحيح. أعد التعويض في الشرطين، واذكر هل المطلوب جميع الحلول أم أصغر حل موجب.

اقرأ كل باقي مع مقسومه عليه

التطابق بترديد m يسجل قابلية الفرق للقسمة على m. لا يعني الرمز ≡ أن العددين متساويان. [2]

في نظامنا الأول نريد x ≡ 2 (mod 3) وx ≡ 1 (mod 5) معًا. مثلًا 11 = 3 × 3 + 2 و 11 = 5 × 2 + 1. العدد نفسه تحقق في العمليتين؛ لا تجمع الباقيين 2 و 1 لتستنتج الحل 3، لأن 3 لا يحقق أيًا من الباقيين المطلوبين.

ابحث بين مرشحي الشرط الأول

بين 0 و 14، الأعداد التي تترك باقيًا 2 عند القسمة على 3 هي 2 و 5 و 8 و 11 و 14. اختبر باقي كل منها عند القسمة على 5. الجدول يبين أن 11 هو التقاطع الوحيد؛ الصورة الرئيسية تعرض المرشحين من الشرطين في الصف نفسه من المواضع.

يمكن كتابة مرشحي الشرط الأول على الصورة x = 2 + 3t، حيث t عدد صحيح. عندما تأخذ t القيم 0 و 1 و 2 و 3 و 4، تكون بواقي x على 5 هي 2 و 0 و 3 و 1 و 4. إضافة 5 إلى t تزيد x بمقدار 15، فلا تغير أيًا من الباقيين.

حل وحيد داخل فترة، وحلول غير منتهية

عندما يكون المقسومان عليهما موجبين وأوليين نسبيًا، يوجد حل لكل زوج بواقي، وهو وحيد بترديد حاصل ضربهما؛ أي فئة واحدة، لا عدد صحيح وحيد بلا قيد. [1]

في مثالنا حاصل الضرب 15. بما أن الباقي 1 على 5 يتحقق عند t = 3 من كل خمس قيم متتابعة، فكل t المقبول يكتب t = 3 + 5k. بالتعويض نحصل على x = 11 + 15k. هذه الصيغة تشمل 11 و 26 و 41، وتشمل أيضًا −4 عند k = −1. أصغر حل موجب هنا 11، لكن −4 حل صحيح كذلك.

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

المقسومان 4 و6: التوافق ممكن

نطلب الآن x ≡ 1 (mod 4) وx ≡ 3 (mod 6). من الأول نكتب x = 1 + 4t. عند t = 0 و 1 و 2 تكون قيم x هي 1 و 5 و 9، وبواقيها على 6 هي 1 و 5 و 3. تكرار هذه الثلاثية يحصل بإضافة 3 إلى t؛ يزيد x حينها بمقدار 12.

إذن t = 2 + 3k، ومنه x = 9 + 12k لجميع الحلول. داخل 0 إلى 11 نجد 9 وحده. العدد 21 حل آخر: 21 = 4 × 5 + 1 و 21 = 6 × 3 + 3. لكنه لا يساوي 9 + 24k لأي k صحيح، لأن الفرق 12 ليس مضاعفًا للعدد 24.

في هذه الحالة نحتاج فترة 12، وهي أصغر مضاعف مشترك للعددين 4 و 6. تحقق 12 من قائمة مضاعفات كل منهما، بدل افتراض أن حاصل الضرب 24 هو أصغر فترة. صف الصورة الداخلية يبين موضع التقاطع 9.

تغيير باقي واحد قد يلغي الحل

احتفظ بالشرط x ≡ 1 (mod 4)، وغير الثاني إلى x ≡ 2 (mod 6). الأول يكتب x = 1 + 4t، وهو فردي لكل t صحيح. الثاني يكتب x = 2 + 6u، وهو زوجي لكل u صحيح. لا يكون العدد الصحيح نفسه فرديًا وزوجيًا؛ لذلك لا حل.

الصورة تقارن الشرطين خلال فترة 12: مرشحو الأول 1 و 5 و 9، ومرشحو الثاني 2 و 8؛ لا تقاطع. الحجة الفردية والزوجية تثبت التعارض لكل الأعداد الصحيحة، لا داخل الرسم وحده. لا نعرض هنا خوارزمية عامة لكل نظام غير أولي نسبيًا.

راجع الباقيين ونطاق المطلوب

ابدأ بكتابة كل باقي مع مقسومه عليه. اختبر العدد الناتج في القسمة الأولى والثانية، ثم اختبر خطوة التكرار: 15 يقبل القسمة على 3 و 5، و 12 يقبل القسمة على 4 و 6. هذا يحفظ الباقيين في نظامينا المتوافقين.

إذا طلب السؤال جميع الحلول، فاكتب الصيغة مع k عدد صحيح. وإذا طلب أصغر حل موجب، فاختره من الصيغة بدل تسمية أي حل «الأصغر». وفي نظام متناقض لا تبحث عن عدد كبير بعد فشل المرشحين: هنا يثبت تعارض الفردي والزوجي استحالة الحل.