Մնացորդների մասին չինական թեորեմ

Մնացորդների մասին չինական թեորեմ, մի քանի գծային համակարգի կապակցված պնդումների համեմատում։


== Պատմություն ==
Այս թեորեմը իր թվաբանական ձևակերպմամբ նկարագրվել է չինական մաթեմատիկոս Սուն Ցզիի «Սուն Ցզի Սուան Ցզին» տրակտատում (չինարեն՝ 孙子算经), մոտավորապես թվագրվել է մ․թ․ա երրորդ դարում և այնուհետև ընդհանրացվել է Ցին Ցզյուշաոյի կողմից իր «Մաթեմատիկական դատողություններ 9 գլխով», տպագրված 1247 թվականին, որտեղ բերված էր ճշգրիտ լուծումը։


== Ձևակերպում ==
Եթե 
  
    
      
        
          a
          
            1
          
        
        ,
        
          a
          
            2
          
        
        ,
        …
        ,
        
          a
          
            n
          
        
      
    
    {\displaystyle a_{1},a_{2},\dots ,a_{n}}
   բնական թվերը զույգ առ զույգ փոխադարձ պարզ են, ապա ցանկացած ամբողջ 
  
    
      
        
          r
          
            1
          
        
        ,
        
          r
          
            2
          
        
        ,
        …
        ,
        
          r
          
            n
          
        
      
    
    {\displaystyle r_{1},r_{2},\dots ,r_{n}}
   այնպիսին է, որ 
  
    
      
        0
        ⩽
        
          r
          
            i
          
        
        <
        
          a
          
            i
          
        
      
    
    {\displaystyle 0\leqslant r_{i}<a_{i}}
   բոլոր 
  
    
      
        i
        ∈
        {
        1
        ,
        2
        ,
        …
        ,
        n
        }
        ,
      
    
    {\displaystyle i\in \{1,2,\dots ,n\},}
   համար կգտնվի 
  
    
      
        N
      
    
    {\displaystyle N}
  , որը 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
   վրա բաժանելիս տալիս է 
  
    
      
        
          r
          
            i
          
        
      
    
    {\displaystyle r_{i}}
   մնացորդ բոլոր 
  
    
      
        i
        ∈
        {
        1
        ,
        2
        ,
        …
        ,
        n
        }
      
    
    {\displaystyle i\in \{1,2,\dots ,n\}}
   համար։ Ավելին, եթե գտնվեն այնպիսի երկու՝ 
  
    
      
        
          N
          
            1
          
        
      
    
    {\displaystyle N_{1}}
   և 
  
    
      
        
          N
          
            2
          
        
      
    
    {\displaystyle N_{2}}
  , ապա 
  
    
      
        
          N
          
            1
          
        
        ≡
        
          N
          
            2
          
        
        
          
          (
          mod
          
          
            a
            
              1
            
          
          ⋅
          
            a
            
              2
            
          
          ⋅
          …
          ⋅
          
            a
            
              n
            
          
          )
        
      
    
    {\displaystyle N_{1}\equiv N_{2}{\pmod {a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}}}
  ։


== Ապացույցներ ==


=== Ինդդուկցիա հավասարումների քանակով ===
Օգտվենք մաթեմատիկական ինդուկցիայի մեթոդից։ 
  
    
      
        n
        =
        1
      
    
    {\displaystyle n=1}
   դեպքում թեորեմի պնդումը ակնհայտ է։
Թող թեորեմը ճշմարիտ լինի 
  
    
      
        n
        =
        k
        −
        1
      
    
    {\displaystyle n=k-1}
   դեպքում, ապա գոյություն ունի 
  
    
      
        m
      
    
    {\displaystyle m}
   թիվը, որը 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
   
  
    
      
        i
        ∈
        {
        1
        ,
        2
        ,
        …
        ,
        k
        −
        1
        }
      
    
    {\displaystyle i\in \{1,2,\dots ,k-1\}}
   դեպքում թվի վրա բաժանելիս տալիս է 
  
    
      
        
          r
          
            i
          
        
      
    
    {\displaystyle r_{i}}
   մնացորդը։ Նշանակենք

  
    
      
        d
        =
        
          a
          
            1
          
        
        ⋅
        
          a
          
            2
          
        
        ⋅
        …
        ⋅
        
          a
          
            k
            −
            1
          
        
      
    
    {\displaystyle d=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{k-1}}
  ։Ընտրում ենք 
  
    
      
        
          a
          
            k
          
        
      
    
    {\displaystyle a_{k}}
   կամայական թիվը, որը փոխադաչձ պարզ է բոլոր 
  
    
      
        
          a
          
            1
          
        
        …
        
          a
          
            k
            −
            1
          
        
      
    
    {\displaystyle a_{1}\dots a_{k-1}}
   հետ և դիտարկենք 
  
    
      
        M
        =
        {
        m
        ,
        m
        +
        d
        ,
        m
        +
        2
        d
        ,
        …
        ,
        m
        +
        (
        
          a
          
            k
          
        
        −
        1
        )
        ⋅
        d
        }
        =
        {
        m
        +
        t
        ⋅
        d
        
          }
          
            0
            ⩽
            t
            <
            
              a
              
                k
              
            
          
        
      
    
    {\displaystyle M=\{m,m+d,m+2d,\dots ,m+(a_{k}-1)\cdot d\}=\{m+t\cdot d\}_{0\leqslant t<a_{k}}}
   թվերը։Ցույց տանք, որ բոլոր 
  
    
      
        t
        ∈
        {
        0
        ,
        …
        ,
        
          a
          
            k
          
        
        −
        1
        }
      
    
    {\displaystyle t\in \{0,\dots ,a_{k}-1\}}
   հանդիսանում են մնացորդներ 
  
    
      
        M
      
    
    {\displaystyle M}
   ֊ի ինչ֊որ էլեմենտների՝ 
  
    
      
        
          a
          
            k
          
        
      
    
    {\displaystyle a_{k}}
   վրա բաժանելիս։
