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

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

Պատմություն

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

Ձևակերպում

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

Ապացույցներ

Ինդդուկցիա հավասարումների քանակով

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

$d=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{k-1}$։

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

Ապացույցի կոնստրուկտիվ մեթոդ

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

${\begin{cases}x&\equiv r_{1}{\pmod {a_{1}}}\\x&\equiv r_{2}{\pmod {a_{2}}}\\&\vdots \\x&\equiv r_{n}{\pmod {a_{n}}}\\\end{cases}}$

(1)

հավասարումների համակարգը։

Եթե $(r_{1},r_{2},\dots ,r_{n})$ և $(a_{1},a_{2},\dots ,a_{n})$ բավարարում են թեորեմի պայմաններին, ապա (1)համակարգի լուծումը գոյություն ունի և $M$ մոդուլով ճշտությամբ միակն է, որտեղ $M={\displaystyle \prod _{i=1}^{n}a_{i}}$, ընդ որում ճշմարիտ է բանաձևը

$x=\sum _{i=1}^{n}r_{i}M_{i}M_{i}^{-1}$, որտեղ $M_{i}={\frac {M}{a_{i}}}$, իսկ $M_{i}^{-1}$ — հակադարձ մուլտիպլիկատիվ $M_{i}\mod a_{i}$ $\mathbb {Z} _{a_{i}}$ օղակի էլեմենտ է։

(2)

Ցույց տանք, որ այդ եղանակով որոշված $x$ ֊ը հանդիսանում է լուծում։ Ստուգենք, որ նրա համար համակարգումգործում է i-е հավասարությունը։ $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}\equiv {\displaystyle \prod _{k\neq j}^{n}a_{k}}\equiv 0{\pmod {a_{i}}}$ , բոլոր $i\neq j$ դեպքում, երրորդը, քանի որ $M_{i}^{-1}$ հանդիսանում է հակադարձ $a_{i}$ մոդուլով $M_{i}$ համար։ Բոլոր $i$ համար կրկնելով դատողությունը, համոզվենք, որ (2) բանաձևով որոշված $x$ ֊ը հանդիսանում է լուծում (1) համար։

Բոլոր $x'\equiv x{\pmod {M}}$ թվերը, ընտրված $M$ թվի համաձայն,կբավարարեն համակարգին։ Այժմ ցույց տանք, որ $0,1,\dots ,M-1$ (բազմություն $A$) թվերի մեջ մեր գտած լուծումից բացի ուրիշ լուծում չի գտնվի։ Այդ փաստի հակառակ ապացույցը։ Ենթադրենք, որ հաջողվել է մնացորդների որոշակի $r$ հավաքածուի համար գտնել գոնե երկու՝ $x_{1},x_{2}\in A$ լուծում։ Քանի որ բոլոր թույլատրելի $(r_{1},r_{2},\dots ,r_{n})$ հավաքածուների բազմությունը հանդիսանում է հավասարահզոր $A$ բազմությանը, ապա ${\overline {A}}_{x}:=A\setminus \{x_{1},x_{2}\}$ և ${\overline {B}}_{r}:=B\setminus \{r\}$ համար գործում է $|{\overline {A}}_{x}|<|{\overline {B}}_{r}|$։ Սակայն, վերը ապացուցվածի համաձայն, ${\overline {B}}_{r}$ ֊ի ցանկացաց հավաքածուի համար գոյություն ունի ${\overline {A}}_{x}$ ֊ից լուծում, հետևաբար Դիրիխլեի սկզբունքի համաձայն կգտնվեն ամենաքիչը երկու մնացորդների հավաքածուներ, որոնց համապատասխանում է նույն $x\in A$ ֊ն։ Այդպիսի $x$ ֊ի համար կգտնվի այնպիսի $a_{i}$, որ $x\equiv r_{1},x\equiv r_{2}{\pmod {a_{i}}}$ և $r_{1}\neq r_{2}$. Հակասություն. Ինչն էլ պահանջվում էր ապացուցել։

Դիտողություն

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

$(x{\pmod {M}})\leftrightarrow (r_{1}{\pmod {a_{1}}},r_{2}{\pmod {a_{2}}},\dots ,r_{n}{\pmod {a_{n}}})$; համապատասխանությունից բացի

ճշմարիտ են նաև

$(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}{\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})$, որտեղ k ֊ն վերականգնվող թիվն է բիթերո։

Լուծումների որոշման ալգորիթմ

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

Էլեմենտար հանրահաշիվ

Որպես օրինակ դիտարկենք

${\begin{cases}x\equiv 1{\pmod {2}}\\x\equiv 2{\pmod {3}}\\x\equiv 6{\pmod {7}}\\\end{cases}}$

համակարգը։

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

$x_{1}\in \{1,3,5,7,9,11,\dots ,39,\mathbf {41} ,43,\dots \}$

$x_{2}\in \{2,5,8,11,14,\dots ,38,\mathbf {41} ,44,\dots \}$

$x_{3}\in \{6,13,20,27,34,\mathbf {41} ,48,\dots \}$

Ակնհայտ է, որ համակարգի լուծումների բազմությունը կլինի վերը ներկայացված բազմությունների հատումը։ Թեորեմի պնդման համաձայն լուծումը գոյություն ունի և միակն է մինչև 42 մոդուլի վերցնելը ճշտությամբ։ Մեր դեպքում $x\in \{41,83,125,\dots \}$ կամ $x\equiv 41{\pmod {42}}.$

Ուրիշ ճանապարհ ցույց տալու համար խնդիրը վերաձևակերպենք։ Գտնենք թվերի (u, v, w) այնպիսի եռյակ, որ։

${\begin{cases}x=1+2u\\x=2+3v\\x=6+7w\\\end{cases}}$

