Kineski teorem o ostatcima (eng. Chinese Remainder Theorem – CRT) govori o rješenju sustava linearnih kongruencija .
Za ovaj se teorem veže ime kineskog matematičara Sun Tzua. Smatra se da je teorem tada korišten u kineskoj vojsci za prebrojavanje vojnika. Ipak, u potpunosti ga je iskazao tek 1247. godine Kinez Qin Jiushao.[1]
Moderni iskaz teorema glasi ovako.
Neka su
m
1
,
m
2
,
.
.
.
,
m
r
{\displaystyle m_{1},m_{2},...,m_{r}}
u parovima relativno prosti brojevi te neka su
a
1
,
a
2
,
.
.
.
,
a
r
∈
Z
.
{\displaystyle a_{1},a_{2},...,a_{r}\in \mathbb {Z} .}
Tada sustav kongruencija
x
≡
a
1
(
mod
m
1
)
,
.
.
.
,
x
≡
a
r
(
mod
m
r
)
{\displaystyle x\equiv a_{1}{\pmod {m_{1}}},...,x\equiv a_{r}{\pmod {m_{r}}}}
ima rješenja.
Uz to, ako je
x
0
{\displaystyle x_{0}}
jedno rješenje sustava, onda su sva rješenja tog sustava dana s
x
≡
x
0
(
mod
m
1
m
2
⋅
.
.
.
⋅
m
r
)
{\displaystyle x\equiv x_{0}{\pmod {m_{1}m_{2}\cdot ...\cdot m_{r}}}}
.
Neka je
m
=
m
1
m
2
⋅
.
.
.
⋅
m
r
{\displaystyle m=m_{1}m_{2}\cdot ...\cdot m_{r}}
te neka je
n
j
=
m
m
j
{\displaystyle n_{j}={\frac {m}{m_{j}}}}
za
j
=
1
,
2
,
.
.
.
,
r
.
{\displaystyle j=1,2,...,r.}
Zbog uvjeta da su
m
1
,
m
2
,
.
.
.
,
m
r
{\displaystyle m_{1},m_{2},...,m_{r}}
u provima relativno prosti, imamo da je
M
(
m
j
,
n
j
)
=
1
{\displaystyle M(m_{j},n_{j})=1}
pa postoji
x
j
∈
Z
{\displaystyle x_{j}\in \mathbb {Z} }
takav da je
n
j
x
j
≡
a
j
(
mod
m
j
)
.
{\displaystyle n_{j}x_{j}\equiv a_{j}{\pmod {m_{j}}}.}
Promotrimo sada broj
x
0
=
n
1
x
1
+
.
.
.
+
n
r
x
r
.
{\displaystyle x_{0}=n_{1}x_{1}+...+n_{r}x_{r}.}
Za njega vrijedi
x
0
=
0
+
0
+
n
j
x
j
+
0
+
.
.
.
+
0
≡
a
j
(
mod
m
j
)
.
{\displaystyle x_{0}=0+0+n_{j}x_{j}+0+...+0\equiv a_{j}{\pmod {m_{j}}}.}
Zato je
x
0
{\displaystyle x_{0}}
rješenje sustava kongruencija s kojim smo počeli.
Konačno, ako su
x
,
x
0
{\displaystyle x,x_{0}}
dva rješenja tog sustava, onda je
x
≡
x
0
(
mod
m
1
)
{\displaystyle x\equiv x_{0}{\pmod {m_{1}}}}
za
j
=
1
,
2
,
.
.
.
,
r
{\displaystyle j=1,2,...,r}
. Zbog toga što su
m
j
{\displaystyle m_{j}}
u parovima relativno prosti, dobivamo da je
x
≡
x
0
(
mod
m
)
.
{\displaystyle x\equiv x_{0}{\pmod {m}}.}
[2]