Teorema restului chinezesc

În matematică , termenul chinez teorema restului cuprinde mai multe rezultate în algebra abstractă și teoria numerelor .

Congruența simultană a numerelor întregi

Formularea originală a teoremei, conținută într-o carte scrisă în secolul al III-lea de matematicianul chinez Sun Tsu și republicată ulterior într-o carte din 1247 scrisă de Qin Jiushao ^[1] , este o afirmație referitoare la congruențe simultane (a se vedea intrarea modulară aritmetică ) . Să presupunem că n ₁ , ..., n _k sunt numere întregi coprimă două la două (ceea ce înseamnă că GCD ( n _i , n _j ) = 1 când i ≠ j ). Apoi, totuși, alegem numere întregi a ₁ , ..., a _k , există o soluție întregi x a sistemului de congruențe

x\equiv a_{i}{\pmod {n_{i}}}\quad \mathrm {per} \;i=1,\ldots ,k.

{\ displaystyle x \ equals_ {i} {\ pmod {n_ {i}}} \ quad \ mathrm {for} \; i = 1, \ ldots, k.}

x \ equals_ {i} {\ pmod {n_ {i}}} \ quad {\ mathrm {for}} \; i = 1, \ ldots, k.

Mai mult, toate soluțiile x ale acestui sistem sunt congruente modul produsul n = n ₁ ... n _k .

O soluție x poate fi găsită după cum urmează. Pentru fiecare i numerele întregi n _i și n / n _i sunt prime și folosind algoritmul euclidian extins putem găsi două numere întregi r și s astfel încât rn _i + s n / n _i = 1. Setarea e _i = s n / n _eu , primim

e_{i}\equiv 1{\pmod {n_{i}}}\quad \mathrm {e} \quad e_{i}\equiv 0{\pmod {n_{j}}}

{\ displaystyle e_ {i} \ equiv 1 {\ pmod {n_ {i}}} \ quad \ mathrm {e} \ quad e_ {i} \ equiv 0 {\ pmod {n_ {j}}}}

e_ {i} \ equiv 1 {\ pmod {n_ {i}}} \ quad {\ mathrm {e}} \ quad e_ {i} \ equiv 0 {\ pmod {n_ {j}}}

pentru j ≠ i . Prin urmare, o soluție a sistemului de congruență este

x=\sum _{i=1}^{k}a_{i}e_{i}.\

{\ displaystyle x = \ sum _ {i = 1} ^ {k} a_ {i} e_ {i}. \}

x = \ sum _ {{i = 1}} ^ {k} a_ {i} e_ {i}. \

Găsirea soluțiilor

Definiți următorul sistem (cu $MCD(n_{1},n_{2})=MCD(n_{1},n_{3})=MCD(n_{2},n_{3})=1$ ${\ displaystyle MCD (n_ {1}, n_ {2}) = MCD (n_ {1}, n_ {3}) = MCD (n_ {2}, n_ {3}) = 1}$ ${\ displaystyle MCD (n_ {1}, n_ {2}) = MCD (n_ {1}, n_ {3}) = MCD (n_ {2}, n_ {3}) = 1}$ ):

${\begin{cases}x\equiv a_{1}{\pmod {n_{1}}}\\x\equiv a_{2}{\pmod {n_{2}}}\\x\equiv a_{3}{\pmod {n_{3}}}\end{cases}}$ ${\ displaystyle {\ begin {cases} x \ equiv a_ {1} {\ pmod {n_ {1}}} \\ x \ equiv a_ {2} {\ pmod {n_ {2}}} \\ x \ equiv a_ {3} {\ pmod {n_ {3}}} \ end {cases}}}$ ${\ displaystyle {\ begin {cases} x \ equiv a_ {1} {\ pmod {n_ {1}}} \\ x \ equiv a_ {2} {\ pmod {n_ {2}}} \\ x \ equiv a_ {3} {\ pmod {n_ {3}}} \ end {cases}}}$

Este $N=n_{1}\cdot n_{2}\cdot n_{3}$ ${\ displaystyle N = n_ {1} \ cdot n_ {2} \ cdot n_ {3}}$ ${\ displaystyle N = n_ {1} \ cdot n_ {2} \ cdot n_ {3}}$

N_{1}=n_{2}n_{3}

{\ displaystyle N_ {1} = n_ {2} n_ {3}}

{\ displaystyle N_ {1} = n_ {2} n_ {3}}