x ֊ը առաջին հավասարումից երկրորդի մեջ տեղափոխելով կստանանք $1+2u\equiv 2{\pmod {3}}$, այդ դեպքում $2u\equiv 1{\pmod {3}}$, կամ $4u\equiv 2{\pmod {3}}$, կամ $u\equiv 2{\pmod {3}}$, կամ $u=2+3s$;

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

այդ դեպքում $x=1+2(2+3\cdot 6)=41$.

Մնացորդների մասին չինական թեորեմի հիմքի վրա ալգորիթմ

Ալգորիթմը տարվում է դեպի թեորեմում տրված բանաձևով լուծումների որոնում։

Քայլ 1. Հաշվում ենք $M={\displaystyle \prod _{i=1}^{n}a_{i}}$։

Քայլ 2. Բոլոր $i\in \{1,2,\dots ,n\}$ համար գտնում ենք $M_{i}={\frac {M}{a_{i}}}$։

Քայլ 3. Գտնում ենք $M_{i}^{-1}={\frac {1}{M_{i}}}{\bmod {a_{i}}}$ (օրինակ, օգտագործելով Էվկլիդեսի ընդլայնված ալգորիթմ)։

Քայլ 4. Հաշվում ենք հիմնական արժեքը $x=\sum _{i=1}^{n}r_{i}M_{i}M_{i}^{-1}\mod M$ բանաձևով։

Գեռների ալգորիթմ

Դիտարկենք մոդուլների $(a_{1},a_{2},\dots ,a_{n})$ խումբը, բավարարող թեորեմի պայմաններին։ Թվերի տեսության մեկ այլ թեորեմով հիմնավորվում է,որ ցանկացած $0\leqslant x<M=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}$ թիվ միանշանակ ներկայացնելի է

$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}$ для $i\in \{1,2,\dots ,n\}$ գործակիցները, մենք կկարողանանք տեղադրել դրանք բանաձևում և գտնել հիմնական լուծումը։

Նշանակենք $r_{ij}=a_{i}^{-1}{\bmod {a_{j}}}$ և դիտարկենք $a_{i}$ մոդուլով արտահայտություն $x$ համար։

$x_{1}=r_{1}$;

$r_{2}=(x_{1}+x_{2}a_{1}){\bmod {a_{2}}}$;

$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}){\bmod {a_{3}}}$;

$x_{3}=((r_{3}-x_{1})r_{13}-x_{2})r_{23}{\bmod {a_{3}}}$

և այլն։

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

for (int i = 0; i < n; i++) {
	x[i] = remainders[i];
	for (int j = 0; j < i; j++) {
		x[i] = inverses[j][i] * (x[i] - x[j]);
		x[i] = x[i] % a[i];
		if (x[i] < 0)
			x[i] += a[i];
	}
}

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

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

Բանաձևայնացում օղակների համար

Թող $A,B_{1},\dots ,B_{n}$ —ն լինի միավորով կոմուտատիվ օղակներ, $\varphi _{i}\colon A\to B_{i}$ ֊ն՝ սյուրեկտիվ հոմոմորֆիզմներ, $\ker \varphi _{i}+\ker \varphi _{j}=A$ հատկանիշներով օժտված, բոլոր $i,j\in \{1,\dots ,n\},i\neq j$ համար։ Այդ դեպքում

$\Phi \colon A\to \prod _{i=1}^{n}B_{i}$ հոմոմորֆիզմը,

տրված

$\Phi (a)=(\varphi _{1}(a),\dots ,\varphi _{n}(a))$ բանաձևով,

հանդիսանում է սյուրեկտիվ։ Առավել ևս, $\Phi$ որոշում է իզոմորֆիզմ

$A/\left(\bigcap _{i=1}^{n}\ker \varphi _{i}\right)\cong \prod _{i=1}^{n}B_{i}$։

Եթե տեղադրել $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} )$ և հոմոմորֆիզմը որոշել հետևյալ կերպ․

$\varphi _{i}(x)=x\,{\bmod {\,a_{i}}}$,

ապա մենք կստանանք թեորեմի թվաբանական տարբերակը։

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

$A/(I_{1}I_{2}\ldots I_{n})\cong A/I_{1}\times A/I_{2}\times \ldots \times A/I_{n}$։

Ապացույց էվկլիդյան օղակների համար

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

$R/_{(mn)}\cong R/_{(m)}\times R/_{(n)}$

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

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

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

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

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

${\begin{cases}u\equiv 1\ {\pmod {m}}\\u\equiv 0\ {\pmod {n}}\end{cases}}$

$\exists y\in \mathbb {Z} :\ u=ny,\ ny\equiv 1{\pmod {m}}$

Անալոգ ձևով գտնենք $[v]_{mn}$:

$\exists x\in \mathbb {Z} :\ u=mx,\ mx\equiv 1{\pmod {m}}$

Ցույց տանք, որ ընդհանուր տեսքով գործում է․

$([a]_{m},\ [b]_{n})\longrightarrow [au+bv]_{mn}$

$au+bv\equiv a{\pmod {m}}$, քանի որ $v\equiv 0{\pmod {m}}$ և $u\equiv 1{\pmod {m}}$

$au+bv\equiv b{\pmod {n}}$, քանի որ $u\equiv 0{\pmod {n}}$ և $v\equiv 1{\pmod {n}}$

Ստուգենք արտապատկերման կոռեկտությունը, այսինքն, որ $[a]_{m},\ [b]_{n}$ դասի տարբեր էլէմենտներ վերցնելու դեպքում արդյունքը չի փոխվում։

${\begin{cases}a\equiv a'{\pmod {m}}\\b\equiv b'{\pmod {n}}\end{cases}}$

Նշանակում է $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.

Արտաքին հղումներ

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