יהיו n 1 , … , n k {\displaystyle n_{1},\ldots ,n_{k}} מספרים טבעיים זרים בזוגות (כלומר המחלק המשותף המקסימלי של כל שניים מהם הוא 1). יהיו a 1 , … , a k {\displaystyle a_{1},\ldots ,a_{k}} מספרים שלמים כאשר 0 ≤ a i ≤ n i − 1 {\displaystyle 0\leq a_{i}\leq n_{i}-1} . אזי למערכת המשוואות
x ≡ a i ( mod n i ) : i = 1 , … , k {\displaystyle x\equiv a_{i}\!\!\!\!{\pmod {\!n_{i}}}\quad :i=1,\ldots ,k} קיים פתרון יחיד מודולו n = n 1 ⋯ n k {\displaystyle n=n_{1}\cdots n_{k}} .
בניסוח אחר, מופשט יותר, המשפט קובע שהחוג Z / ( n 1 ⋯ n k ) Z {\displaystyle \mathbb {Z} /(n_{1}\cdots n_{k})\mathbb {Z} } איזומורפי לסכום הישר של החוגים Z / n 1 Z ⊕ ⋯ ⊕ Z / n k Z {\displaystyle \mathbb {Z} /n_{1}\mathbb {Z} \oplus \cdots \oplus \mathbb {Z} /n_{k}\mathbb {Z} } .
הוכחה רעיון ההוכחה הוא למצוא בסיס בו מודולו n i {\displaystyle n_{i}} הם 1 ומודולו n j {\displaystyle n_{j}} (כאשר i ≠ j {\displaystyle i\neq j} ) הם 0. תוצאות אלה בונות בסיס למרחב הפתרונות, והפתרון המבוקש הוא צירוף ליניארי של איברי בסיס עם המקדמים החופשיים במשוואות המודולריות.
נגדיר N i = n n i {\displaystyle N_{i}={\frac {n}{n_{i}}}} ואז מתקיים כי n i , N i {\displaystyle n_{i},N_{i}} זרים (מאחר ש- n i {\displaystyle n_{i}} זר לכל גורם במכפלה N i {\displaystyle N_{i}} ). לכן לקונגרואנציה הליניארית N i x ≡ 1 ( mod n i ) {\displaystyle N_{i}x\equiv 1\!\!\!\!{\pmod {\!n_{i}}}} קיים פתרון יחיד x i {\displaystyle x_{i}} .
N i x i ≡ 1 ( mod n i ) N i x i ≡ 0 ( mod n j ) : i ≠ j {\displaystyle {\begin{aligned}&N_{i}x_{i}\equiv 1\!\!\!\!{\pmod {\!n_{i}}}\\&N_{i}x_{i}\equiv 0\!\!\!\!{\pmod {\!n_{j}}}\quad :i\neq j\end{aligned}}} בנינו בסיס למערכת המשוואות. נסכם בעזרת הדלתא של קרונקר :
N i x i ≡ δ i j ( mod n j ) x = ∑ i = 1 k a i N i x i ≡ ∑ i = 1 k a i δ i j ≡ a j ( mod n j ) {\displaystyle {\begin{aligned}N_{i}x_{i}\equiv \delta _{ij}\!\!\!\!{\pmod {\!n_{j}}}\\x=\sum _{i\,=\,1}^{k}a_{i}N_{i}x_{i}\equiv \sum _{i\,=\,1}^{k}a_{i}\delta _{ij}\equiv a_{j}\!\!\!\!{\pmod {\!n_{j}}}\end{aligned}}} לסיום, יהי y {\displaystyle y} פתרון אחר. אזי לכל i {\displaystyle i} מתקיים כי n i ∣ ( x − y ) {\displaystyle n_{i}\mid (x-y)} ומאחר שכל ה- n i {\displaystyle n_{i}} זרים נובע שגם n ∣ ( x − y ) {\displaystyle n\mid (x-y)} , ומכאן ששני הפתרונות שקולים מודולו n {\displaystyle n} .
בכך הסתיימה ההוכחה, שמציגה גם אלגוריתם מהיר לפתרון מערכת קונגרואנציות. ◼ {\displaystyle \blacksquare }
דוגמה נפתור את מערכת המשוואות הבאה:
x ≡ 1 ( mod 3 ) x ≡ 2 ( mod 4 ) x ≡ 3 ( mod 5 ) N 1 = 4 ⋅ 5 = 20 N 2 = 3 ⋅ 5 = 15 N 3 = 3 ⋅ 4 = 12 N 1 x 1 = 20 ⋅ 2 = 40 ≡ 1 ( mod 3 ) N 2 x 2 = 15 ⋅ 3 = 45 ≡ 1 ( mod 4 ) N 3 x 3 = 12 ⋅ 3 = 36 ≡ 1 ( mod 5 ) x = 1 ⋅ 20 ⋅ 2 + 2 ⋅ 15 ⋅ 3 + 3 ⋅ 12 ⋅ 3 = 238 ≡ 58 ( mod 60 ) {\displaystyle {\begin{matrix}\color {blue}x\equiv 1\!{\pmod {\!3}}\\\color {blue}x\equiv 2\!{\pmod {\!4}}\\\color {blue}x\equiv 3\!{\pmod {\!5}}\\\\N_{1}=4\cdot 5=20\\N_{2}=3\cdot 5=15\\N_{3}=3\cdot 4=12\\\\N_{1}x_{1}=20\cdot 2=40\equiv 1\!{\pmod {\!3}}\\N_{2}x_{2}=15\cdot 3=45\equiv 1\!{\pmod {\!4}}\\N_{3}x_{3}=12\cdot 3=36\equiv 1\!{\pmod {\!5}}\\\\x=1\cdot 20\cdot 2+2\cdot 15\cdot 3+3\cdot 12\cdot 3=238\equiv 58\!{\pmod {\!60}}\end{matrix}}} נוודא שזהו אכן פתרון:
58 ≡ 1 ( mod 3 ) 58 ≡ 2 ( mod 4 ) 58 ≡ 3 ( mod 5 ) {\displaystyle {\begin{matrix}58\equiv 1\!{\pmod {\!3}}\\58\equiv 2\!{\pmod {\!4}}\\58\equiv 3\!{\pmod {\!5}}\end{matrix}}} מסקנה: האיזומורפיזם בין החוגים מסקנה של המשפט היא כי Z / ( n 1 ⋯ n k ) Z ≅ Z / n 1 Z ⊕ ⋯ ⊕ Z / n k Z {\displaystyle \mathbb {Z} /(n_{1}\cdots n_{k})\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \oplus \cdots \oplus \mathbb {Z} /n_{k}\mathbb {Z} } .
יהי x ∈ Z / ( n 1 ⋯ n k ) Z {\displaystyle x\in \mathbb {Z} /(n_{1}\cdots n_{k})\mathbb {Z} } , אפשר לשכן אותו ב- Z / n 1 Z ⊕ ⋯ ⊕ Z / n k Z {\displaystyle \mathbb {Z} /n_{1}\mathbb {Z} \oplus \cdots \oplus \mathbb {Z} /n_{k}\mathbb {Z} } על ידי
x ↦ ( x mod n 1 , … , x mod n k ) {\displaystyle x\mapsto (x{\bmod {n}}_{1},\ldots ,x{\bmod {n}}_{k})} ובכיוון ההפוך, יהי ( a 1 , … , a k ) ∈ Z / n 1 Z ⊕ ⋯ ⊕ Z / n k Z {\displaystyle (a_{1},\ldots ,a_{k})\in \mathbb {Z} /n_{1}\mathbb {Z} \oplus \cdots \oplus \mathbb {Z} /n_{k}\mathbb {Z} } . לפי משפט השאריות הסיני קיים x ∈ Z / ( n 1 ⋯ n k ) Z {\displaystyle x\in \mathbb {Z} /(n_{1}\cdots n_{k})\mathbb {Z} } כך שמתקיים ∀ j = 1 , … , k : x ≡ a j ( mod n j ) {\displaystyle \forall j=1,\ldots ,k:x\equiv a_{j}{\pmod {n_{j}}}} , ולכן נתאים
( a 1 , … , a k ) ↦ x {\displaystyle (a_{1},\ldots ,a_{k})\mapsto x} כאשר x הוא זה שמתקבל ממשפט השאריות הסיני והוא יחיד עד כדי מודולו n = n 1 ⋯ n k {\displaystyle n=n_{1}\cdots n_{k}} .
שתי ההתאמות הללו הן הומומורפיזמים הופכיים אחד של השני ולכן מגדירות איזומורפיזם בין שני החוגים.
יהי R {\displaystyle R} חוג עם יחידה (לאו דווקא קומוטטיבי). נניח כי האידיאלים I 1 , … , I k {\displaystyle I_{1},\ldots ,I_{k}} זרים בזוגות (או "מקסימליים הדדית"), כלומר I i + I j = R {\displaystyle I_{i}+I_{j}=R} לכל i ≠ j {\displaystyle i\neq j} . אז חוג המנה R / ( I 1 ∩ ⋯ ∩ I k ) {\displaystyle R/(I_{1}\cap \cdots \cap I_{k})} איזומורפי, לפי ההטלה הטבעית, לסכום הישר של החוגים R / I 1 ⊕ ⋯ ⊕ R / I k {\displaystyle R/I_{1}\oplus \cdots \oplus R/I_{k}} . בפרט, אם R {\displaystyle R} קומוטטיבי והאידיאלים I 1 , … , I k {\displaystyle I_{1},\ldots ,I_{k}} כולם אידיאלים מקסימליים ושונים זה מזה, אז R / ( I 1 ∩ ⋯ ∩ I k ) {\displaystyle R/(I_{1}\cap \cdots \cap I_{k})} הוא מכפלה ישרה של שדות.