شرح مبرهنة الباقي الصينية
عدد يترك الباقي 2 عند قسمته على 3، والباقي 3 عند قسمته على 5، والباقي 2 عند قسمته على 7. ما هذا العدد؟ جرّب الأعداد واحدًا تلو الآخر وستصل إلى 23 بعد حين، لكن السؤال يخفي مبرهنة: ما دام القواسم بلا عامل مشترك، يوجد دائمًا جواب واحد بالضبط أصغر من حاصل ضربها، ويمكن إيجاده دون تجربة أي شيء. عمر المبرهنة نحو 1500 سنة، وما زالت تعمل في التقاويم وحساب الحواسيب والتشفير الذي يحمي الويب.
مسألة من سون تزو سوان جينغ
يسأل كتاب سون تزو سوان جينغ، وهو كتاب صيني في الحساب من القرن الثالث إلى الخامس، عن عدد من الأشياء يبقى منه 2 إذا عُدّ ثلاثة ثلاثة، و3 إذا عُدّ خمسة خمسة، و2 إذا عُدّ سبعة سبعة. جوابه 23، وطريقته ما زالت تُدرَّس: خذ 70 لكل شيء يبقى عند العد ثلاثة ثلاثة، و21 لكل شيء يبقى عند العد خمسة خمسة، و15 لكل شيء يبقى عند العد سبعة سبعة، واجمع، واطرح 105 ما استطعت. 2 × 70 + 3 × 21 + 2 × 15 = 233، و233 − 2 × 105 = 23. حفظت قصيدة من عهد مينغ الأعداد 70 و21 و15 و105 في الذاكرة قرونًا. وقدّم تشين جيو شاو طريقة عامة عام 1247، وتظهر المسألة نفسها في كتاب الحساب لفيبوناتشي عام 1202، وصاغ كارل فريدريش غاوس المبرهنة بصورتها الحديثة في كتابه «بحوث حسابية» عام 1801.
ماذا تقول المبرهنة
خذ مقاييس n₁, n₂, …, nₖ لا يوجد بين أي اثنين منها عامل مشترك، وبواقي a₁, a₂, …, aₖ أيًّا كانت. عندئذ يوجد عدد صحيح واحد بالضبط x من 0 إلى N − 1، حيث N = n₁ × n₂ × … × nₖ، يترك الباقي aᵢ عند القسمة على nᵢ لكل i. وكل الحلول الأخرى تختلف عنه بمضاعف لـ N. وبلغة الحساب المعياري: للنظام x ≡ aᵢ (mod nᵢ) حل، وهو وحيد بالمقياس N. وبعبارة أخرى، يحمل العدد من 0 إلى N − 1 وقائمة بواقيه المعلومات نفسها تمامًا: 3 × 5 × 7 = 105 عددًا و3 × 5 × 7 = 105 قائمة بواقٍ ممكنة، تُستخدم كل منها مرة واحدة.
بناء الحل
الأعداد 70 و21 و15 ليست سحرًا. كل منها يترك الباقي 1 عند القسمة على مقياسه والباقي 0 عند القسمة على المقاييس الأخرى: 70 = 2 × 35 من مضاعفات 5 و7 ويترك الباقي 1 عند القسمة على 3. وفي الحالة العامة نأخذ Nᵢ = N / nᵢ، وهو من مضاعفات كل مقياس ما عدا nᵢ، ونضربه في yᵢ، معكوس Nᵢ mod nᵢ. المعكوس موجود لأن Nᵢ وnᵢ بلا عامل مشترك، وتجده خوارزمية إقليدس الموسعة: تُجري قسمات إقليدس لإيجاد القاسم المشترك الأكبر ثم ترجع إلى متطابقة بيزو 1 = s × nᵢ + t × Nᵢ، فيكون t هو المعكوس. عندئذ يناسب x = a₁N₁y₁ + a₂N₂y₂ + …، بعد اختزاله بالمقياس N، كل تطابق، لأن كل حد يناسب تطابقه ويختفي في كل التطابقات الأخرى.
تطابقًا تلو الآخر
هناك طريقة ثانية لا تحتاج إلى حاصل ضرب كل المقاييس. كل حل لـ x ≡ 2 (mod 3) على الصورة x = 2 + 3t. عوّض بذلك في التطابق التالي: 2 + 3t ≡ 3 (mod 5)، أي 3t ≡ 1 (mod 5)، والضرب في 2، معكوس 3 بالمقياس 5، يعطي t ≡ 2 (mod 5). عندئذ x = 2 + 3 × 2 = 8، ويقول التطابقان الأولان معًا إن x ≡ 8 (mod 15). كرّر ذلك مع التطابق الثالث: 8 + 15t ≡ 2 (mod 7) يعطي t ≡ 1، إذن x ≡ 23 (mod 105). يبقي هذا التعويض الأعداد أصغر، وهو الطريقة التي يحل بها الحاسوب عادة مثل هذه الأنظمة، وينجح أيضًا عندما يكون للمقاييس عامل مشترك.
مقاييس بينها عامل مشترك
إذا كان لمقياسين عامل مشترك، تداخلت تطابقاتهما: x ≡ 1 (mod 4) يقول من قبل إن x فردي، وx ≡ 4 (mod 6) يقول إن x زوجي، فلا يوجد x يحققهما معًا. وفي الحالة العامة، يمكن أن يتحقق x ≡ a (mod m) وx ≡ b (mod n) معًا إذا وفقط إذا ترك a وb الباقي نفسه عند القسمة على g = gcd(m, n)، أي إذا كان g يقسم a − b. ويكون الحل عندئذ وحيدًا بالمقياس lcm(m, n) = m × n / g لا بالمقياس m × n. وأحجية سلة البيض القديمة، التي يبقى منها 1 إذا أُخرج البيض 2 أو 3 أو 4 أو 5 أو 6 في كل مرة ولا يبقى شيء إذا أُخرج 7 في كل مرة، جوابها 301، ويتكرر كل 420 = lcm(2, 3, 4, 5, 6, 7). يكون للنظام حل إذا وفقط إذا توافق كل تطابقين فيه، لذا يحتوي النظام المستحيل دائمًا على زوج متعارض.
التقاويم والحواسيب وRSA
في عام 1583 جمع جوزيف سكاليجر ثلاث دورات تقويمية، الدورة الشمسية ومدتها 28 سنة والدورة القمرية ومدتها 19 سنة والإنديكشن ومدتها 15 سنة، في الدورة اليوليانية التي تمتد 28 × 19 × 15 = 7980 سنة. وبحسب المبرهنة لكل سنة تركيبة خاصة بها من أرقام الدورات الثلاث، وتبدأ الدورة عام 4713 قبل الميلاد، آخر سنة كانت فيها الأرقام الثلاثة كلها 1؛ وما زال علماء الفلك يعدّون الأيام اليوليانية من هناك. وتستخدم الحواسيب المبرهنة لتحسب بأعداد هائلة على شكل قوائم من بواقٍ صغيرة، يمكن جمعها وضربها كلٍّ على حدة وبالتوازي ثم ضمها في النهاية. ويعمل فك تشفير RSA بالطريقة نفسها: يُحسب c^d mod n مع n = p × q على شكل قوتين بالمقياسين p وq تجمعهما المبرهنة، أسرع بنحو أربع مرات من قوة واحدة بالمقياس n. وتخفي مخططات تقاسم الأسرار، مثل مخطط مينيوت ومخطط أسموث وبلوم، سرًّا في بواقٍ بحيث لا يكشفه إلا عدد كافٍ منها مجتمعًا.
جرّبها بنفسك
افتح الحاسبة لتكتب أي نظام تطابقات، حتى 20 تطابقًا وأعدادًا لا يزيد كل منها على 200 رقم، أو اختر أحد الأمثلة المحلولة: مسألة سون تزو، وسلة البيض، والدورة اليوليانية، وجدولي مواعيد حافلتين، وفك تشفير RSA، ونظامًا بلا حل. يُكتب الحل بأعدادك، بالبناء أو بالتعويض، مع خوارزمية إقليدس الموسعة لكل معكوس. ويضع الرسم علامة على الأعداد التي تحقق كل تطابق لترى العمود الوحيد الذي تلتقي فيه كلها، أو يرتّب بواقي تطابقين في جدول لكل عدد فيه خانته الخاصة.
الأسئلة المتداولة
هل حل نظام التطابقات وحيد؟
فقط بتقريب مضاعف للمقياس. إذا كان x = 23 حلًا لمسألة سون تزو، فإن 23 + 105 = 128 و233 و−82 حلول أيضًا، لأن إضافة 105 لا تغيّر أي باقٍ. تقول المبرهنة إن هناك حلًا واحدًا بالضبط من 0 إلى 104؛ ومع مقاييس بينها عوامل مشتركة، حلًا واحدًا بالضبط أصغر من مضاعفها المشترك الأصغر.
لماذا يجب أن تكون المقاييس أولية فيما بينها؟
في طريقة البناء، لأن Nᵢ يجب أن يكون له معكوس بالمقياس nᵢ، وهذا لا يوجد إلا إذا لم يكن بينهما عامل مشترك. وفي المبرهنة نفسها، لأن العوامل المشتركة تجعل بعض التطابقات تتداخل: فإما ألا يكون للنظام حل، وإما أن تقل حلوله المختلفة، وتتكرر الحلول كل مضاعف مشترك أصغر بدلًا من كل حاصل ضرب.
كيف أجد المعكوس المعياري يدويًا؟
بخوارزمية إقليدس الموسعة. لمعكوس 15 بالمقياس 7: 15 = 2 × 7 + 1، إذن 1 = 15 − 2 × 7، و15 × 1 ≡ 1 (mod 7): المعكوس هو 1. ولـ 35 بالمقياس 3: 35 = 11 × 3 + 2 و3 = 1 × 2 + 1، إذن 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35، ومعكوس 35 بالمقياس 3 هو −1 ≡ 2. ومع المقاييس الصغيرة يمكنك ببساطة تجربة 1 و2 و3 و… حتى يترك حاصل الضرب الباقي 1.
ما علاقة المبرهنة بالساعات؟
الباقي بالمقياس n موضع على ساعة ذات n ساعات. ساعتان بـ 3 و5 ساعات، تبدآن معًا وتتقدمان ساعة واحدة في كل مرة، تعرضان كل زوج من أزواج المواضع الخمسة عشر مرة واحدة قبل أن تعودا إلى البداية، لأن 3 و5 بلا عامل مشترك. أما الساعتان بـ 4 و6 ساعات فتعودان بعد 12 خطوة ولا تعرضان إلا 12 من الأزواج الأربعة والعشرين: موضع فردي وموضع زوجي لا يظهران معًا أبدًا.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
افتح حاسبة مبرهنة الباقي الصينية