יהיו
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}}
n
j
{\displaystyle n_{j}}
i
≠
j
{\displaystyle i\neq j}
נגדיר
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})}
מכפלה ישרה של שדות.