Ենթադրենք, որ դա այդպես չէ, այսինքն գոյություն ունեն որոշակի 
  
    
      
        
          r
          
            k
          
        
        <
        
          a
          
            k
          
        
      
    
    {\displaystyle r_{k}<a_{k}}
  , որոնք չեն պատկանում 
  
    
      
        M
      
    
    {\displaystyle M}
   էլեմենտների՝ 
  
    
      
        
          a
          
            k
          
        
      
    
    {\displaystyle a_{k}}
   վրա բաժանելիս ստացված մնացորդների բազմությանը։Քանի որ այդ էլեմենտների թիվը հավասար է 
  
    
      
        
          |
        
        M
        
          |
        
        =
        
          a
          
            k
          
        
      
    
    {\displaystyle |M|=a_{k}}
  ,իսկ 
  
    
      
        M
      
    
    {\displaystyle M}
   ֊ի ինչ֊որ էլեմենտների՝ 
  
    
      
        
          a
          
            k
          
        
      
    
    {\displaystyle a_{k}}
   վրա բաժանելիս հնարավոր մնացորդները հնարավոր է շատ չեն, քան 
  
    
      
        
          a
          
            k
          
        
        −
        1
      
    
    {\displaystyle a_{k}-1}
   (քանի որ ոչ մի թիվ չի տալիս 
  
    
      
        
          r
          
            k
          
        
      
    
    {\displaystyle r_{k}}
   մնացորդ), ապա նրանց մեջ կգտնվեն երկու թիվ, որոնք ունեն հավասար մնացորդներ (Դիրիխլեի արկղի սկզբունք). Թող այդ թվերը լինեն 
  
    
      
        m
        +
        
          t
          
            1
          
        
        d
      
    
    {\displaystyle m+t_{1}d}
   և 
  
    
      
        m
        +
        
          t
          
            2
          
        
        d
      
    
    {\displaystyle m+t_{2}d}
   , 
  
    
      
        
          t
          
            1
          
        
        ≠
        
          t
          
            2
          
        
      
    
    {\displaystyle t_{1}\neq t_{2}}
   դեպքում. Այդ դեպքում իրենց 
  
    
      
        (
        m
        +
        
          t
          
            1
          
        
        d
        )
        −
        (
        m
        +
        
          t
          
            2
          
        
        d
        )
        =
        (
        
          t
          
            1
          
        
        −
        
          t
          
            2
          
        
        )
        d
      
    
    {\displaystyle (m+t_{1}d)-(m+t_{2}d)=(t_{1}-t_{2})d}
   տարբերությունը բաժանվում է 
  
    
      
        
          a
          
            k
          
        
      
    
    {\displaystyle a_{k}}
   վրա, ինչը հնարավոր է, քանի որ 
  
    
      
        
          t
          
            1
          
        
        <
        
          a
          
            k
          
        
      
    
    {\displaystyle t_{1}<a_{k}}
  , 
  
    
      
        
          t
          
            2
          
        
        <
        
          a
          
            k
          
        
      
    
    {\displaystyle t_{2}<a_{k}}
  , 
  
    
      
        0
        <
        
          |
        
        
          t
          
            1
          
        
        −
        
          t
          
            2
          
        
        
          |
        
        <
        
          a
          
            k
          
        
      
    
    {\displaystyle 0<|t_{1}-t_{2}|<a_{k}}
   և 
  
    
      
        d
        =
        
          a
          
            1
          
        
        ⋅
        
          a
          
            2
          
        
        ⋅
        …
        ⋅
        
          a
          
            k
            −
            1
          
        
      
    
    {\displaystyle d=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{k-1}}
   
  
    
      
        
          a
          
            k
          
        
      
    
    {\displaystyle a_{k}}
   հետ փոխադարձ պարզ են, այլապես 
  
    
      
        
          a
          
            1
          
        
        ,
        
          a
          
            2
          
        
        ,
        …
        ,
        
          a
          
            k
          
        
      
    
    {\displaystyle a_{1},a_{2},\dots ,a_{k}}
   թվերը զույգ առ զույգ փոխադարձ պարզ են (ըստ պայմանի). Հակասություն։
Այսպիսով, դիտարկվող թվերի մեջ կգտնվի math>N = m + t\cdot d</math> թիվ, որը 
  
    
      
        
          a
          
            k
          
        
      
    
    {\displaystyle a_{k}}
   վրա բաժանելիս տալիս է 
  
    
      
        
          r
          
            k
          
        
      
    
    {\displaystyle r_{k}}
   մնացորդ. Միևնույն ժամանակ 
  
    
      
        
          a
          
            1
          
        
        ,
        
          a
          
            2
          
        
        ,
        …
        ,
        
          a
          
            k
            −
            1
          
        
      
    
    {\displaystyle a_{1},a_{2},\dots ,a_{k-1}}
   վրա բաժանելիս 
  
    
      
        N
      
    
    {\displaystyle N}
   թիվը համապատասխանաբար տալիս է 
  
    
      
        
          r
          
            1
          
        
        ,
        
          r
          
            2
          
        
        ,
        …
        ,
        
          r
          
            k
            −
            1
          
        
      
    
    {\displaystyle r_{1},r_{2},\dots ,r_{k-1}}
   մնացորդ,քանի որ 
  
    
      
        m
        +
        t
        ⋅
        d
        ≡
        m
        
          
          (
          mod
          
          
            a
            
              i
            
          
          )
        
      
    
    {\displaystyle m+t\cdot d\equiv m{\pmod {a_{i}}}}
  ։
Այժմ ապացուցենք, որ 
  
    
      
        
          N
          
            1
          
        
        ≡
        
          N
          
            2
          
        
        
          
          (
          mod
          
          
            a
            
              1
            
          
          ⋅
          
            a
            
              2
            
          
          ⋅
          …
          ⋅
          
            a
            
              n
            
          
          )
        
      
    
    {\displaystyle N_{1}\equiv N_{2}{\pmod {a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}}}
  .
Իրականում 
  
    
      
        
          N
          
            1
          
        
        ≡
        
          N
          
            2
          
        
        ≡
        
          r
          
            i
          
        
        
          
          (
          mod
          
          
            a
            
              i
            
          
          )
        
      
    
    {\displaystyle N_{1}\equiv N_{2}\equiv r_{i}{\pmod {a_{i}}}}
  , այսինքն

  
    
      
        
          N
          
            1
          
        
        −
        
          N
          
            2
          
        
        ≡
        0
        
          
          (
          mod
          
          
            a
            
              i
            
          
          )
        
      
    
    {\displaystyle N_{1}-N_{2}\equiv 0{\pmod {a_{i}}}}
  . այսպիսով, 
  
    
      
        
          N
          
            1
          
        
        −
        
          N
          
            2
          
        
      
    
    {\displaystyle N_{1}-N_{2}}
   թիվը բոլոր 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
   բաժանում է առանց մնացորդի, ինչպես նաև իրենց արտադրյալները։ Ինչն էլ պահանջվում էր ապացուցել։


=== Ապացույցի կոնստրուկտիվ մեթոդ ===
Ներքևում նկարագրված թեորեմի ապացույցը օգնում է լուծել պրակտիկորեն կարևոր խնդիր՝ մոդուլով դծային հավասարումների համակարգի լուծման որոնում։.
Դիտարկենք 

 հավասարումների համակարգը։
