ماذا تحسب حاسبة نظرية الباقي الصيني؟

تحل هذه الحاسبة نظام تطابقات من الشكل x ≡ aᵢ (mod mᵢ)، ثم تعرض النتيجة في الصورة x ≡ r (mod M). وتمثل عائلة الحلول بالصورة x = r + k × M حيث k عدد صحيح.

ليست الحاسبة محصورة في الحالة الكلاسيكية التي تكون فيها كل المعاملات متباينة نسبياً اثنين باثنين. فهي تستخدم خوارزمية عامة تدمج التطابقات زوجياً، وتتعامل مع المعاملات غير المتباينة نسبياً إذا كان النظام متوافقاً.

ما هي نظرية الباقي الصيني؟

نظرية الباقي الصيني طريقة في نظرية الأعداد تجمع عدة شروط على بواقي عدد واحد إلى تطابق واحد يصف كل الحلول الممكنة.

مثلًا النظام x ≡ 2 (mod 3) وx ≡ 3 (mod 5) يعطي x ≡ 8 (mod 15). هذا يعني أن 8 و23 و38 وكل عدد يختلف عنها بمضاعف 15 يحقق الشرطين معاً.

• الباقي aᵢ: ما يتبقى من x عند القسمة على mᵢ.
• المعامل mᵢ: أساس التطابق أو القسمة المعيارية؛ ويجب أن يكون 2 أو أكبر في هذه الحاسبة.
• عائلة الحلول: النتيجة لا تمثل عدداً واحداً فقط، بل كل الأعداد التي تختلف بمضاعفات M.
• التوافق: عند وجود قاسم مشترك بين معاملين، يجب أن يقسم هذا القاسم فرق الباقيين.

الفرق بين CRT الكلاسيكي وCRT العام

الصياغة الكلاسيكية من نظرية الباقي الصيني تفترض عادة أن المعاملات متباينة نسبياً اثنين باثنين. أما الطريقة العامة فتفحص أيضاً الأنظمة التي تشترك معاملاتها في قواسم.

في المثال x ≡ 1 (mod 6) وx ≡ 3 (mod 8)، المعاملان 6 و8 ليسا متباينين نسبياً لأن gcd(6, 8) = 2. لكن فرق الباقيين هو 2، وهو قابل للقسمة على 2، لذلك يوجد حل وتكون النتيجة x ≡ 19 (mod 24).

كيف تتم خطوات الحساب؟

تدمج الحاسبة التطابقات زوجاً بعد زوج. في كل خطوة تتحقق من شرط التوافق، ثم تستخدم خوارزمية إقليدس الموسعة عند الحاجة، وتنتج تطابقاً موحداً جديداً.

1. تُطبّع البواقي أولاً بطريقة mod أوقليدية، لذلك تتحول البواقي السالبة إلى ممثل قياسي بين 0 وm − 1.
2. لزوج من التطابقات تحسب الحاسبة g = gcd(m1, m2) وdiff = a2 − a1.
3. إذا لم يكن diff قابلاً للقسمة على g فلا يوجد حل في تلك الخطوة.
4. إذا كان النظام متوافقاً، تُستخدم المعكوسات المعيارية الناتجة من خوارزمية إقليدس الموسعة.
5. ينتج معامل موحد جديد M = lcm(m1, m2) وباقٍ موحد r.

كل الحسابات هنا حسابات أعداد صحيحة. لذلك تقبل الحاسبة بواقي ومعاملات صحيحة فقط، ولا تقبل الأعداد العشرية أو الصيغ الرمزية.

كيف تتعامل الحاسبة مع البواقي السالبة؟

تقبل الحاسبة البواقي السالبة وتحوّلها تلقائياً إلى باقي مكافئ داخل نفس المعامل. هذا التحويل لا يغيّر الشرط الرياضي، بل يكتبه بصورة معيارية أوضح.

مثلًا x ≡ −1 (mod 5) يكافئ x ≡ 4 (mod 5). لذلك تعرض الحاسبة ملاحظة تطبيع عندما يتغير الباقي المدخل بهذه الطريقة.

مثال 1: معاملات متباينة نسبياً

النظام x ≡ 2 (mod 3) وx ≡ 3 (mod 5) مثال كلاسيكي لأن 3 و5 متباينان نسبياً.

