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

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

مبرهنة الباقي الصينية (بالإنجليزية: Chinese remainder theorem)‏ هي نتيجة للحسابيات التوافقية في نظرية الأعداد تعالج حل أنظمة تقارب.[2][3] هذه النتيجة خاصة أساسا في Z/nZ تعمم في نظرية الحلقات. نُشرت لأول بين القرنين الثالث والخامس للميلاد من طرف عالم الرياضيات الصيني سون تزو.

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

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

مبرهنة

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

${\displaystyle {\begin{matrix}x\equiv a_{1}{\pmod {n_{1}}}\\\ldots \\x\equiv a_{k}{\pmod {n_{k}}}\\\end{matrix}}}$

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

لكل i, الأعداد ${\displaystyle n_{i}\,}$ و${\displaystyle {\hat {n}}_{i}={\frac {n}{n_{i}}}}$ أولية فيما بينها، وباستعمال 'متساوية بيزوت, يمكن إيجاد الأعداد ${\displaystyle u_{i}\,}$ و${\displaystyle v_{i}\,}$ بحيث${\displaystyle u_{i}n_{i}+v_{i}{\hat {n}}_{i}=1}$. إذا افترضنا ${\displaystyle e_{i}=v_{i}{\hat {n}}_{i}}$, فنحصل على

${\displaystyle e_{i}\equiv 1{\pmod {n_{i}}}\,}$

و

${\displaystyle e_{i}\equiv 0{\pmod {n_{j}}}\,}$ ل j ≠ i.

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

يمكن إثبات الوحدانية والوجود من خلال التالي: هناك N = n₁·…·n_k من k بواقٍ مختلفة. لنسم هذه المجموعة R. من ناحية أخرى، N = #{1, ..., N}, وكل عنصر من {1, ..., N} يقابل عنصر من R.

هل من الممكن أن يقابل عنصران من a, b ∈ {1, ..., N}, نفس العنصر من R؟ أي هل من الممكن أن يكون لهما نفس مجموعة العناصر عند القسمة على n₁, ..., n_k؟ إذا كان هذا صحيحاً فإن كلاً من a − b سيكون قابلاً للقسمة على كلٍ من n_i. وبما أن n_i أوليان مثنى مثنى، فإن a − b سيكون قابلاً على القسمة على حاصل ضربهم N.

وبما أن هذا مستحيل الحدوث فإن الدالة {1, ..., N} → R ستكون دالة تقابل، حيث أن #{1, ..., N} = #R، وبالتالي نحصل على علاقة التقابل. يمكن رؤية الوجود من خلال البناء لعناصر x. لتكن [a^−1]_b ترمز للمعاكسات الضربية ل a (mod b) والتي يمكن الحصول عليها من خلال القسمة الإقليدية الممددة، والتي تكون معرفة إذا a و b أوليان فيما بينهما. البناء التالي للعناصر يبين لم نحتاج هذه الخاصية.

حالة المعادلتين (k = 2)

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

${\displaystyle {\begin{cases}x\equiv a_{1}&{\pmod {n_{1}}}\\x\equiv a_{2}&{\pmod {n_{2}}}\end{cases}}}$

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

${\displaystyle n_{2}\left[n_{2}^{-1}\right]_{n_{1}}+n_{1}\left[n_{1}^{-1}\right]_{n_{2}}=1}$

الحالة العامة

تطبيقات

ترقيم المتتاليات

تحويل فيورييه السريع

التعمية

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

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

مبرهنة ديدكايند

مراجع

1. Gauss & Clarke (1986, Art. 32-36)
2. Le théorème des restes chinois نسخة محفوظة 24 نوفمبر 2016 على موقع واي باك مشين., Textes, commentaires et activités pour l’arithmétique au lycée, sur le site CultureMath نسخة محفوظة 14 مايو 2012 على موقع واي باك مشين. de l'ENS, § 1. Le problème des restes chinois : Questions sur ses origines. نسخة محفوظة 24 نوفمبر 2016 على موقع واي باك مشين.
3. Joseph B. Dence, Thomas P. Dence. "Elements of the Theory of Numbers". مؤرشف من الأصل في 2018-01-15. اطلع عليه بتاريخ 2016-08-28.

وصلات خارجية