Եթե 
  
    
      
        (
        
          r
          
            1
          
        
        ,
        
          r
          
            2
          
        
        ,
        …
        ,
        
          r
          
            n
          
        
        )
      
    
    {\displaystyle (r_{1},r_{2},\dots ,r_{n})}
   և 
  
    
      
        (
        
          a
          
            1
          
        
        ,
        
          a
          
            2
          
        
        ,
        …
        ,
        
          a
          
            n
          
        
        )
      
    
    {\displaystyle (a_{1},a_{2},\dots ,a_{n})}
   բավարարում են թեորեմի պայմաններին, ապա (1)համակարգի լուծումը գոյություն ունի և 
  
    
      
        M
      
    
    {\displaystyle M}
   մոդուլով ճշտությամբ միակն է, որտեղ 
  
    
      
        M
        =
        
          
            
              ∏
              
                i
                =
                1
              
              
                n
              
            
            
              a
              
                i
              
            
          
        
      
    
    {\displaystyle M={\displaystyle \prod _{i=1}^{n}a_{i}}}
  , ընդ որում ճշմարիտ է բանաձևը
Ցույց տանք, որ այդ եղանակով որոշված 
  
    
      
        x
      
    
    {\displaystyle x}
   ֊ը հանդիսանում է լուծում։ Ստուգենք, որ նրա համար համակարգումգործում է i-е հավասարությունը։

  
    
      
        x
        ≡
        
          ∑
          
            j
            =
            1
          
          
            n
          
        
        
          r
          
            j
          
        
        
          M
          
            j
          
        
        
          M
          
            j
          
          
            −
            1
          
        
        ≡
        
          r
          
            i
          
        
        
          M
          
            i
          
        
        
          M
          
            i
          
          
            −
            1
          
        
        ≡
        
          r
          
            i
          
        
        
          
          (
          mod
          
          
            a
            
              i
            
          
          )
        
      
    
    {\displaystyle x\equiv \sum _{j=1}^{n}r_{j}M_{j}M_{j}^{-1}\equiv r_{i}M_{i}M_{i}^{-1}\equiv r_{i}{\pmod {a_{i}}}}
  
Երկրորդ հավասարությունը ճշմարիտ է, քանի որ 
  
    
      
        
          M
          
            j
          
        
        ≡
        
          
            
              ∏
              
                k
                ≠
                j
              
              
                n
              
            
            
              a
              
                k
              
            
          
        
        ≡
        0
        
          
          (
          mod
          
          
            a
            
              i
            
          
          )
        
      
    
    {\displaystyle M_{j}\equiv {\displaystyle \prod _{k\neq j}^{n}a_{k}}\equiv 0{\pmod {a_{i}}}}
   , բոլոր 
  
    
      
        i
        ≠
        j
      
    
    {\displaystyle i\neq j}
   դեպքում, երրորդը, քանի որ 
  
    
      
        
          M
          
            i
          
          
            −
            1
          
        
      
    
    {\displaystyle M_{i}^{-1}}
   հանդիսանում է հակադարձ 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
   մոդուլով 
  
    
      
        
          M
          
            i
          
        
      
    
    {\displaystyle M_{i}}
   համար։ Բոլոր 
  
    
      
        i
      
    
    {\displaystyle i}
   համար կրկնելով դատողությունը, համոզվենք, որ (2) բանաձևով որոշված 
  
    
      
        x
      
    
    {\displaystyle x}
   ֊ը հանդիսանում է լուծում (1) համար։