1. الشرط الأول يعني أن x يعطي باقي 2 عند القسمة على 3.
2. الشرط الثاني يعني أن x يعطي باقي 3 عند القسمة على 5.
3. أصغر ممثل غير سالب يحقق الشرطين هو 8.
4. النتيجة: x ≡ 8 (mod 15).
5. عائلة الحلول: x = 8 + k × 15 حيث k عدد صحيح.

مثال 2: معاملات غير متباينة نسبياً لكنها متوافقة

النظام x ≡ 1 (mod 6) وx ≡ 3 (mod 8) ليس من الحالة الكلاسيكية البسيطة، لكنه يملك حلاً.

1. gcd(6, 8) = 2.
2. فرق الباقيين هو 3 − 1 = 2.
3. بما أن 2 يقسم 2، فالتطابقان متوافقان.
4. تعطي الحاسبة النتيجة x ≡ 19 (mod 24).

هذا المثال يوضح فائدة الخوارزمية العامة: وجود قاسم مشترك بين المعاملات لا يعني وحده أن الحل مستحيل.

مثال 3: حالة لا يوجد فيها حل

النظام x ≡ 1 (mod 6) وx ≡ 2 (mod 4) لا يملك حلاً لأن شرط التوافق لا يتحقق.

1. gcd(6, 4) = 2.
2. فرق الباقيين هو 2 − 1 = 1.
3. العدد 1 لا يقبل القسمة على 2.
4. لذلك لا يوجد عدد صحيح يحقق الشرطين في الوقت نفسه.

طريقة استخدام الحاسبة

أدخل في كل سطر باقيًا ومعاملًا. تبدأ الحاسبة بسطرين، ويمكنك إضافة أسطر حتى أربعة تطابقات كحد أقصى.

• استخدم خانة الباقي aᵢ لكتابة باقي صحيح، ويمكن أن يكون سالباً.
• استخدم خانة المعامل mᵢ لعدد صحيح لا يقل عن 2.
• لا تستخدم الكسور أو الأعداد العشرية أو التعابير الجبرية.
• إذا كان الباقي خارج المجال المعتاد، تطبّعه الحاسبة قبل الحل.
• إذا كان النظام غير متوافق، تعرض الحاسبة خطوة الدمج التي سببت عدم وجود حل.

أين تُستخدم نظرية الباقي الصيني؟

تُستخدم نظرية الباقي الصيني في نظرية الأعداد، والحساب المعياري، وبعض مسائل البرمجة التنافسية والخوارزميات.

• في الرياضيات الجامعية تُستخدم لحل أنظمة التطابقات.
• في البرمجة التنافسية تظهر في المسائل التي تجمع عدة شروط معيارية.
• في الحساب المعياري تربط بين gcd وlcm والمعكوس المعياري.
• في الشرح التعليمي تساعد على رؤية كيف تتحول عدة شروط إلى تطابق واحد.

أخطاء شائعة

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

• اعتبار x ≡ r (mod M) عدداً واحداً فقط، مع أنه يمثل عائلة حلول كاملة.
• رفض الباقي السالب بدل تطبيعه إلى باقي مكافئ.
• إدخال معامل 0 أو 1، مع أن الحاسبة تشترط m ≥ 2.
• توقع حل تطابقات رمزية أو كثيرة حدود من أداة رقمية.
• القول إن الحل فريد دائماً دون إضافة عبارة “بترديد M” أو “mod M”.

حدود هذه الحاسبة

تحل هذه الحاسبة من 2 إلى 4 تطابقات صحيحة. ولا تدعم أكثر من أربعة تطابقات، ولا المعاملات السالبة، ولا حالة المعامل 1، ولا الأعداد العشرية، ولا التطابقات الرمزية أو كثيرة الحدود.

• يجب أن تكون البواقي والمعاملات أعداداً صحيحة.
• يجب أن يكون كل معامل 2 أو أكبر.
• النتيجة فريدة بترديد M، وليست عدداً منفرداً فقط.
• الخوارزمية المستخدمة هي الدمج الزوجي، وليست طريقة مصفوفات أو حذف غاوسي.
• لا توجد بيانات رسمية أو متغيرة؛ هذه عملية رياضية دقيقة فقط.