قضیه باقی‌مانده چینی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

قضیه باقی‌مانده چینی(Chinese remainder theorem) قضیه‌ای در زمینه نظریه اعداد است و تعمیم آن در جبر نظری بیان می‌شود.

شرح قضیه[ویرایش]

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

فرض کنید n۱، n۲، …، nk اعداد صحیحی باشند که دو به دو نسبت به هم اولند. برای هر سری اعداد صحیح a۱،a۲، …، ak عدد صحیح x وجود دارد به طوری که در دستگاه معادلات همنهشتی زیر صدق کند:

\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}

علاوه بر این تمام جوابهای x به پیمانه N = n۱n۲nk همنهشتند. در نتیجه برای همه 1\leq i \leq k داریم: x\equiv y \pmod{n_i} اگر و تنها اگر x \equiv y \pmod{N}. گاهی اوقات این دستگاه حتی زمانی که همه niها دوبه دو نسبت به هم اول نیستند هم قابل حل است: جواب x وجود دارد اگر و تنها اگر:

a_i \equiv a_j \pmod{\gcd(n_i,n_j)} \qquad \mbox{for all }i\mbox{ and }j. \,\!

در این حالات تمام جوابهای x به پیمانه کوچک‌ترین مضرب مشترک niها همنهشتند. شکلهایی از این قضیه در کتابLiber Abaci از فیبوناچی(Fibonacci) در سال ۱۲۰۲ آمده‌است.

الگوریتمی ساختاری برای یافتن جواب[ویرایش]

این الگوریتم قسمتی از اثبات قضیه هم هست زیرا جواب x را برای دستگاه پیدا می‌کند.

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

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

x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \ldots, k.

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

 r_i n_i + e_i = 1 \,\!

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

e_i \equiv 1 \pmod{n_i} \quad \mathrm{and} \quad  e_i \equiv 0 \pmod{n_j} \quad \mathrm{for} ~ i \ne j

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

 x = \sum_{i=1}^k a_i e_i.\!

نمونه[ویرایش]

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

x \equiv 2 \pmod{3}, \,\!
x \equiv 3 \pmod{4}, \,\!
x \equiv 1 \pmod{5}. \,\!

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

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

کاربرد[ویرایش]

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

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

اثبات قضیه[ویرایش]

یک طرف قضیه با روشی که برای بدست آوردن جواب ارائه شد اثبات شد. اثبات یکتایی این جواب هم با استفاده از برهان خلف ثابت می‌شود:

فرض می‌کنیم که دو جواب صحیح مثبت x و y کوچکتر از N برای دستگاه وجود دارد. بعد ثابت می کنیم که هر کدام از niها تفاضل این دو عدد را می شمارد. نتیجه می‌شود که N هم تفاضل این دو عدد را می شمارد که این خلاف فرض ما است که دو عدد x و y را بین صفر و N در نظر گرفتیم.

تعمیم[ویرایش]

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

\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}

منابع[ویرایش]