N_{2}=n_{1}n_{3}

{\ displaystyle N_ {2} = n_ {1} n_ {3}}

{\ displaystyle N_ {2} = n_ {1} n_ {3}}

N_{3}=n_{1}n_{2}

{\ displaystyle N_ {3} = n_ {1} n_ {2}}

{\ displaystyle N_ {3} = n_ {1} n_ {2}}

Lasă-i să fie atunci $y_{i}$ ${\ displaystyle y_ {i}}$ $y_ {i}$ soluții la congruențe $N_{i}y_{i}\equiv 1{\pmod {n_{i}}}$ ${\ displaystyle N_ {i} y_ {i} \ equiv 1 {\ pmod {n_ {i}}}}$ ${\ displaystyle N_ {i} y_ {i} \ equiv 1 {\ pmod {n_ {i}}}}$ ; soluția va fi dată de:

x\equiv a_{1}N_{1}y_{1}+a_{2}N_{2}y_{2}+a_{3}N_{3}y_{3}{\pmod {N}}

{\ displaystyle x \ equals_ {1} N_ {1} y_ {1} + a_ {2} N_ {2} y_ {2} + a_ {3} N_ {3} y_ {3} {\ pmod {N}} }

{\ displaystyle x \ equals_ {1} N_ {1} y_ {1} + a_ {2} N_ {2} y_ {2} + a_ {3} N_ {3} y_ {3} {\ pmod {N}} }

În cazul în care $MCD(n_{1},n_{2},n_{3})>1$ ${\ displaystyle MCD (n_ {1}, n_ {2}, n_ {3})> 1}$ ${\ displaystyle MCD (n_ {1}, n_ {2}, n_ {3})> 1}$ sistemul congruențelor ar fi putut fi descompus într-un sistem mai mare făcând fiecare $n_{i}$ ${\ displaystyle n_ {i}}$ $n_i$ primul. ^[2] De exemplu: ${\begin{cases}x\equiv 2{\pmod {6}}\\x\equiv 2{\pmod {3}}\end{cases}}$ ${\ displaystyle {\ begin {cases} x \ equiv 2 {\ pmod {6}} \\ x \ equiv 2 {\ pmod {3}} \ end {cases}}}$ ${\ displaystyle {\ begin {cases} x \ equiv 2 {\ pmod {6}} \\ x \ equiv 2 {\ pmod {3}} \ end {cases}}}$

ar deveni

${\begin{cases}x\equiv 2{\pmod {3}}\\x\equiv 0{\pmod {2}}\\x\equiv 2{\pmod {3}}\end{cases}}$ ${\ displaystyle {\ begin {cases} x \ equiv 2 {\ pmod {3}} \\ x \ equiv 0 {\ pmod {2}} \\ x \ equiv 2 {\ pmod {3}} \ end {cases }}}$ ${\ displaystyle {\ begin {cases} x \ equiv 2 {\ pmod {3}} \\ x \ equiv 0 {\ pmod {2}} \\ x \ equiv 2 {\ pmod {3}} \ end {cases }}}$

adică

${\begin{cases}x\equiv 0{\pmod {2}}\\x\equiv 2{\pmod {3}}\end{cases}}$ ${\ displaystyle {\ begin {cases} x \ equiv 0 {\ pmod {2}} \\ x \ equiv 2 {\ pmod {3}} \ end {cases}}}$ ${\ displaystyle {\ begin {cases} x \ equiv 0 {\ pmod {2}} \\ x \ equiv 2 {\ pmod {3}} \ end {cases}}}$

Enunțate de principalele domenii de idealuri

Pentru un domeniu cu idealuri principale R, teorema restului chinezesc ia următoarea formă: dacă u ₁ , ..., u _k sunt elemente ale lui R care sunt două câte două coprimă, și u denotă produsul u ₁ ... u _k , atunci inelul coeficient R / uR și produsul inelelor R / u ₁ R x ... x R / u _k R sunt izomorfe prin intermediul homomorfismului inelelor

f:R/uR\rightarrow R/u_{1}R\times \cdots \times R/u_{k}R

{\ displaystyle f: R / uR \ rightarrow R / u_ {1} R \ times \ cdots \ times R / u_ {k} R}

f: R / uR \ rightarrow R / u_ {1} R \ times \ cdots \ times R / u_ {k} R

astfel încât

f(x+uR)=(x+u_{1}R,\ldots ,x+u_{k}R)\quad {\mbox{ per ogni }}x\in R.