Բոլոր 
  
    
      
        
          x
          ′
        
        ≡
        x
        
          
          (
          mod
          
          M
          )
        
      
    
    {\displaystyle x'\equiv x{\pmod {M}}}
   թվերը, ընտրված 
  
    
      
        M
      
    
    {\displaystyle M}
   թվի համաձայն,կբավարարեն համակարգին։
Այժմ ցույց տանք, որ 
  
    
      
        0
        ,
        1
        ,
        …
        ,
        M
        −
        1
      
    
    {\displaystyle 0,1,\dots ,M-1}
   (բազմություն 
  
    
      
        A
      
    
    {\displaystyle A}
  ) թվերի մեջ մեր գտած լուծումից բացի ուրիշ լուծում չի գտնվի։ Այդ փաստի հակառակ ապացույցը։ Ենթադրենք, որ հաջողվել է մնացորդների որոշակի 
  
    
      
        r
      
    
    {\displaystyle r}
   հավաքածուի համար գտնել գոնե երկու՝ 
  
    
      
        
          x
          
            1
          
        
        ,
        
          x
          
            2
          
        
        ∈
        A
      
    
    {\displaystyle x_{1},x_{2}\in A}
   լուծում։ Քանի որ բոլոր թույլատրելի 
  
    
      
        (
        
          r
          
            1
          
        
        ,
        
          r
          
            2
          
        
        ,
        …
        ,
        
          r
          
            n
          
        
        )
      
    
    {\displaystyle (r_{1},r_{2},\dots ,r_{n})}
   հավաքածուների բազմությունը հանդիսանում է հավասարահզոր 
  
    
      
        A
      
    
    {\displaystyle A}
   բազմությանը, ապա 
  
    
      
        
          
            
              A
              ¯
            
          
          
            x
          
        
        :=
        A
        ∖
        {
        
          x
          
            1
          
        
        ,
        
          x
          
            2
          
        
        }
      
    
    {\displaystyle {\overline {A}}_{x}:=A\setminus \{x_{1},x_{2}\}}
   և 
  
    
      
        
          
            
              B
              ¯
            
          
          
            r
          
        
        :=
        B
        ∖
        {
        r
        }
      
    
    {\displaystyle {\overline {B}}_{r}:=B\setminus \{r\}}
   համար գործում է 
  
    
      
        
          |
        
        
          
            
              A
              ¯
            
          
          
            x
          
        
        
          |
        
        <
        
          |
        
        
          
            
              B
              ¯
            
          
          
            r
          
        
        
          |
        
      
    
    {\displaystyle |{\overline {A}}_{x}|<|{\overline {B}}_{r}|}
  ։ Սակայն, վերը ապացուցվածի համաձայն, 
  
    
      
        
          
            
              B
              ¯
            
          
          
            r
          
        
      
    
    {\displaystyle {\overline {B}}_{r}}
   ֊ի ցանկացաց հավաքածուի համար գոյություն ունի 
  
    
      
        
          
            
              A
              ¯
            
          
          
            x
          
        
      
    
    {\displaystyle {\overline {A}}_{x}}
   ֊ից լուծում, հետևաբար Դիրիխլեի սկզբունքի համաձայն կգտնվեն ամենաքիչը երկու մնացորդների հավաքածուներ, որոնց համապատասխանում է նույն 
  
    
      
        x
        ∈
        A
      
    
    {\displaystyle x\in A}
   ֊ն։ Այդպիսի 
  
    
      
        x
      
    
    {\displaystyle x}
   ֊ի համար կգտնվի այնպիսի 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
  , որ 
  
    
      
        x
        ≡
        
          r
          
            1
          
        
        ,
        x
        ≡
        
          r
          
            2
          
        
        
          
          (
          mod
          
          
            a
            
              i
            
          
          )
        
      
    
    {\displaystyle x\equiv r_{1},x\equiv r_{2}{\pmod {a_{i}}}}
   և 
  
    
      
        
          r
          
            1
          
        
        ≠
        
          r
          
            2
          
        
      
    
    {\displaystyle r_{1}\neq r_{2}}
  . Հակասություն. Ինչն էլ պահանջվում էր ապացուցել։


=== Դիտողություն ===
Վերը ապացուցվածից հետևում է, որ 
  
    
      
        (
        
          a
          
            1
          
        
        ,
        
          a
          
            2
          
        
        ,
        …
        ,
        
          a
          
            n
          
        
        )
      
    
    {\displaystyle (a_{1},a_{2},\dots ,a_{n})}
   ցանկացած հավաքածուի 
  
    
      
        B
      
    
    {\displaystyle B}
   մնացորդների վեկտորի և 
  
    
      
        A
      
    
    {\displaystyle A}
   բազմության թվի միջև գոյություն ունի միարժեք փոխադարձ համապատասխանություն, ինչը նշանակում է, որ (2) ֊ով տրված 
  
    
      
        B
      
    
    {\displaystyle B}
   ֊ի արտապատկերումը 
  
    
      
        A
      
    
    {\displaystyle A}
   մեջ հանդիսանում է բիեկտիվ. Նկատենք, որ

  
    
      
        (
        x
        
          
          (
          mod
          
          M
          )
        
        )
        ↔
        (
        
          r
          
            1
          
        
        
          
          (
          mod
          
          
            a
            
              1
            
          
          )
        
        ,
        
          r
          
            2
          
        
        
          
          (
          mod
          
          
            a
            
              2
            
          
          )
        
        ,
        …
        ,
        
          r
          
            n
          
        
        
          
          (
          mod
          
          
            a
            
              n
            
          
          )
        
        )
      
    
    {\displaystyle (x{\pmod {M}})\leftrightarrow (r_{1}{\pmod {a_{1}}},r_{2}{\pmod {a_{2}}},\dots ,r_{n}{\pmod {a_{n}}})}
  ; համապատասխանությունից բացի
ճշմարիտ են նաև 
  
    
      
        (
        
          x
          
            1
          
        
        ±
        
          x
          
            2
          
        
        
          
          (
          mod
          
          M
          )
        
        )
        ↔
        (
        
          r
          
            11
          
        
        ±
        
          r
          
            21
          
        
        
          
          (
          mod
          
          
            a
            
              1
            
          
          )
        
        ,
        
          r
          
            12
          
        
        ±
        
          r
          
            22
          
        
        
          
          (
          mod
          
          
            a
            
              2
            
          
          )
        
        ,
        …
        ,
        
          r
          
            1
            n
          
        
        ±
        
          r
          
            2
            n
          
        
        
          
          (
          mod
          
          
            a
            
              n
            
          
          )
        
        )
      
    
    {\displaystyle (x_{1}\pm x_{2}{\pmod {M}})\leftrightarrow (r_{11}\pm r_{21}{\pmod {a_{1}}},r_{12}\pm r_{22}{\pmod {a_{2}}},\dots ,r_{1n}\pm r_{2n}{\pmod {a_{n}}})}
  ;

  
    
      
        (
        
          x
          
            1
          
        
        
          x
          
            2
          
        
        
          
          (
          mod
          
          M
          )
        
        )
        ↔
        (
        
          r
          
            11
          
        
        
          r
          
            21
          
        
        
          
          (
          mod
          
          
            a
            
              1
            
          
          )
        
        ,
        
          r
          
            12
          
        
        
          r
          
            22
          
        
        
          
          (
          mod
          
          
            a
            
              2
            
          
          )
        
        ,
        …
        ,
        
          r
          
            1
            n
          
        
        
          r
          
            2
            n
          
        
        
          
          (
          mod
          
          
            a
            
              n
            
          
          )
        
        )
      
    
    {\displaystyle (x_{1}x_{2}{\pmod {M}})\leftrightarrow (r_{11}r_{21}{\pmod {a_{1}}},r_{12}r_{22}{\pmod {a_{2}}},\dots ,r_{1n}r_{2n}{\pmod {a_{n}}})}
  .
Մնացորդների վեկտորի անցումը թվի ժամանակավոր բարդությունը գնահատվում է 
  
    
      
        O
        (
        
          k
          
            2
          
        
        )
      
    
    {\displaystyle O(k^{2})}
  , որտեղ k ֊ն վերականգնվող թիվն է բիթերո։


== Լուծումների որոշման ալգորիթմ ==
Բերենք ներքևում խնդիրների լուծման ալգորիթմ, որը դրվում է 
  
    
      
        x
      
    
    {\displaystyle x}
   թվի, որոշակի տրված փոխադարձ պարզ 
  
    
      
        
          a
          
            1
          
        
        ,
        
          a
          
            2
          
        
        ,
        …
        ,
        
          a
          
            n
          
        
      
    
    {\displaystyle a_{1},a_{2},\dots ,a_{n}}
   թվերի բաժանումով իր մնացորդների հավաքածուով, վերականգնման թեորեմում։


=== Էլեմենտար հանրահաշիվ ===
Որպես օրինակ դիտարկենք

համակարգը։
Համակարգի լուծման համար առանձին արտագրենք առաջին, երկրորդ և երրորդ հավասարումների լուծումները 2 × 3 × 7 = 42):

  
    
      
        
          x
          
            1
          
        
        ∈
        {
        1
        ,
        3
        ,
        5
        ,
        7
        ,
        9
        ,
        11
        ,
        …
        ,
        39
        ,
        
          41
        
        ,
        43
        ,
        …
        }
      
    
    {\displaystyle x_{1}\in \{1,3,5,7,9,11,\dots ,39,\mathbf {41} ,43,\dots \}}
  

  
    
      
        
          x
          
            2
          
        
        ∈
        {
        2
        ,
        5
        ,
        8
        ,
        11
        ,
        14
        ,
        …
        ,
        38
        ,
        
          41
        
        ,
        44
        ,
        …
        }
      
    
    {\displaystyle x_{2}\in \{2,5,8,11,14,\dots ,38,\mathbf {41} ,44,\dots \}}
  

  
    
      
        
          x
          
            3
          
        
        ∈
        {
        6
        ,
        13
        ,
        20
        ,
        27
        ,
        34
        ,
        
          41
        
        ,
        48
        ,
        …
        }
      
    
    {\displaystyle x_{3}\in \{6,13,20,27,34,\mathbf {41} ,48,\dots \}}
  Ակնհայտ է, որ համակարգի լուծումների բազմությունը կլինի վերը ներկայացված բազմությունների հատումը։ Թեորեմի պնդման համաձայն լուծումը գոյություն ունի և միակն է մինչև 42 մոդուլի վերցնելը ճշտությամբ։ Մեր դեպքում 
  
    
      
        x
        ∈
        {
        41
        ,
        83
        ,
        125
        ,
        …
        }
      
    
    {\displaystyle x\in \{41,83,125,\dots \}}
   կամ 
  
    
      
        x
        ≡
        41
        
          
          (
          mod
          
          42
          )
        
        .
      
    
    {\displaystyle x\equiv 41{\pmod {42}}.}
  
