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

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

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

## Ձևակերպում
Եթե a_1, a_2, \dots, a_n բնական թվերը զույգ առ զույգ փոխադարձաբար պարզ են, ապա ցանկացած ամբողջ r_1, r_2, \dots, r_n այնպիսին է, որ 0 \leqslant r_i  բոլոր i \in \{1, 2, \dots, n\}  համար կգտնվի N, որը a_i վրա բաժանելիս տալիս է r_i մնացորդ։ Ավելին, եթե գտնվեն այնպիսի երկու՝ 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  թվերը։Ցույց տանք, որ բոլոր t\in\{0,\dots,a_{k} - 1\} հանդիսանում են մնացորդներ M ֊ի ինչ֊որ էլեմենտների՝ a_k վրա բաժանելիս։
Ենթադրենք, որ դա այդպես չէ, այսինքն գոյություն ունեն որոշակի r_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 , t_2 , 0  և 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 թիվ, որը 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 բաժանում է առանց մնացորդի, ինչպես նաև իրենց արտադրյալները։ Ինչն էլ պահանջվում էր ապացուցել։

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

Եթե (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 ֊ը հանդիսանում է լուծում։ Ստուգենք, որ նրա համար համակարգումգործում է 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 \ne j}^n a_k} \equiv 0 \pmod{a_i} , բոլոր i \ne 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 A_x ֊ից լուծում, հետևաբար Դիրիխլեի սկզբունքի համաձայն կգտնվեն ամենաքիչը երկու մնացորդների հավաքածուներ, որոնց համապատասխանում է նույն x \in A ֊ն։ Այդպիսի x ֊ի համար կգտնվի այնպիսի a_i, որ x \equiv r_1, x \equiv r_2 \pmod{a_i} և r_1 \ne 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_1x_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 թվերի բաժանումով իր մնացորդների հավաքածուով, վերականգնման թեորեմում։

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

համակարգը։

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

: 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*) այնպիսի եռյակ, որ։

*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}= \frac1{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  թիվ միանշանակ ներկայացնելի է

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_2a_1) \bmod{a_2};

x_2 = (r_2 - x_1)r_{12} \bmod{a_2};

r_3 = (x_1 + x_2a_1 + x_3a_1a_2) \bmod{a_3};

x_3 = ((r_3 - x_1)r_{13} - x_2)r_{23} \bmod{a_3}

և այլն։

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


```javascript
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_1I_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* ֊ն, միավորելով իրենց բանալիները.
* Կիրառումներից մեկը հանդիսանում է պարզ թվերի հիման վրա Ֆուրյեի արագ փոխակերպումը։
* Թեորեմն ընկած է հավասարման ամբողջաթվային արմատների որոնման Խասսեի սկզբունքի հիմքում.
* Թեորեմից հետևում է Էյլերի ֆունկցիայի մուլտիպլիկատիվությունը։ 
* Թեորեմում հիմնավորվում է հատուկ տեսք ունեցող թվերի համար պոլիմինալ ժամանակից դիսկրետ ալգորիթմի որոնումը՝ Պոլիգ — Խելլմանի ալգորիթմ։
* Թեորեմը բազմակի կիրառում ունի գաղտնագրման համակարգերում վերծանման և ապավերծանման մեջ, օրինակ, Ռաբինի կրիպտոհամակարգում կամ Վիժեների ծածկագրման մեջ։

## Գրականություն
* 
* 
* 
* 
* 
* 
* 
* 

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

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

Կատեգորիա:Թվերի տեսության մասին թեորեմներ
Կատեգորիա:Կոմուտատիվ հանրահաշիվ
Կատեգորիա:Հանրահաշվի թեորեմներ