{\ displaystyle f (x + uR) = (x + u_ {1} R, \ ldots, x + u_ {k} R) \ quad {\ mbox {pentru fiecare}} x \ în R.}

f (x + uR) = (x + u_ {1} R, \ ldots, x + u_ {k} R) \ quad {\ mbox {pentru fiecare}} x \ în R.

Izomorfismul invers poate fi construit după cum urmează. Pentru fiecare i , elementele u _i și u / u _i sunt prime și pentru aceasta există două elemente r și s în R astfel încât

ru_{i}+su/u_{i}=1.

{\ displaystyle ru_ {i} + su / u_ {i} = 1.}

ru_ {i} + su / u_ {i} = 1.

Fie e _i = su / u _i . Apoi inversul lui f este harta

g:R/u_{1}R\times \cdots \times R/u_{k}R\rightarrow R/uR

{\ displaystyle g: R / u_ {1} R \ times \ cdots \ times R / u_ {k} R \ rightarrow R / uR}

g: R / u_ {1} R \ times \ cdots \ times R / u_ {k} R \ rightarrow R / uR

astfel încât

g(a_{1}+u_{1}R,\ldots ,a_{k}+u_{k}R)=\left(\sum _{i=1}^{k}a_{i}e_{i}\right)+uR\quad {\mbox{ per ogni }}a_{1},\ldots ,a_{k}\in R.

{\ displaystyle g (a_ {1} + u_ {1} R, \ ldots, a_ {k} + u_ {k} R) = \ left (\ sum _ {i = 1} ^ {k} a_ {i} e_ {i} \ right) + uR \ quad {\ mbox {for each}} a_ {1}, \ ldots, a_ {k} \ in R.}

g (a_ {1} + u_ {1} R, \ ldots, a_ {k} + u_ {k} R) = \ left (\ sum _ {{i = 1}} ^ {k} a_ {i} e_ {i} \ right) + uR \ quad {\ mbox {pentru fiecare}} a_ {1}, \ ldots, a_ {k} \ în R.

Rețineți că această formulare este o generalizare a teoremei anterioare privind congruențele întregi: inelul Z al întregilor este un domeniu cu idealuri principale, surjectivitatea hărții f arată că fiecare sistem de congruențe în formă

x\equiv a_{i}{\pmod {u_{i}}}\quad \mathrm {per} \;i=1,\ldots ,k

{\ displaystyle x \ equals_ {i} {\ pmod {u_ {i}}} \ quad \ mathrm {per} \; i = 1, \ ldots, k}

x \ equals_ {i} {\ pmod {u_ {i}}} \ quad {\ mathrm {for}} \; i = 1, \ ldots, k

poate fi rezolvat pentru a găsi x , iar injectivitatea hărții f arată că toate soluțiile x sunt modulul congruent u .

Declarație pentru inele generice

Forma generală a teoremei restului chinezesc, care implică toate formulările anterioare, poate fi formulată pentru inele și idealuri . Dacă R este un inel și I ₁ , ..., I _k sunt idealuri (bilaterale) ale lui R care sunt două câte două coprimă (ceea ce înseamnă că I _i + I _j = R ori de câte ori i ≠ j ), atunci produsul I de aceste idealuri sunt egale cu intersecția lor, iar inelul coeficient R / I este izomorf pentru produsul inelar R / I ₁ x R / I ₂ x ... x R / I _k prin izomorfism

f:R/I\rightarrow R/I_{1}\times \cdots \times R/I_{k}

{\ displaystyle f: R / I \ rightarrow R / I_ {1} \ times \ cdots \ times R / I_ {k}}

f: R / I \ rightarrow R / I_ {1} \ times \ cdots \ times R / I_ {k}

astfel încât

f(x+I)=(x+I_{1},\ldots ,x+I_{k})\quad {\mbox{ per ogni }}x\in R.

{\ displaystyle f (x + I) = (x + I_ {1}, \ ldots, x + I_ {k}) \ quad {\ mbox {pentru fiecare}} x \ în R.}

f (x + I) = (x + I_ {1}, \ ldots, x + I_ {k}) \ quad {\ mbox {pentru fiecare}} x \ în R.

Aplicațiile teoremei restului chinez