Ուրիշ ճանապարհ ցույց տալու համար խնդիրը վերաձևակերպենք։ 
Գտնենք թվերի (u, v, w) այնպիսի եռյակ, որ։

x ֊ը առաջին հավասարումից երկրորդի մեջ տեղափոխելով կստանանք 
  
    
      
        1
        +
        2
        u
        ≡
        2
        
          
          (
          mod
          
          3
          )
        
      
    
    {\displaystyle 1+2u\equiv 2{\pmod {3}}}
  , այդ դեպքում 
  
    
      
        2
        u
        ≡
        1
        
          
          (
          mod
          
          3
          )
        
      
    
    {\displaystyle 2u\equiv 1{\pmod {3}}}
  , կամ 
  
    
      
        4
        u
        ≡
        2
        
          
          (
          mod
          
          3
          )
        
      
    
    {\displaystyle 4u\equiv 2{\pmod {3}}}
  , կամ 
  
    
      
        u
        ≡
        2
        
          
          (
          mod
          
          3
          )
        
      
    
    {\displaystyle u\equiv 2{\pmod {3}}}
  , կամ 
  
    
      
        u
        =
        2
        +
        3
        s
      
    
    {\displaystyle u=2+3s}
  ;
հետո x ֊ը տեղափոխելով առաջին հավասարումից երրորդի մեջ 
  
    
      
        u
      
    
    {\displaystyle u}
   տեսքի արտահայտության հաշվարկի համար, կստանանք 
  
    
      
        1
        +
        2
        (
        2
        +
        3
        s
        )
        ≡
        6
        
          
          (
          mod
          
          7
          )
        
      
    
    {\displaystyle 1+2(2+3s)\equiv 6{\pmod {7}}}
   կամ 
  
    
      
        6
        s
        ≡
        1
        
          
          (
          mod
          
          7
          )
        
      
    
    {\displaystyle 6s\equiv 1{\pmod {7}}}
  , 
  
    
      
        36
        s
        ≡
        6
        
          
          (
          mod
          
          7
          )
        
      
    
    {\displaystyle 36s\equiv 6{\pmod {7}}}
   և հետևաբար 
  
    
      
        s
        ≡
        6
        
          
          (
          mod
          
          7
          )
        
      
    
    {\displaystyle s\equiv 6{\pmod {7}}}
  ;
այդ դեպքում 
  
    
      
        x
        =
        1
        +
        2
        (
        2
        +
        3
        ⋅
        6
        )
        =
        41
      
    
    {\displaystyle x=1+2(2+3\cdot 6)=41}
  .


=== Մնացորդների մասին չինական թեորեմի հիմքի վրա ալգորիթմ ===
Ալգորիթմը տարվում է դեպի թեորեմում տրված բանաձևով լուծումների որոնում։
Քայլ 1. Հաշվում ենք 
  
    
      
        M
        =
        
          
            
              ∏
              
                i
                =
                1
              
              
                n
              
            
            
              a
              
                i
              
            
          
        
      
    
    {\displaystyle M={\displaystyle \prod _{i=1}^{n}a_{i}}}
  ։
Քայլ 2. Բոլոր 
  
    
      
        i
        ∈
        {
        1
        ,
        2
        ,
        …
        ,
        n
        }
      
    
    {\displaystyle i\in \{1,2,\dots ,n\}}
   համար գտնում ենք 
  
    
      
        
          M
          
            i
          
        
        =
        
          
            M
            
              a
              
                i
              
            
          
        
      
    
    {\displaystyle M_{i}={\frac {M}{a_{i}}}}
  ։
Քայլ 3. Գտնում ենք 
  
    
      
        
          M
          
            i
          
          
            −
            1
          
        
        =
        
          
            1
            
              M
              
                i
              
            
          
        
        
          mod
          
            
              a
              
                i
              
            
          
        
      
    
    {\displaystyle M_{i}^{-1}={\frac {1}{M_{i}}}{\bmod {a_{i}}}}
   (օրինակ, օգտագործելով Էվկլիդեսի ընդլայնված ալգորիթմ)։
Քայլ 4. Հաշվում ենք հիմնական արժեքը 
  
    
      
        x
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          r
          
            i
          
        
        
          M
          
            i
          
        
        
          M
          
            i
          
          
            −
            1
          
        
        
        mod
        
        
        M
      
    
    {\displaystyle x=\sum _{i=1}^{n}r_{i}M_{i}M_{i}^{-1}\mod M}
   բանաձևով։


=== Գեռների ալգորիթմ ===
Դիտարկենք մոդուլների 
  
    
      
        (
        
          a
          
            1
          
        
        ,
        
          a
          
            2
          
        
        ,
        …
        ,
        
          a
          
            n
          
        
        )
      
    
    {\displaystyle (a_{1},a_{2},\dots ,a_{n})}
   խումբը, բավարարող թեորեմի պայմաններին։ Թվերի տեսության մեկ այլ թեորեմով հիմնավորվում է,որ ցանկացած 
  
    
      
        0
        ⩽
        x
        <
        M
        =
        
          a
          
            1
          
        
        ⋅
        
          a
          
            2
          
        
        ⋅
        …
        ⋅
        
          a
          
            n
          
        
      
    
    {\displaystyle 0\leqslant x<M=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}
   թիվ միանշանակ ներկայացնելի է
  
    
      
        x
        =
        
          x
          
            1
          
        
        +
        
          x
          
            2
          
        
        ⋅
        
          a
          
            1
          
        
        +
        
          x
          
            3
          
        
        ⋅
        
          a
          
            1
          
        
        ⋅
        
          a
          
            2
          
        
        +
        ⋯
        +
        
          x
          
            n
          
        
        ⋅
        
          a
          
            1
          
        
        ⋅
        
          a
          
            2
          
        
        ⋅
        …
        ⋅
        
          a
          
            n
            −
            1
          
        
      
    
    {\displaystyle x=x_{1}+x_{2}\cdot a_{1}+x_{3}\cdot a_{1}\cdot a_{2}+\dots +x_{n}\cdot a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n-1}}
   տեսքով։
Հերթականությամբ հաշվելով բոլոր 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
   для 
  
    
      
        i
        ∈
        {
        1
        ,
        2
        ,
        …
        ,
        n
        }
      
    
    {\displaystyle i\in \{1,2,\dots ,n\}}
   գործակիցները, մենք կկարողանանք տեղադրել դրանք բանաձևում և գտնել հիմնական լուծումը։
