المحتوى هنا ينقصه الإستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
بحاجة لمصدر
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.(أغسطس 2015)

مبرهنة الباقي الصيني (بالإنكليزية: Chinese remainder theorem) هي نتيجة للحسابيات التوافقية تعالج حل أنظمة تقارب. هذه النتيجة خاصة أساسا في Z/nZ تعمم في نظرية الحلقات. تم نشرها لأول بين القرنين الثالث والخامس للميلاد. في شكلها المبسط، تبين المبرهنة إذا كان العدد n، عند قسمته بعدة قواسم، يعني بواقٍ معينة.

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

مبرهنة[عدل]

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


\begin{matrix}
x \equiv a_1\pmod{n_1}\\ 
\ldots \\ 
x \equiv a_k\pmod{n_k}\\
\end{matrix}

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

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

e_i \equiv 1 \pmod{n_i} \,

و

e_i \equiv 0 \pmod{n_j}\, ل ji.

الوجود والوحدانية[عدل]

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

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

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

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

انظر أيضا[عدل]

مراجع[عدل]

وصلات خارجية[عدل]