ما هي نظرية الباقي الصينية؟
نظرية الباقي الصينية (CRT) من النتائج الكلاسيكية في نظرية الأعداد. تنص على أنه إذا كان لديك نظام من التطابقات \(x \equiv a_1 \pmod{m_1}\) و \(x \equiv a_2 \pmod{m_2}\)... وكانت المقاسات أولية فيما بينها مثنى مثنى (أي لا تشترك في أي عامل مشترك)، فإن هناك حلًّا وحيدًا فريدًا للقيمة \(x\) بالنسبة إلى المقاس \(M = m_1 \cdot m_2 \cdot \ldots\). وتجد هذه الحاسبة أصغر حل غير سالب لهذا النظام.
كيفية استخدام الحاسبة
أدخل كل باقٍ \(a_i\) مع المقاس المقابل له \(m_i\). يمكنك حل نظام مكوّن من تطابقَين أو ثلاثة — اترك حقل المقاس الثالث فارغًا إذا كنت تحتاج تطابقَين فقط. تتحقق الأداة من أن مقاساتك أولية فيما بينها مثنى مثنى، ثم تُرجِع قيمة \(x\) والمقاس المجمَّع \(M\). وكل قيمة من الشكل \(x + Mk\) (لأي عدد صحيح \(k\)) تُعدّ حلًّا صحيحًا أيضًا.
شرح الصيغة الرياضية
لِنفرض أن \(M = \prod m_i\). لكل تطابق نُعرّف \(M_i = M / m_i\) و \(y_i = M_i^{-1} \bmod m_i\) (وهو المعكوس الضربي بالنسبة للمقاس، ويُحسب باستخدام خوارزمية إقليدس الموسّعة). يكون الحل عبارة عن مجموع موزون:
$$x \equiv \sum_{i} a_i\,M_i\,y_i \pmod{M}$$وبما أن \(M_i\) قابلة للقسمة على كل المقاسات عدا \(m_i\)، فإن كل حد يساهم بالباقي الصحيح لتطابقه الخاص فقط.
مثال محلول
لنحل النظام \(x \equiv 2 \pmod{3}\) و \(x \equiv 1 \pmod{4}\). هنا \(M = 3 \cdot 4 = 12\). لدينا \(M_1 = 4\)، و \(4 \equiv 1 \pmod{3}\) إذن \(y_1 = 1\)؛ و \(M_2 = 3\)، و \(3 \equiv 3 \pmod{4}\) إذن \(y_2 = 3\) (لأن \(3 \cdot 3 = 9 \equiv 1\)). إذن $$x = 2 \cdot 4 \cdot 1 + 1 \cdot 3 \cdot 3 = 8 + 9 = 17 \equiv 5 \pmod{12}$$ 5 (mod 12). للتحقق: \(5 \bmod 3 = 2\) ✓ و \(5 \bmod 4 = 1\) ✓.
الأسئلة الشائعة
لماذا يجب أن تكون المقاسات أولية فيما بينها؟ إذا اشترك مقاسان في عامل واحد، فقد لا يكون للنظام حل على الإطلاق، أو قد تتعدّد الحلول بالنسبة إلى المضاعف المشترك الأصغر لهما، وبالتالي لا تنطبق صيغة CRT القياسية.
ماذا يعني "أصغر حل غير سالب"؟ جميع الحلول تختلف بمضاعفات \(M\)؛ وتُرجِع الحاسبة الحل الواقع في المجال من \(0\) إلى \(M-1\).
هل يمكنني استخدام بواقٍ سالبة؟ نعم. يجري اختزالها بالنسبة لكل مقاس \(m_i\) إلى المجال من \(0\) إلى \(m_i-1\) قبل الحل.