Նշանակենք 
  
    
      
        
          r
          
            i
            j
          
        
        =
        
          a
          
            i
          
          
            −
            1
          
        
        
          mod
          
            
              a
              
                j
              
            
          
        
      
    
    {\displaystyle r_{ij}=a_{i}^{-1}{\bmod {a_{j}}}}
   և դիտարկենք 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
   մոդուլով արտահայտություն 
  
    
      
        x
      
    
    {\displaystyle x}
   համար։

  
    
      
        
          x
          
            1
          
        
        =
        
          r
          
            1
          
        
      
    
    {\displaystyle x_{1}=r_{1}}
  ;

  
    
      
        
          r
          
            2
          
        
        =
        (
        
          x
          
            1
          
        
        +
        
          x
          
            2
          
        
        
          a
          
            1
          
        
        )
        
          mod
          
            
              a
              
                2
              
            
          
        
      
    
    {\displaystyle r_{2}=(x_{1}+x_{2}a_{1}){\bmod {a_{2}}}}
  ;

  
    
      
        
          x
          
            2
          
        
        =
        (
        
          r
          
            2
          
        
        −
        
          x
          
            1
          
        
        )
        
          r
          
            12
          
        
        
          mod
          
            
              a
              
                2
              
            
          
        
      
    
    {\displaystyle x_{2}=(r_{2}-x_{1})r_{12}{\bmod {a_{2}}}}
  ;

  
    
      
        
          r
          
            3
          
        
        =
        (
        
          x
          
            1
          
        
        +
        
          x
          
            2
          
        
        
          a
          
            1
          
        
        +
        
          x
          
            3
          
        
        
          a
          
            1
          
        
        
          a
          
            2
          
        
        )
        
          mod
          
            
              a
              
                3
              
            
          
        
      
    
    {\displaystyle r_{3}=(x_{1}+x_{2}a_{1}+x_{3}a_{1}a_{2}){\bmod {a_{3}}}}
  ;

  
    
      
        
          x
          
            3
          
        
        =
        (
        (
        
          r
          
            3
          
        
        −
        
          x
          
            1
          
        
        )
        
          r
          
            13
          
        
        −
        
          x
          
            2
          
        
        )
        
          r
          
            23
          
        
        
          mod
          
            
              a
              
                3
              
            
          
        
      
    
    {\displaystyle x_{3}=((r_{3}-x_{1})r_{13}-x_{2})r_{23}{\bmod {a_{3}}}}
  
և այլն։

  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
   գործակիցների որոնման ալգորիթմը ակնառուության համար կիրառենք կոդով, ենթադրությամբ, որ a, remainders զանգվածները և հակադարձ էլեմենտների inverses երկչափ զանգվածը արդեն ստացել են անհրաժեշտ արժեքները։

Տրված ալգորիթմի համար 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
   գործակիցների որոշման բարդությունը 
  
    
      
        O
        (
        
          n
          
            2
          
        
        )
      
    
    {\displaystyle O(n^{2})}
   է։ Բարդությունը նույնպիսին է նաև գտնված գործակիցներով իրական արժեքի վերականգման դեպքում։


== Վարիացիաներ և ընդհանրացումներ ==


=== Բանաձևայնացում օղակների համար ===
Թող 
  
    
      
        A
        ,
        
          B
          
            1
          
        
        ,
        …
        ,
        
          B
          
            n
          
        
      
    
    {\displaystyle A,B_{1},\dots ,B_{n}}
   —ն լինի միավորով կոմուտատիվ օղակներ, 
  
    
      
        
          φ
          
            i
          
        
        :
        A
        →
        
          B
          
            i
          
        
      
    
    {\displaystyle \varphi _{i}\colon A\to B_{i}}
   ֊ն՝ սյուրեկտիվ հոմոմորֆիզմներ, 
  
    
      
        ker
        ⁡
        
          φ
          
            i
          
        
        +
        ker
        ⁡
        
          φ
          
            j
          
        
        =
        A
      
    
    {\displaystyle \ker \varphi _{i}+\ker \varphi _{j}=A}
   հատկանիշներով օժտված, բոլոր 
  
    
      
        i
        ,
        j
        ∈
        {
        1
        ,
        …
        ,
        n
        }
        ,
        i
        ≠
        j
      
    
    {\displaystyle i,j\in \{1,\dots ,n\},i\neq j}
   համար։ Այդ դեպքում 

  
    
      
        Φ
        :
        A
        →
        
          ∏
          
            i
            =
            1
          
          
            n
          
        
        
          B
          
            i
          
        
      
    
    {\displaystyle \Phi \colon A\to \prod _{i=1}^{n}B_{i}}
   հոմոմորֆիզմը,տրված 

  
    
      
        Φ
        (
        a
        )
        =
        (
        
          φ
          
            1
          
        
        (
        a
        )
        ,
        …
        ,
        
          φ
          
            n
          
        
        (
        a
        )
        )
      
    
    {\displaystyle \Phi (a)=(\varphi _{1}(a),\dots ,\varphi _{n}(a))}
   բանաձևով,հանդիսանում է սյուրեկտիվ։ Առավել ևս, 
  
    
      
        Φ
      
    
    {\displaystyle \Phi }
   որոշում է իզոմորֆիզմ

  
    
      
        A
        
          /
        
        
          (
          
            
              ⋂
              
                i
                =
                1
              
              
                n
              
            
            ker
            ⁡
            
              φ
              
                i
              
            
          
          )
        
        ≅
        
          ∏
          
            i
            =
            1
          
          
            n
          
        
        
          B
          
            i
          
        
      
    
    {\displaystyle A/\left(\bigcap _{i=1}^{n}\ker \varphi _{i}\right)\cong \prod _{i=1}^{n}B_{i}}
  ։Եթե տեղադրել 
  
    
      
        A
        =
        
          Z
        
        
          /
        
        (
        
          a
          
            1
          
        
        ⋅
        …
        ⋅
        
          a
          
            n
          
        
        
          Z
        
        )
        ,
        
          B
          
            i
          
        
        =
        
          Z
        
        
          /
        
        
          a
          
            i
          
        
        
          Z
        
         
        (
        i
        =
        1
        ,
        2
        ,
        …
        ,
        n
        ;
         
        
          a
          
            i
          
        
        ∈
        
          Z
        
        )
      
    
    {\displaystyle A=\mathbb {Z} /(a_{1}\cdot \ldots \cdot a_{n}\mathbb {Z} ),B_{i}=\mathbb {Z} /a_{i}\mathbb {Z} \ (i=1,2,\dots ,n;\ a_{i}\in \mathbb {Z} )}
   և հոմոմորֆիզմը որոշել հետևյալ կերպ․ 

  
    
      
        
          φ
          
            i
          
        
        (
        x
        )
        =
        x
        
        
          mod
          
            
            
              a
              
                i
              
            
          
        
      
    
    {\displaystyle \varphi _{i}(x)=x\,{\bmod {\,a_{i}}}}
  ,ապա մենք կստանանք թեորեմի թվաբանական տարբերակը։
