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

مبرهنة الباقي الصيني بُرهن عليها من طرف غاوس في عمل المنشور عام 1801 استفسارات حسابية.

مبرهنة الباقي الصينية قالب:إنج هي نتيجة للحسابيات التوافقية في نظرية الأعداد تعالج حل أنظمة تقارب. هذه النتيجة خاصة أساسا في Z/nZ تعمم في نظرية الحلقات. نُشرت لأول بين القرنين الثالث والخامس للميلاد من طرف عالم الرياضيات الصيني سون تزو.

في شكلها المبسط، تحدد المبرهنة عددا n، عند قسمته على عدة قواسم معلومة، يعطي بواقٍ معلومة. على سبيل المثال، ما هو أصغر عدد طبيعي الذي إذا قُسم على 3 يعطي باقيا مساويا ل 2 وإذا قُسم على 5 يعطي باقيا مساويا ل 3 وإذا قُسم على 7 يعطي باقيا مساويا ل 2 ؟

نظام تقارب الأعداد

مبرهنة

ليكن $n_1$,..., $n_k$ أعداد طبيعية مثنى مثنى أولية فيما بينها (أي pgcd (n_i، n_j) = 1 عند i ≠ j). إذن كل الأعداد الصحيحة $a_1$,..., $a_k$, يوجد عدد صحيح $x$, وحيد المقاربة بترديد $n=\prod _{i=1}^k{n}_i$ وبحيث

$\begin{array}{c}x\equiv a_1(\mathrm{mod}{n}_1)\\ \dots \\ x\equiv a_k(\mathrm{mod}{n}_k)\end{array}$

الحل x يمكن إيجاده كما يلي:

لكل i, الأعداد $n_i$ و${\hat{n}}_i=\frac{n}{n_i}$ أولية فيما بينها، وباستعمال 'متساوية بيزوت, يمكن إيجاد الأعداد $u_i$ و$v_i$ بحيث$u_i{n}_i+v_i{\hat{n}}_i=1$. إذا افترضنا $e_i=v_i{\hat{n}}_i$, فنحصل على

$e_i\equiv 1(\mathrm{mod}{n}_i)$

و

$e_i\equiv 0(\mathrm{mod}{n}_j)$ ل j ≠ i.

الوجود والوحدانية

يمكن إثبات الوحدانية والوجود من خلال التالي: هناك قالب:Math من k بواقٍ مختلفة. لنسم هذه المجموعة R. من ناحية أخرى، قالب:Math وكل عنصر من قالب:Math يقابل عنصر من R.

هل من الممكن أن يقابل عنصران من قالب:Math نفس العنصر من R؟ أي هل من الممكن أن يكون لهما نفس مجموعة العناصر عند القسمة على قالب:Math؟ إذا كان هذا صحيحاً فإن كلاً من قالب:Math سيكون قابلاً للقسمة على كلٍ من n_i. وبما أن n_i أوليان مثنى مثنى، فإن قالب:Math سيكون قابلاً على القسمة على حاصل ضربهم N.

وبما أن هذا مستحيل الحدوث فإن الدالة قالب:Math ستكون دالة تقابل، حيث أن قالب:Math، وبالتالي نحصل على علاقة التقابل. يمكن رؤية الوجود من خلال البناء لعناصر x. لتكن قالب:Math ترمز للمعاكسات الضربية ل قالب:Math والتي يمكن الحصول عليها من خلال القسمة الإقليدية الممددة، والتي تكون معرفة إذا a و b أوليان فيما بينهما. البناء التالي للعناصر يبين لم نحتاج هذه الخاصية.

حالة المعادلتين (قالب:Math)

ليكن النظام التالي المكون من معادلتين:

$\{\begin{array}{cc}x\equiv a_1& (\mathrm{mod}{n}_1)\\ x\equiv a_2& (\mathrm{mod}{n}_2)\end{array}$

انظر إلى متطابقة بوزو.

$n_2{\left[n_2^{-1}\right]}_{n_1}+n_1{\left[n_1^{-1}\right]}_{n_2}=1$

تطبيقات

استيفاء هيرميت

انظر إلى معضلة استيفاء هيرميت.