În algoritmul RSA calculele se fac modulo $n$ ${\ displaystyle n}$ $n$ , unde este $n$ ${\ displaystyle n}$ $n$ este un produs din două numere prime $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ . De obicei, dimensiunea $n$ ${\ displaystyle n}$ $n$ este 1024, 2048 sau 4096 biți, ceea ce face calculele foarte lungi. Utilizând teorema restului chinez, aceste calcule pot fi transportate de inel $\mathbb {Z} _{n}$ ${\ displaystyle \ mathbb {Z} _ {n}}$ $\ mathbb {Z} _ {n}$ la inel $\mathbb {Z} _{p}\times \mathbb {Z} _{q}$ ${\ displaystyle \ mathbb {Z} _ {p} \ times \ mathbb {Z} _ {q}}$ $\ mathbb {Z} _ {p} \ times \ mathbb {Z} _ {q}$ . Suma dimensiunilor de biți ai $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ este dimensiunea de biți a $n$ ${\ displaystyle n}$ $n$ , în acest fel calculele sunt mult simplificate.

O altă aplicație potențială a teoremei restului chinez este problema numărării soldaților într-o armată. Generalul poate face soldați să se alinieze în grupuri de 2, 3, 5, 7, 11 și așa mai departe și să numere soldații rămași care nu pot forma grupuri complete. După ce s-au făcut suficiente teste, generalul poate calcula cu ușurință câți soldați alcătuiesc armata, transformând un număr care ar dura câteva ore într-un altul care ar dura câteva minute.

Faptul că un număr foarte mare poate fi reprezentat de un număr mic de resturi relativ mici este, de asemenea, ideea centrală a sistemelor de număr rezidual .

Notă

^ Giovanni Giuseppe Nicosia, chineză, școală și matematică , Lulu, Bologna, 2010, pagina 62, secțiunea 3.2.23
^ Massimo Gobbino, Fișe olimpice , 2006.

Bibliografie

Tom M. Apostol , Introducere în teoria numerelor analitice , Springer-Verlag, New York, 1976. ISBN 0-387-90163-9 (capitolul 5.7).
Donald Knuth . The Art of Computer Programming , Volumul 2: Seminumerical Algorithms , Ediția a treia. Addison-Wesley, 1997. ISBN 0-201-89684-2 . Secțiunea 4.3.2 (pp. 286-291), exercițiul 4.6.2-3 (p. 456).
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein . Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001. ISBN 0262032937 . Secțiunea 31.5: Teorema restului chinez, pp. 873–876.

linkuri externe

Teorema restului chinezilor tăiați-nodul

Controlul autorității	LCCN (EN) sh97002778 · GND (DE) 4470755-1

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Giovanni Giuseppe Nicosia, chineză, școală și matematică , Lulu, Bologna, 2010, pagina 62, secțiunea 3.2.23

[2] Massimo Gobbino, Fișe olimpice , 2006.

[1]

[2]

V · D · M Teoria numerelor
Cele mai utilizate numere	Natural · Întreg · Par și impar
Principii generale	Principiul inducției · Principiul unei bune ordonări · Relația de echivalență
Secvențe de numere întregi	Factorial · Fibonacci · Număr de catalană · Număr Perrin · Număr de Euler · Secvență Mian-Chowla · Succesiunea lui Thue-Morse
Caracteristicile numerelor prime	Primul număr · lema lui Euclid · Teorema infinitate de numere prime · ciurul Eratostene · teste primality · Teorema fundamentală a aritmeticii · Total acoperire mine · Bézout Identitate · MCD · mcm · algoritmul lui Euclid · Teorema de Prime Numbers
Funcții aritmetice	Funcție multiplicativă · funcție aditivă · convoluție Dirichlet · funcția Euler Euler · funcția Möbius · funcția tau pe pozitiv · funcția sigmoidă · funcția Liouville · funcția Mertens
Aritmetica modulară	Teorema a restului chinez · teorema lui Fermat mici · teorema lui Euler · Criterii de divizibilitate · teorema lui Fermat pe sume de două pătrate · Wilson Teorema · reciprocitatea pătratică
Conjecturi	Conjectura lui Goldbach · Conjectura Polignac · Guess abc · conjectura primelor gemene · Conjectura lui Legendre · Noua conjectură Mersenne · Conjectura Collatz · Ipoteza Riemann
Alte	Problema lui Waring
Principalii teoreticieni	Fibonacci · Fermat · Gauss · Euler · Legendre · Riemann · Dirichlet
Disciplinele conexe	Teoria algebrică a numerelor · Teoria analitică a numerelor · Criptografie · Teoria computațională a numerelor