Այդպես հաճախ հանդիպում է օղակների էկվիվալենտ ձևակերպումը, որտեղ 
  
    
      
        
          B
          
            i
          
        
      
    
    {\displaystyle B_{i}}
   ունեն 
  
    
      
        A
        
          /
        
        
          I
          
            i
          
        
      
    
    {\displaystyle A/I_{i}}
   տեսքը, իդեալների որոշակի 
  
    
      
        
          I
          
            1
          
        
        ,
        …
        ,
        
          I
          
            n
          
        
      
    
    {\displaystyle I_{1},\dots ,I_{n}}
   խմբի, 
  
    
      
        
          φ
          
            i
          
        
      
    
    {\displaystyle \varphi _{i}}
   հոմոմորֆիզները հանդիսանում են իրական պրոյեկցիաներ 
  
    
      
        A
        
          /
        
        
          I
          
            i
          
        
      
    
    {\displaystyle A/I_{i}}
   վրաև պահանջվում է, որ 
  
    
      
        
          I
          
            i
          
        
        +
        
          I
          
            j
          
        
        =
        A
      
    
    {\displaystyle I_{i}+I_{j}=A}
   ցանկացած 
  
    
      
        i
        ,
        j
        ∈
        {
        1
        ,
        …
        ,
        n
        }
        ,
        i
        ≠
        j
      
    
    {\displaystyle i,j\in \{1,\dots ,n\},i\neq j}
   համար։ Ուրիշ բառերով, եթե 
  
    
      
        
          I
          
            1
          
        
        ,
        …
        ,
        
          I
          
            n
          
        
      
    
    {\displaystyle I_{1},\dots ,I_{n}}
   իդեալները զույգ առ զույգ փոխադարձ պարզ են (այսինքն երկու իդեալների գումարը հավասար է հենց օղակին), ապա նրանց արտադրյալը համընկնում է իրենց հատման հետ և ֆակտոր օղակը այդ արտադրյալով իզոմորֆ է ֆակտորների արտադրյալին․

  
    
      
        A
        
          /
        
        (
        
          I
          
            1
          
        
        
          I
          
            2
          
        
        …
        
          I
          
            n
          
        
        )
        ≅
        A
        
          /
        
        
          I
          
            1
          
        
        ×
        A
        
          /
        
        
          I
          
            2
          
        
        ×
        …
        ×
        A
        
          /
        
        
          I
          
            n
          
        
      
    
    {\displaystyle A/(I_{1}I_{2}\ldots I_{n})\cong A/I_{1}\times A/I_{2}\times \ldots \times A/I_{n}}
  ։


=== Ապացույց էվկլիդյան օղակների համար ===
Թող 
  
    
      
        R
      
    
    {\displaystyle R}
   լինի էվլկիդյան օղակ և 
  
    
      
        m
        ,
        n
      
    
    {\displaystyle m,n}
   ֊ն՝ փոխադարձ պարզ թվեր։ Այդ դեպքում կապացուցենք, որ գոյություն ունի կոռեկտ տրված իզոմորֆիզմ․

  
    
      
        R
        
          
            /
          
          
            (
            m
            n
            )
          
        
        ≅
        R
        
          
            /
          
          
            (
            m
            )
          
        
        ×
        R
        
          
            /
          
          
            (
            n
            )
          
        
      
    
    {\displaystyle R/_{(mn)}\cong R/_{(m)}\times R/_{(n)}}
  

  
    
      
        [
        x
        
          ]
          
            m
            n
          
        
        ⟶
        (
        [
        x
        
          ]
          
            m
          
        
        ,
         
        [
        x
        
          ]
          
            n
          
        
        )
      
    
    {\displaystyle [x]_{mn}\longrightarrow ([x]_{m},\ [x]_{n})}
   ուղիղ արտապատկերումն ակնհայտ է։

Հակառակ արտապատկերման գոյության ապացուցման համար դիտարկենք 
  
    
      
        [
        1
        ]
      
    
    {\displaystyle [1]}
   և 
  
    
      
        [
        0
        ]
      
    
    {\displaystyle [0]}
   էկվիվալենտության դասերը։

  
    
      
        (
        [
        1
        
          ]
          
            m
          
        
        ,
         
        [
        0
        
          ]
          
            n
          
        
        )
        ⟶
        [
        u
        
          ]
          
            m
            n
          
        
      
    
    {\displaystyle ([1]_{m},\ [0]_{n})\longrightarrow [u]_{mn}}
  

  
    
      
        (
        [
        0
        
          ]
          
            m
          
        
        ,
         
        [
        1
        
          ]
          
            n
          
        
        )
        ⟶
        [
        v
        
          ]
          
            m
            n
          
        
      
    
    {\displaystyle ([0]_{m},\ [1]_{n})\longrightarrow [v]_{mn}}
  

  
    
      
        [
        u
        
          ]
          
            m
            n
          
        
      
    
    {\displaystyle [u]_{mn}}
   կգտնենք լուծելով հավասարումների հետևյալ համակարգը․

  
    
      
        
          
            {
            
              
                
                  u
                  ≡
                  1
                   
                  
                    
                    (
                    mod
                    
                    m
                    )
                  
                
              
              
                
                  u
                  ≡
                  0
                   
                  
                    
                    (
                    mod
                    
                    n
                    )
                  
                
              
            
            
          
        
      
    
    {\displaystyle {\begin{cases}u\equiv 1\ {\pmod {m}}\\u\equiv 0\ {\pmod {n}}\end{cases}}}
  

  
    
      
        ∃
        y
        ∈
        
          Z
        
        :
         
        u
        =
        n
        y
        ,
         
        n
        y
        ≡
        1
        
          
          (
          mod
          
          m
          )
        
      
    
    {\displaystyle \exists y\in \mathbb {Z} :\ u=ny,\ ny\equiv 1{\pmod {m}}}
  
Անալոգ ձևով գտնենք 
  
    
      
        [
        v
        
          ]
          
            m
            n
          
        
      
    
    {\displaystyle [v]_{mn}}
  :

  
    
      
        ∃
        x
        ∈
        
          Z
        
        :
         
        u
        =
        m
        x
        ,
         
        m
        x
        ≡
        1
        
          
          (
          mod
          
          m
          )
        
      
    
    {\displaystyle \exists x\in \mathbb {Z} :\ u=mx,\ mx\equiv 1{\pmod {m}}}
  
Ցույց տանք, որ ընդհանուր տեսքով գործում է․

  
    
      
        (
        [
        a
        
          ]
          
            m
          
        
        ,
         
        [
        b
        
          ]
          
            n
          
        
        )
        ⟶
        [
        a
        u
        +
        b
        v
        
          ]
          
            m
            n
          
        
      
    
    {\displaystyle ([a]_{m},\ [b]_{n})\longrightarrow [au+bv]_{mn}}
  

  
    
      
        a
        u
        +
        b
        v
        ≡
        a
        
          
          (
          mod
          
          m
          )
        
      
    
    {\displaystyle au+bv\equiv a{\pmod {m}}}
  , քանի որ 
  
    
      
        v
        ≡
        0
        
          
          (
          mod
          
          m
          )
        
      
    
    {\displaystyle v\equiv 0{\pmod {m}}}
   և 
  
    
      
        u
        ≡
        1
        
          
          (
          mod
          
          m
          )
        
      
    
    {\displaystyle u\equiv 1{\pmod {m}}}
  

  
    
      
        a
        u
        +
        b
        v
        ≡
        b
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle au+bv\equiv b{\pmod {n}}}
  , քանի որ 
  
    
      
        u
        ≡
        0
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle u\equiv 0{\pmod {n}}}
   և 
  
    
      
        v
        ≡
        1
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle v\equiv 1{\pmod {n}}}
  
