משפט השאריות הסיני

משפט השאריות הסיני הוא שמם של מספר משפטים בתורת המספרים ובתורת החוגים, הקשורים זה לזה. בצורתו הבסיסית והמקורית המשפט עוסק במערכת של משוואות מודולריות ומבטיח קיום של פתרון למערכת תחת תנאים מסוימים.

מקורו של המשפט בספר מהמאה ה-3 של המתמטיקאי הסיני סן-צו, ומכאן שמו. המשפט פורסם פעם נוספת ב על ידי מתמטיקאי סיני נוסף, צ'ין ג'יו-האו.

==המשפט עבור משוואות מודולריות==
יהיו <math>n_1,\ldots,n_k</math> מספרים טבעיים זרים בזוגות (כלומר המחלק המשותף המקסימלי של כל שניים מהם הוא 1).
יהיו <math>a_1,\ldots,a_k</math> מספרים שלמים כאשר <math>0\le a_i\le n_i-1</math>. אזי למערכת המשוואות
:<math>x\equiv a_i\!\!\!\!\pmod{\!n_i}\quad:i=1,\ldots,k</math>
קיים פתרון יחיד מודולו <math>n=n_1\cdots n_k</math>.

בניסוח אחר, מופשט יותר, המשפט קובע שהחוג <math>\Z/(n_1\cdots n_k)\Z</math> איזומורפי לסכום הישר של החוגים <math>\Z/n_1\Z\oplus\cdots\oplus\Z/n_k\Z</math>.

===הוכחה===
רעיון ההוכחה הוא למצוא בסיס בו מודולו <math>n_i</math> הם 1 ומודולו <math>n_j</math> (כאשר <math>i\ne j</math>) הם 0. תוצאות אלה בונות בסיס למרחב הפתרונות, והפתרון המבוקש הוא צירוף ליניארי של איברי בסיס עם המקדמים החופשיים במשוואות המודולריות.

נגדיר <math>N_i=\frac{n}{n_i}</math> ואז מתקיים כי <math>n_i,N_i</math> זרים (מאחר ש-<math>n_i</math> זר לכל גורם במכפלה <math>N_i</math>). לכן לקונגרואנציה הליניארית <math>N_ix\equiv1\!\!\!\!\pmod{\!n_i}</math> קיים פתרון יחיד <math>x_i</math>.
:<math>\begin{align}&N_ix_i\equiv1\!\!\!\!\pmod{\!n_i}\\&N_ix_i\equiv0\!\!\!\!\pmod{\!n_j}\quad:i\ne j\end{align}</math>
בנינו בסיס למערכת המשוואות. נסכם בעזרת הדלתא של קרונקר: 
:<math>\begin{align}N_ix_i\equiv\delta_{ij}\!\!\!\!\pmod{\!n_j}\\x=\sum_{i\,=\,1}^ka_iN_ix_i\equiv\sum_{i\,=\,1}^ka_i\delta_{ij}\equiv a_j\!\!\!\!\pmod{\!n_j}\end{align}</math> 

לסיום, יהי <math>y</math> פתרון אחר. אזי לכל <math>i</math> מתקיים כי <math>n_i\mid(x-y)</math> ומאחר שכל ה-<math>n_i</math> זרים נובע שגם <math>n\mid(x-y)</math>, ומכאן ששני הפתרונות שקולים מודולו <math>n</math>.

בכך הסתיימה ההוכחה, שמציגה גם אלגוריתם מהיר לפתרון מערכת קונגרואנציות. <math>\blacksquare</math>

===דוגמה===
נפתור את מערכת המשוואות הבאה:
:<math display=block>\begin{matrix}\color{blue}x\equiv1\!\pmod{\!3}\\\color{blue}x\equiv2\!\pmod{\!4}\\\color{blue}x\equiv3\!\pmod{\!5}\\\\N_1=4\cdot5=20\\N_2=3\cdot5=15\\N_3=3\cdot4=12\\\\N_1x_1=20\cdot2=40\equiv1\!\pmod{\!3}\\N_2x_2=15\cdot3=45\equiv1\!\pmod{\!4}\\N_3x_3=12\cdot3=36\equiv1\!\pmod{\!5}\\\\x=1\cdot20\cdot2+2\cdot15\cdot3+3\cdot12\cdot3=238\equiv58\!\pmod{\!60}\end{matrix}</math>
נוודא שזהו אכן פתרון:
:<math>\begin{matrix}58\equiv1\!\pmod{\!3}\\58\equiv2\!\pmod{\!4}\\58\equiv3\!\pmod{\!5}\end{matrix}</math>

===מסקנה: האיזומורפיזם בין החוגים===
מסקנה של המשפט היא כי <math>\Z/(n_1\cdots n_k)\Z\cong\Z/n_1\Z\oplus\cdots\oplus\Z/n_k\Z</math>.

יהי <math>x\in\Z/(n_1\cdots n_k)\Z</math>, אפשר לשכן אותו ב-<math>\Z/n_1\Z\oplus\cdots\oplus\Z/n_k\Z</math> על ידי
:<math>x\mapsto(x\bmod n_1,\ldots,x\bmod n_k)</math>
ובכיוון ההפוך, יהי <math>(a_1,\ldots,a_k)\in\Z/n_1\Z\oplus\cdots\oplus\Z/n_k\Z</math>. לפי משפט השאריות הסיני קיים <math>x\in\Z/(n_1\cdots n_k)\Z</math> כך שמתקיים <math>\forall j=1,\ldots,k:x\equiv a_j\pmod{n_j}</math>, ולכן נתאים
:<math>(a_1,\ldots,a_k)\mapsto x</math>
כאשר x הוא זה שמתקבל ממשפט השאריות הסיני והוא יחיד עד כדי מודולו <math>n=n_1\cdots n_k</math>.

שתי ההתאמות הללו הן הומומורפיזמים הופכיים אחד של השני ולכן מגדירות איזומורפיזם בין שני החוגים.

==גרסה כללית==
יהי <math>R</math> חוג עם יחידה (לאו דווקא קומוטטיבי). נניח כי האידיאלים <math>I_1,\ldots,I_k</math> זרים בזוגות (או "מקסימליים הדדית"), כלומר <math>I_i+I_j=R</math> לכל <math>i\ne j</math>. אז חוג המנה <math>R/(I_1\cap\cdots\cap I_k)</math> איזומורפי, לפי ההטלה הטבעית, לסכום הישר של החוגים <math>R/I_1\oplus\cdots\oplus R/I_k</math>. בפרט, אם <math>R</math> קומוטטיבי והאידיאלים <math>I_1,\ldots,I_k</math> כולם אידיאלים מקסימליים ושונים זה מזה, אז <math>R/(I_1\cap\cdots\cap I_k)</math> הוא מכפלה ישרה של שדות.

==קישורים חיצוניים==
*[http://howmath.wiki.co.il/index.php/משפט_השאריות_הסיני משפט השאריות הסיני] באתר howMath 
*
*
*
*

שאריות הסיני
קטגוריה:תורת החוגים
שאריות הסיני
קטגוריה:חשבון מודולרי