نمایش مبدأ برای قضیه باقی‌مانده چینی

[[File:Sun_Tzu_Chinese_remainder_theorem.svg|پیوند=https://en.wikipedia.org/wiki/File:Sun_Tzu_Chinese_remainder_theorem.svg|بندانگشتی|فرمول اصلی Sun-tzu: ''x'' ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7)با جواب <math>x = 23 + 105k</math>، که k یک [[عدد صحیح]] است.|حاشیه]]
در ریاضیات، '''قضیه باقیمانده چینی''' بیان می‌کند که اگر باقی‌مانده تقسیم اقلیدسی یک عدد صحیح n را بر چند عدد صحیح بدانیم، می‌توانیم باقیمانده تقسیم n را بر [[حاصل‌ضرب|حاصل ضرب]] این اعداد صحیح به‌طور یکتا تعیین کنیم، به شرط آن که مقسوم‌علیه‌ها نسبت به هم اول باشند (هیچ دو مقسوم‌علیه به جز ۱ عامل مشترکی نداشته باشند).

به عنوان مثال، اگر بدانیم که باقیمانده n تقسیم بر ۳ برابر ۲ است، باقیمانده n تقسیم بر ۵ برابر ۳ است و باقیمانده n تقسیم بر ۷ برابر ۲ است، بدون دانستن مقدار n، می‌توانیم تعیین کنیم که باقیمانده n تقسیم بر ۱۰۵ (ضرب ۳، ۵ و ۷) ۲۳ است. مهمتر از همه، این به ما می‌گوید که اگر n [[عدد طبیعی]] کمتر از ۱۰۵ باشد، ۲۳ تنها مقدار ممکن n است.

فرم اولیه قضیه در کتاب [[:en:Sunzi_Suanjing|سان زی سوآنجینگ]](孙子算经)([[Sun Zi Suanjing]]) نوشته ریاضی‌دان چینی [[سان تزو|سون تزو]] (Sun Tzu) که بعداً در [[۱۲۴۷]] توسط [[قین جیوشاو]] (Qin Jiushao) باز نوشت شد گنجانده شده.

قضیه باقیمانده چینی به‌طور گسترده برای محاسبات با اعداد صحیح بزرگ استفاده می‌شود، زیرا محاسباتی را که برای آن فرد محدودیتی در اندازه خروجی دارد با چندین محاسبات مشابه روی اعداد صحیح کوچک جایگزین می‌کند.

قضیه باقی مانده چینی (بیان شده بر حسب [[هم‌نهشتی (نظریه اعداد)|همنهشتی‌ها]]) در هر [[حوزه ایده‌آل اصلی]] صادق است. این قضیه با صورتی شامل [[ایده‌آل (نظریه حلقه‌ها)|ایده‌آل‌های دوطرفه]] به هر [[حلقه (ریاضیات)|حلقه‌ای]] تعمیم داده شده‌است.

== تاریخچه ==
[[File:Disqvisitiones-800.jpg|پیوند=https://en.wikipedia.org/wiki/File:Disqvisitiones-800.jpg|بندانگشتی|قضیه باقی‌مانده چینی توسط [[کارل فریدریش گاوس|گاوس]] در ''Disquisitiones Arithmeticae''(منتشر شده در ۱۸۰۱ میلادی) استفاده شد است.<ref name="Gauss1801.loc=32-36">{{Harvnb|Gauss|1986|loc=Art. 32–36}}</ref>]]
اولین نسخه شناخته شده از این قضیه، به عنوان مسئله ای با اعدادی خاص، در کتاب قرن سوم Sun-tzu Suan-ching توسط ریاضیدان چینی Sun-tzu آمده‌است:<ref>{{Cite journal|last=Tattersall|first=Jim|last2=Katz|first2=Victor J.|date=1994-09|title=A History of Mathematics: An Introduction|url=http://dx.doi.org/10.2307/2687626|journal=The College Mathematics Journal|volume=25|issue=4|pages=347|doi=10.2307/2687626|issn=0746-8342}}</ref><blockquote>چند شی داریم که تعدادشان مشخص نیست. اگر آنها را سه‌تا سه‌تا بشماریم، دو عدد باقی می‌ماند و با پنج، ما سه تا باقی‌مانده خواهیم داشت. برای هفت هم، دو تا باقی می‌ماند. چند شی وجود دارد؟<ref>{{Cite journal|last=Bruckman|first=Paul|last2=Dence|first2=Joseph B.|last3=Dence|first3=Thomas P.|last4=Young|first4=Justin|date=2013-05|title=Series of Reciprocal Triangular Numbers|url=http://dx.doi.org/10.4169/college.math.j.44.3.177|journal=The College Mathematics Journal|volume=44|issue=3|pages=177–184|doi=10.4169/college.math.j.44.3.177|issn=0746-8342}}</ref></blockquote>
کارهای سون تزو شامل هیچ الگوریتم یا اثباتی کاملی برای این سؤال نیست.<ref>{{harvnb|Dauben|2007|page=302}}</ref> اولین چیزی که بتوان آن را به عنوان یک الگوریتم برای این سؤال شناخت توسط [[آریابهاتا]] در قرن ششم ارائه شد.<ref>{{harvnb|Kak|1986}}</ref> نسخه‌های خاصی از قضیه باقی‌مانده چینی توسط [[برهماگوپتا]] (قرن ۷ام) نیز شناخته شده بود که در کتاب [[:en:Liber_Abaci|Liber Abaci]] [[لئوناردو فیبوناچی|فیبوناچی]] در ۱۲۰۲ میلادی نیز آورده شده‌اند.<ref>{{harvnb|Pisano|2002|pages=402–403}}</ref> در نهایت تعمیم این صورت‌بندی‌ها به اسم ''Da-yan-shu'' ({{lang|zh|大衍術}}) توسط [[:en:Qin_Jiushao|Ch'in Chiu-shao]] در ''[[:en:Mathematical_Treatise_in_Nine_Sections|Mathematical Treatise in Nine Sections]]'' ({{lang|zh|數書九章}}, ''Shu-shu Chiu-chang'')<ref>{{harvnb|Dauben|2007|page=310}}</ref> در سال ۱۲۴۷ میلادی منتشر شده‌است که نهایتاً اوایل قرن ۱۹ام میلادی به زبان انگلیسی توسط [[:en:Alexander_Wylie_(missionary)|Alexander Wylie]] ترجمه شده‌اند.<ref>{{harvnb|Libbrecht|1973}}</ref>

اولین صورت‌بندی به وسیله همنهشتی‌ها توسط [[کارل فریدریش گاوس|گاوس]] در ''Disquisitiones Arithmeticae''(منتشر شده در ۱۸۰۱ میلادی) استفاده شد است. گاوس قضیه باقیمانده چینی را در مورد مسئله‌ای در مورد تقویم‌ها نشان می‌دهد، یعنی «پیدا کردن سال‌هایی که دارای یک دوره معین نسبت به چرخه خورشیدی و قمری و دوره رومی هستند».<ref>{{harvnb|Ore|1988|page=247}}</ref> گاوس روشی را برای [[حل مسئله]] معرفی می‌کند که قبلاً توسط [[لئونارد اویلر]] استفاده شده بود اما در واقع یک روش بسیار قدیمی‌تر بود که چندین بار ظاهر شده بود.<ref>{{harvnb|Ore|1988|page=245}}</ref>

== شرح قضیه ==
فرض کنید ''n''<sub>۱</sub>، ''n''<sub>۲</sub>، …، ''n''<sub>''k''</sub> اعداد صحیحی باشند که دو به دو نسبت به هم اولند. برای هر سری اعداد صحیح ''a''<sub>۱</sub>،''a''<sub>۲</sub>، …، ''a''<sub>''k''</sub> عدد صحیح x وجود دارد به‌طوری‌که در دستگاه [[معادلات همنهشتی]] زیر صدق کند:

:<math display="block">\begin{align}
 x &\equiv a_1 \pmod{n_1} \\
 x &\equiv a_2 \pmod{n_2} \\
   &\vdots \\
 x &\equiv a_k \pmod{n_k}
\end{align}</math>

علاوه بر این تمام جوابهای x به [[پیمانه]] ''N'' = ''n''<sub>۱</sub>''n''<sub>۲</sub>…''n''<sub>''k''</sub> همنهشتند. در نتیجه برای همه <math>1\leq i \leq k</math> داریم:<math> x\equiv y \pmod{n_i}</math> اگر و تنها اگر <math>x \equiv y \pmod{N}</math>.
گاهی اوقات این دستگاه حتی زمانی که همه ''n<sub>i</sub>''ها دوبه دو نسبت به هم اول نیستند هم قابل حل است.

فرض کنید <math>\; d_1,d_2, ... ,d_n</math> و همچنین <math>\; a_1,a_2,...,a_n</math> اعدادی صحیح باشند که برای هر <math>\; 0 \le i,j \le n</math> داشته باشیم <math> \; (d_i,d_j)|a_i-a_j</math>. که <math> \;(d_i,d_j)</math> [[بزرگ‌ترین مقسوم علیه مشترک|ب.م. م]] <math>\; d_i</math> و <math>\; d_j</math> است. حال حتماً عدد صحیح <math>\; x</math> وجود دارد به‌طوری‌که در دستگاه [[معادلات همنهشتی]] زیر صدق کند:

<math display="block">\begin{align}
 x &\equiv a_1 \pmod{d_1} \\
 x &\equiv a_2 \pmod{d_2} \\
   &\vdots \\
 x &\equiv a_k \pmod{d_k}
\end{align}</math>

== روش ساختاری برای یافتن جواب ==
این [[الگوریتم]] قسمتی از اثبات قضیه هم هست زیرا جواب x را برای دستگاه پیدا می‌کند.

این الگوریتم تنها زمانی که <math>n_i</math>ها دوبه دو نسبت به هم اولند جواب می‌دهد. در حالی که روش [[تفریق‌های متوالی]] معمولاً حتی زمانی که پیمانه‌ها دو به دو نسبت به هم اول نیستند هم کاربرد دارد.

فرض کنید جوابی برای دستگاه معادلات زیر وجود دارد.

:<math>x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \ldots, k.</math>

حاصلضرب <math> N=n_1n_2\ldots n_k</math> تعریف می‌شود. جواب x به صورت زیر بدست می‌آید. برای هرi, <math>n_i</math> و <math>N/n_i</math> نسبت به هم اولند. با استفاده از [[الگوریتم گسترده اقلیدس]](extended Euclidean algorithm) می‌توان اعداد <math>r_i</math> و <math>s_i</math> را طوری‌که <math>r_in_i + s_iN/n_i = 1</math> باشد را یافت. با فرض اینکه <math>e_i=s_iN/n_i</math> باشد می‌توان به عبارت زیر رسید.

:<math> r_i n_i + e_i = 1 \,\! </math>

با در نظر گرفتن <math>e_i</math>، عبارت بالا تضمین می‌کند که باقی‌مانده تقسیم آن بر <math>n_i</math> برابر ۱ خواهد بود. از طرفی چون خود این عدد برابر <math>s_iN/n_i</math> تعریف شده‌است، بر تمام <math>n_j</math>ها مگر <math>n_i</math> بخشپذیر است و داریم:

:<math>e_i \equiv 1 \pmod{n_i} \quad \mathrm{and} \quad  e_i \equiv 0 \pmod{n_j} \quad \mathrm{for} ~ i \ne j</math>

در نتیجه با استفاده از قوانین ضرب در همنهشتی‌ها، جوابی برای دستگاه معادلات همنهشتی به صورت زیر خواهد بود:

:<math> x = \sum_{i=1}^k a_i e_i.\! </math>

== نمونه ==
پرسشی برای بدست آوردن عدد صحیح x که در دستگاه زیر صدق کند را در نظر بگیرید.

:<math>x \equiv 2 \pmod{3}, \,\! </math>
:<math>x \equiv 3 \pmod{4}, \,\! </math>
:<math>x \equiv 1 \pmod{5}. \,\! </math>

با استفاده از [[الگوریتم اقلیدس]] برای ۳و ۴×۵ = ۲۰ داریم (۱۳-) × ۳ + ۲ × ۲۰ = ۱، یعنی ''e''<sub>۱</sub> = ۴۰ و برای ۴ و ۳×۵ = ۱۵ بدست می‌آوریم (۱۱-) × ۴ + ۳ × ۱۵ = ۱ یعنی ''e''<sub>۲</sub> = ۴۵. در نهایت برای ۵ و ۳×۴ = ۱۲ الگوریتم اقلیدس نتیجه می‌دهد۵ × ۵ + (۲-) × ۱۲ = ۱ به این معنا که ''''e''<sub>۳</sub> = −۲۴ است. پس یکی از جوابها برای x عدد ۲ × ۴۰ + ۳ × ۴۵ + ۱ × (۲۴-) = ۱۹۱ است. تمام اعداد صحیح دیگر که به پیمانه ۳ × ۴ × ۵ = ۶۰ با ۱۹۱ همنهشتند هم جواب هستند؛ یعنی همه آن‌ها با ۱۱ به پیمانه ۶۰ [[هم‌نهشتی (نظریه اعداد)|همنهشتند]].

نکته: ممکن است اعداد بدست آمده با الگوریتم اقلیدس برای <math>e_i</math>ها متفاوت باشد، اما در جواب نهایی همه مشترکند.

== کاربرد ==
{{ویکی‌سازی}}
{{تمیزکاری}}
از این قضیه در [[الگوریتم RSA]] برای رسیدن به جواب در زمان کمتر استفاده می‌شود.

برای انجام محاسبات بر روی اعداد بسیار بزرگ از این قضیه استفاده می‌شود. اعداد که نسبت به هم اولند به عنوان <math>n_i</math> انتخاب می‌شوند و اعداد بزرگ برای محاسبه به صورت [[زوج مرتب]] از <math>a_i</math>ها در می‌آیند و پس از انجام محاسبات بر روی <math>a_i</math>ها نتیجه به صورت خود عدد درمی‌آید.

== تعمیم ==
فرض کنید <math>R</math> یک حلقه باشد و <math>I_1,\cdots,I_n</math> ایده‌آل‌هایی از <math>R</math> باشند که برای هر <math>i\neq j</math> داشته باشیم <math>I_i+I_j=R</math>. اگر <math>b_1,\cdots,b_n</math> عنصرهای دلخواه <math>R</math> باشند آنگاه عنصر <math>b</math> چنان در <math>R</math> موجود است که <math>b-b_i\in R</math> (در واقع <math>b\overset{I_i}{\equiv}b_i</math>). به علاوه اگر <math>c</math> موجود باشد که خاصیت <math>b</math> را داشته‌باشد آنگاه <math>b-c\in \bigcap_{i=1}^n I_i</math> (در واقع <math>b\overset{\bigcap_{i=1}^n I_i}{\equiv}c</math>).<ref>Bhattacharya, Phani Bhushan, Surender Kumar Jain, and S. R. Nagpaul. ''Basic abstract algebra''. Cambridge University Press, 1994.</ref>

== منابع ==
{{پانویس|۲}}

== منابع ==
{{چپ‌چین}}
* [[دانلد کنوت]]. ''[[هنر برنامه‌نویسی رایانه]]'', Volume 2: ''Seminumerical Algorithms'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89684-2|en}}. Section 4.3.2 (pp.286–291), exercise 4.6.2–3 (page 456).
* [[توماس اچ کورمن]]،  [[Charles E. Leiserson]], [[رونالد ریوست]]،  and [[کلیفورد استین]]. ''[[مقدمه‌ای بر الگوریتم‌ها]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7|en}}. Section 31.5: The Chinese remainder theorem, pp.873–876.
* {{یادکرد|فصل= |کتاب=Fibonacci's Liber Abaci|ناشر= Springer-Verlag|شهر= |کوشش= |ویرایش= |سال= 2002 |شابک=0-387-95419-8 |نویسنده= Sigler, Laurence E. (trans.)|نویسندگان سایر بخش‌ها=|ترجمه=|صفحه=402–403 |زبان=en |مقاله= |ژورنال= |نشریه= |تاریخ= |دوره= |شماره= |شاپا=}}
{{پایان چپ‌چین}}

[[رده:جبر جابجایی]]
[[رده:جبر]]
[[رده:حساب پیمانه‌ای]]
[[رده:قضیه‌ها در نظریه اعداد]]
[[رده:قضیه‌های ریاضی]]
[[رده:کشفیات ریاضیاتی چینی]]
[[رده:نظریه اعداد]]