Formularea originală a luiSun-tzu : sistemul:x ≡ 2 ( mod 3 ) {\displaystyle x\equiv 2{\pmod {3}}} x ≡ 3 ( mod 5 ) {\displaystyle x\equiv 3{\pmod {5}}} x ≡ 2 ( mod 7 ) {\displaystyle x\equiv 2{\pmod {7}}} x = 23 + 105 k {\displaystyle x=23+105k} k ∈ Z {\displaystyle k\in \mathbb {Z} } Teorema chinezească a resturilor este un rezultat provenit dinteoria numerelor , cu aplicații încriptografie . Teorema a fost cunoscută de matematicieniichinezi dinsecolul al III-lea , apărând într-o carte a matematicianului Sunzi înSunzi Suanjing , iar apoi, în1247 , într-o altă carte a luiQin Jiushao .
Dacăm 1 , m 2 , . . . , m n {\displaystyle m_{1},m_{2},...,m_{n}} întregi prime între ele două câte două, atunci, pentru orice numere întregia 1 , a 2 , . . . , a n {\displaystyle a_{1},a_{2},...,a_{n}} x {\displaystyle x} [ 1]
x ≡ a 1 ( mod m 1 ) x ≡ a 2 ( mod m 2 ) ⋮ x ≡ a k ( mod m k ) {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {m_{1}}}\\x&\equiv a_{2}{\pmod {m_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {m_{k}}}\end{aligned}}} Pentru a rezolva sistemul, definim mai întâi notațiax m − 1 {\displaystyle x_{m}^{-1}} inversul modular al luix {\displaystyle x} m {\displaystyle m} x , m ∈ Z {\displaystyle x,m\in \mathbb {Z} } X k = M m k {\displaystyle X_{k}={\frac {M}{m_{k}}}} k = 1 , n ¯ {\displaystyle k={\overline {1,n}}} M = m 1 ∗ m 2 ∗ . . . ∗ m n {\displaystyle M={m_{1}*m_{2}*...*m_{n}}} x = a 1 X 1 X 1 m 1 − 1 + a 2 X 2 X 2 m 2 − 1 + . . . + a n X n X n m n − 1 = ∑ k = 1 n a k X k X k m k − 1 {\displaystyle x=a_{1}X_{1}{X_{1}}_{m_{1}}^{-1}+a_{2}X_{2}{X_{2}}_{m_{2}}^{-1}+...+a_{n}X_{n}{X_{n}}_{m_{n}}^{-1}=\sum _{k=1}^{n}{a_{k}X_{k}{X_{k}}_{m_{k}}^{-1}}} a k X k X k m k − 1 {\displaystyle {a_{k}X_{k}{X_{k}}_{m_{k}}^{-1}}} a k ( mod m k ) {\displaystyle a_{k}({\text{mod }}m_{k})} X k X k m k − 1 ≡ 1 ( mod m k ) {\displaystyle {X_{k}{X_{k}}_{m_{k}}^{-1}}\equiv 1({\text{mod }}m_{k})} a i X i X i m i − 1 {\displaystyle {a_{i}X_{i}{X_{i}}_{m_{i}}^{-1}}} i ≠ k {\displaystyle i\neq k} X i = m 1 m 2 . . . m n m i {\displaystyle X_{i}={\frac {m_{1}m_{2}...m_{n}}{m_{i}}}} multiplu dem k {\displaystyle m_{k}} S = { x + k M | k ∈ Z } {\displaystyle S=\{x+kM\,\,|\,\,k\in \mathbb {Z} \}}
Să considerăm sistemul:
x ≡ 3 ( mod 5 ) x ≡ 4 ( mod 7 ) x ≡ 2 ( mod 3 ) {\displaystyle {\begin{aligned}x&\equiv 3{\pmod {5}}\\x&\equiv 4{\pmod {7}}\\x&\equiv 2{\pmod {3}}\end{aligned}}}
Conform formuleix = ∑ k = 1 n a k X k X k m k − 1 {\displaystyle x=\sum _{k=1}^{n}{a_{k}X_{k}{X_{k}}_{m_{k}}^{-1}}} x = 3 ∗ 21 ∗ 1 + 4 ∗ 15 ∗ 1 + 2 ∗ 35 ∗ 2 = 263 {\displaystyle x=3*21*1+4*15*1+2*35*2=263} x = 263 + 105 k {\displaystyle x=263+105k}
Relațiax ≡ y ( mod m i ) {\displaystyle x\equiv y{\pmod {m_{i}}}} 1 ≤ i ≤ n {\displaystyle 1\leq i\leq n} dacă și numai dacă x ≡ y ( mod M ) {\displaystyle x\equiv y{\pmod {M}}} m i {\displaystyle m_{i}}
a i ≡ a j ( mod c m m d c ( m i , m j ) ) ∀ 1 ≤ i , j ≤ n {\displaystyle a_{i}\equiv a_{j}{\pmod {cmmdc(m_{i},m_{j})}}\,\,\,\,\forall \,1\leq i,\,j\leq n\,\!}
Toate soluțiilex {\displaystyle x} cel mai mic multiplu comun al numerelorm i {\displaystyle m_{i}}
M = c m m m c ( m 1 , m 2 , . . . , m n ) {\displaystyle M=cmmmc(m_{1},m_{2},...,m_{n})}
Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott.Handbook of Applied Cryptography . 
