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

مبرهنة

ليكن n_1,…, n_k أعداد طبيعية مثنى مثنى أعداد أولية فيما بينها أولية فيما بينها (أي PGCD pgcd (< >n< >i، < >n< >j) 1 عند < >i ≠ < >j). إذن كل الأعداد الصحيحة a_1,…, a_k, يوجد عدد صحيح x, وحيد متقارب مع الأعداد الصحيحة المقاربة بترديد n prod_ i 1 ^k n_i وبحيث

egin matrix

x equiv a_1pmod n_1

ldots

x equiv a_kpmod n_k

end matrix

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

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

e_i equiv 1 pmod n_i ,

و

e_i equiv 0 pmod n_j , ل < >j ≠ < >i.

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

يمكن إثبات الوحدانية والوجود من خلال التالي

هناك math < >N < >n1·…·< >nk من k بواقٍ مختلفة. لنسم هذه المجموعة R. من ناحية أخرى، math < >N 1, …, < >N , وكل عنصر من math 1, …, < >N يقابل عنصر من R.

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

وبما أن هذا مستحيل الحدوث فإن الدالة math 1, …, < >N → < >R ستكون دالة تقابل، حيث أن math 1, …, < >N < >R ، وبالتالي نحصل على علاقة التقابل.

يمكن رؤية الوجود من خلال البناء لعناصر x. لتكن math [< >a−1]< >b ترمز مقلوب عدد نمطي للمعاكسات الضربية ل math < >a (mod < >b) والتي يمكن الحصول عليها من خلال خوارزمية إقليدس الممددة القسمة الإقليدية الممددة ، والتي تكون معرفة إذا a و b أوليان فيما بينهما. البناء التالي للعناصر يبين لم نحتاج هذه الخاصية.

حالة المعادلتين ( math < >k 2 )

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

egin cases x equiv a_1 & pmod n_1 x equiv a_2 & pmod n_2 end cases

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

n_2 [n_2^ -1
ight ]_ n_1 + n_1 [n_1^ -1
ight ]_ n_2 1

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

تطبيقات

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

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

التعمية

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

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

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

Disqvisitiones-800 مبرهنة الباقي الصيني بُرهن عليها من طرف كارل فريدريش غاوس غاوس في عمل المنشور عام 1801 < > استفسارات حسابية (كتاب) استفسارات حسابية . Harvtxt Gauss Clarke 1986 loc Art. 32-36

مبرهنة الباقي الصيني إنك Chinese r ainder theor هي نتيجة حسابيات توافقية للحسابيات التوافقية في نظرية الأعداد تعالج حل أنظمة التقارب على الأعداد تقارب . هذه النتيجة خاصة أساسا في الحلقة Z/nZ Z/nZ تعمم في نظرية الحلقات . نُشرت لأول بين القرنين الثالث والخامس للميلاد من طرف عالم الرياضيات الصيني سون تزو (عالم رياضيات) سون تزو .

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