أصغر حل
المقياس
المقاييس

    التطابقات

    المزيد عن مبرهنة الباقي الصينية

    حاسبة مبرهنة الباقي الصينية

    عُدّ كومة من الأشياء ثلاثة ثلاثة فيبقى 2، وخمسة خمسة فيبقى 3، وسبعة سبعة فيبقى 2: عددها 23، أو 128، أو 233، جواب واحد كل 105. هذه مسألة كتاب سون تزو سوان جينغ التي منحت مبرهنة الباقي الصينية اسمها. اكتب أي نظام تطابقات ⁦x ≡ a (mod n)⁩، بأي عدد من التطابقات وأعداد بأي حجم، وشاهد الجواب، والحل بأعدادك، ورسمًا يبيّن لماذا ينجح ذلك. وعندما لا يمكن أن تتحقق التطابقات كلها، تذكر الحاسبة التطابقين المتعارضين وتبيّن السبب. اكتب التطابقات ⁦x ≡ a (mod n)⁩، تطابقًا واحدًا في كل سطر: ⁦a⁩ هو الباقي و⁦n⁩ هو المقياس. أضف سطرًا بزر إضافة تطابق، أو بالضغط على Enter في آخر مقياس، واحذف سطرًا بالزر ×. يمكن استخدام أعداد صحيحة حتى 200 رقم، ويمكن أن يكون ⁦a⁩ سالبًا. أو اختر مثالًا محلولًا. تعرض البطاقات أصغر حل وكل كم يتكرر؛ وتحتها أول الحلول الموجبة وتحقق من كل تطابق. يضع الرسم علامة على الأعداد التي تحقق كل تطابق، والعمود الذي فيه علامة في كل صف هو الحل؛ ويعرض جدول البواقي تطابقين معًا. يُكتب الحل بأعدادك، بطريقة البناء المعروفة في الكتب أو بالتعويض.

    كيف يعمل

    1. اكتب التطابقات ⁦x ≡ a (mod n)⁩، تطابقًا في كل سطر، أو اختر مثالًا محلولًا مثل مسألة سون تزو أو سلة البيض أو الدورة اليوليانية.
    2. اقرأ أصغر حل، والمقياس الذي يتكرر به، وأول الحلول الموجبة، وكل منها متحقق منه في كل تطابق.
    3. تابع الحل خطوة بخطوة، بالبناء أو بالتعويض، وبدّل الرسم بين خط الأعداد وجدول البواقي.

    كيف تعمل طريقة البناء

    عندما لا يكون لأي مقياسين عامل مشترك، يمكن بناء الحل مباشرة. اضرب المقاييس: في مسألة سون تزو ⁦N = 3 × 5 × 7 = 105⁩. لكل تطابق خذ ⁦Nᵢ = N / nᵢ⁩، وهو من مضاعفات كل مقياس آخر: 35 و21 و15. ثم أوجد المعكوس ⁦yᵢ⁩ لـ ⁦Nᵢ mod nᵢ⁩ بخوارزمية إقليدس الموسعة: 35 يترك الباقي 2 عند القسمة على 3، و⁦2 × 2 = 4 ≡ 1 (mod 3)⁩، لذا ⁦y₁ = 2⁩؛ و21 و15 يتركان الباقي 1، فمعكوساهما 1. والآن ⁦x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233⁩، و⁦233 mod 105 = 23⁩. كل حد يناسب تطابقه ويكون من مضاعفات المقاييس الأخرى، لذا يناسب المجموع التطابقات كلها.

    عندما يكون للمقاييس عامل مشترك

    قد يكون للنظام حل حتى لو كان لمقاييسه عوامل مشتركة. يمكن أن يتحقق التطابقان ⁦x ≡ a (mod m)⁩ و⁦x ≡ b (mod n)⁩ معًا إذا وفقط إذا كان ⁦a − b⁩ من مضاعفات ⁦gcd(m, n)⁩، ويتكرر الحل عندئذ كل ⁦lcm(m, n)⁩ بدلًا من كل ⁦m × n⁩. حافلتان تنطلقان في الدقيقتين 5 و11، كل 12 وكل 18 دقيقة، تلتقيان في الدقيقة 29 ثم كل 36 دقيقة، لأن ⁦11 − 5 = 6⁩ من مضاعفات ⁦gcd(12, 18) = 6⁩. لكن ⁦x ≡ 1 (mod 4)⁩ و⁦x ≡ 4 (mod 6)⁩ لا يمكن أن يتحققا معًا أبدًا: الأول يجعل ⁦x⁩ فرديًا والثاني يجعله زوجيًا. يكون للنظام كله حل إذا وفقط إذا كان لكل زوج من تطابقاته حل، وهكذا تجد الحاسبة التطابقين المتعارضين.

    الأسئلة المتداولة

    ماذا تقول مبرهنة الباقي الصينية؟

    إذا لم يكن لأي اثنين من المقاييس ⁦n₁, n₂, …⁩ عامل مشترك، فلأي بواقٍ ⁦a₁, a₂, …⁩ يوجد بالضبط ⁦x⁩ واحد من 0 إلى ⁦N − 1⁩ بحيث ⁦x ≡ aᵢ (mod nᵢ)⁩ لكل ⁦i⁩، حيث ⁦N⁩ حاصل ضرب المقاييس. وكل حل آخر يختلف عنه بمضاعف لـ ⁦N⁩: حلول مسألة سون تزو هي 23 و128 و233 وهكذا، حل كل 105.

    لماذا تُسمّى صينية؟

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

    وماذا لو لم تكن المقاييس أولية فيما بينها؟

    عندئذ قد لا يوجد حل، وإن وُجد فإنه يتكرر كل مضاعف مشترك أصغر للمقاييس بدلًا من كل حاصل ضرب. يتوافق تطابقان إذا تساوى باقياهما بمقياس ⁦gcd⁩ مقياسيهما. تستخدم أحجية البيض الأعداد 2 و3 و4 و5 و6 و7، ولها عوامل مشتركة، ومع ذلك لها حل: 301، ويتكرر كل 420.

    كيف يستخدم RSA مبرهنة الباقي الصينية؟

    فك تشفير رسالة RSA يعني حساب ⁦c^d mod n⁩، حيث ⁦n = p × q⁩. والأسرع حساب ⁦c^d mod p⁩ و⁦c^d mod q⁩ كلٍّ على حدة، مع اختزال الأس بالمقياسين ⁦p − 1⁩ و⁦q − 1⁩، ثم جمع النتيجتين بالمبرهنة. مع أعداد طولها النصف، تحتاج كل من القوتين إلى نحو ثُمن العمل، لذا يصبح فك التشفير أسرع بنحو أربع مرات، وأغلب برامج RSA تفعل ذلك.

    ما أكبر حجم للأعداد؟

    حتى 20 تطابقًا، وأعداد لا يزيد كل منها على 200 رقم. تحسب الحاسبة بأعداد صحيحة دقيقة في متصفحك، لذا يكون الجواب دقيقًا مهما طال، ولا يُرسل أي شيء إلى أي مكان.

    هل أنت مستعد لتجربتها؟

    افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

    الانتقال إلى المحرر