Ստուգենք արտապատկերման կոռեկտությունը, այսինքն, որ 
  
    
      
        [
        a
        
          ]
          
            m
          
        
        ,
         
        [
        b
        
          ]
          
            n
          
        
      
    
    {\displaystyle [a]_{m},\ [b]_{n}}
   դասի տարբեր էլէմենտներ վերցնելու դեպքում արդյունքը չի փոխվում։

  
    
      
        
          
            {
            
              
                
                  a
                  ≡
                  
                    a
                    ′
                  
                  
                    
                    (
                    mod
                    
                    m
                    )
                  
                
              
              
                
                  b
                  ≡
                  
                    b
                    ′
                  
                  
                    
                    (
                    mod
                    
                    n
                    )
                  
                
              
            
            
          
        
      
    
    {\displaystyle {\begin{cases}a\equiv a'{\pmod {m}}\\b\equiv b'{\pmod {n}}\end{cases}}}
  
Նշանակում է 
  
    
      
        a
        u
        +
        b
        v
        ≡
        
          a
          ′
        
        u
        +
        
          b
          ′
        
        v
        
          
          (
          mod
          
          m
          n
          )
        
      
    
    {\displaystyle au+bv\equiv a'u+b'v{\pmod {mn}}}
  , արտապատկերումը կոռեկտ է։
Կարելի է ստուգել, որ կառուցված արտապատկերումը ճիշտ հակառակն է։


== Կիրառում ==
Մնացորդների մասին չինական թեորեմը լայն կիրառում ունի թվերի տեսության, ծածկագրության մեջ և այլ տեղերում։

Փոխադարձ միարժեք համապատասխանությունը կամայական թվի և իր մնացորդների միչև,փոխադարձ պարզ թվերի խմբով վորոշվող, որի գոյությունը հաստատվում է թեորեմում, պրակտիկայում օգնում է աշխատել ոչ երկար թվերի հետ, այլ իր մնացորդների կարճ երկարությամբ խմբերի հետ։ Բացի դրանից, մոդուլներից յուրաքանչյուրի հաշվումը կարելի է կատարել զուգահեռ։ Եթե, որպես բազիս վերցնենք, օրինակ, առաջին 500 պարզ թվերը, որոնցից յուրաքանչյուրի երկարությունը չի գերազանցում 12 բիթ, ապա դա բավարար է տասական թվերի ներկայացմանը մինչև 1519 նշան երկարությամբ։ (Թե,որտեղից է վերցրված 1519 թիվը, շատ հեշտ է հասկանալ․ առաջին 500 պարզ թվերի տասական լոգարիթմների գումարը հավասար է 1519,746…)։Օրինակ, RSA ալգորիթմում հաշվումը կատարվում է n շատ մեծ թվի մոդուլով, ներկայացված երկու մեծ պարզ թվերի արտադրյալի տեսքով։ Թեորեմը թույլ է տալիս անցում կատարել այդ պարզ բաժանարարների մոդուլով հաշվմանը, որոնք մեծությամբ արդեն n արմատների կարգի են, նշանակում է ունեն երկու անգամ փոքր բիթային երկարություն։Նշենք նաև, որ հաշվարկների օգտագործումը, համաձայն մնացորդների մասին չինական թեորեմի, RSA ալգորիթմը ժամանակային հարձակումները դարձնում է ընկալելի։.Թեորեմում հիմնավորված են Ասմուտ — բլումի սխեմա և Մինյոտտայի սխեմա — մասնակիցների խմբում գաղտնիքի բաժանարարի մուտքային սխեմաները։ Գաղտիքը կարող են իմանալ n մասնակիցներից միայն k ֊ն, միավորելով իրենց բանալիները.
Կիրառումներից մեկը հանդիսանում է պարզ թվերի հիման վրա Ֆուրյեի արագ փոխակերպումը։
Թեորեմն ընկած է հավասարման ամբողջաթվային արմատների որոնման Խասսեի սկզբունքի հիմքում.
Թեորեմից հետևում է Էյլերի ֆունկցիայի մուլտիպլիկատիվությունը։
Թեորեմում հիմնավորվում է հատուկ տեսք ունեցող թվերի համար պոլիմինալ ժամանակից դիսկրետ ալգորիթմի որոնումը՝ Պոլիգ — Խելլմանի ալգորիթմ։
Թեորեմը բազմակի կիրառում ունի գաղտնագրման համակարգերում վերծանման և ապավերծանման մեջ, օրինակ, Ռաբինի կրիպտոհամակարգում կամ Վիժեների ծածկագրման մեջ։


== Գրականություն ==
С. Ленг Алгебра. — М.: Мир, 1968. — С. 82—83.
Гольденберг А. Задача остатков(ռուս.) // В.О.Ф.Э.М.. — 1887. — № 35. — С. 247—253.
Н. Смарт Криптография. — 2005. — 528 с.
Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — 190 с.
Переславцева О. Н. Распараллеливание алгоритмов с применением китайской теоремы об остатках. — Вестник ТГУ, 2009. — № 4. — ISSN 1810-0198.
Фергюсон, Нильс, Шнаер, Брюс Практическая криптография. — М.: Вильямс, 2004. — 432 с. — ISBN 5-8459-0733-0
Ян Сонг Й Криптоанализ RSA. — 2011. — 312 с. — ISBN 978-5-93972-873-7
Шенец Н. Н. Модульное разделение секрета и системы электронного голосования. — Вестник БГУ, 2011. — № 1.


== Ծանոթագրություններ ==


== Արտաքին հղումներ ==
Шенец Н. Н. Модульное разделение секрета и системы электронного голосования(2011)
Ишухаметов Ш. Т. Методы факторизации натуральных чисел(2011)
Нестеренко А. Введение в современную криптографию Теоретико-числовые алгоритмы (2011)
Минеев М. П., Чубариков В. Н. Об одном применении китайской теоремы об остатках к шифру Виженера(չաշխատող հղում) (2010)