Page 31 - MATINF Nr. 13-14

a
Teorema chinezeasc˘ a resturilor 31

Inversul modular al num˘arului a se poate determina prin ˆıncercarea tuturor valorilor dintre
1 s , i m − 1, sau, ˆın mod eficient, prin utilizarea algoritmului extins al lui Euclid, algoritm
constructiv care demonstreaz˘a s , i existent , a sa (a se vedea, de exemplu, [2]).

4. Sistemul format din congruent , ele x ≡ a (mod m) s , i x ≡ b (mod n) are solut , ie dac˘a s , i
a
a
numai dac˘ a ≡ b (mod cmmdc(a, b)), iar ˆın acest caz solut , ia este unic˘ mod cmmmc(m, n).
Demonstrat , ie:
Fie d = cmmdc(m, n).

,,⇒”
Avem x = m ∗ p + a s , i x = n ∗ q + b, deci m ∗ p − n ∗ q = b − a.

Cum d|m s , i d|n, rezult˘a d|(b − a), adic˘a a ≡ b (mod d), deci condit , ia este necesar˘a.

,,⇐”

Ne folosim de algoritmul extins al lui Euclid, care rezolv˘a urm˘atoarea problem˘a:
Fiind dat , i doi ˆıntregi m s , i n care nu sunt simultan 0, s˘a se determine cel mai mare divizor
comun al lor, d, s , i doi ˆıntregi u s , i v astfel ˆıncˆat m ∗ u + n ∗ v = d (Identitatea lui B´ezout).

Algoritmul extins al lui Euclid ne asigur˘ existent , a ˆıntregilor u s , i v.
a
Cum din ipotez˘ avem a ≡ b (mod d) rezult˘a b − a = d ∗ k;
a
Acum ˆınmult , im cu k identitatea lui B´ezout s , i rezult˘a ca m ∗ u ∗ k + n ∗ v ∗ k = b − a

a
a
Notˆand u ∗ k = p, v ∗ k = −q rezult˘ c˘ m ∗ p + a = n ∗ q + b, deci sistemul are solut , ie.
a
Unicitatea: Dac˘ x 1 s , i x 2 sunt dou˘ solut , ii, atunci
a
x 1 ≡ x 2 ≡ a (mod m), deci m|(x 1 − x 2 );
x 1 ≡ x 2 ≡ b (mod n), deci n|(x 1 − x 2 ).

Deoarece x 1 − x 2 este multiplu comun pentru m s , i n, atunci acesta este divizibil s , i cu
cmmmc(m, n), deci x 1 ≡ x 2 (mod cmmmc(m, n)).
ˆ
In ,,Disquisitiones Arithmeticae”, Gauss generalizeaz˘a problema lui Sun Zi, definind astfel
a
a
teorema chinez˘ a resturilor s , i a oferit o solut , ie general˘ pentru un sistem de ecuat , ii de congruent , ˘
a
a
liniar˘ ˆıntr-o singur˘ variabil˘a.
a
ˆ a
In termeni matematici moderni, dat , i de Gauss, teorema chinez˘ a resturilor este urm˘atoarea:
Fie m 1 , m 2 , . . . , m n ∈ N, cu proprietatea c˘ (m i , m j ) = 1 pentru orice i 6= j. Atunci, pentru
a
orice a 1 , a 2 , . . . , a n ∈ Z, sistemul de congruent , e:
x ≡ a 1 (mod m 1 ), x ≡ a 2 (mod m 2 ), . . . , x ≡ a n (mod m n )

admite solut , ie, iar toate solut , iile sunt congruente modulo M = m 1 m 2 . . . m n .

Observat , ii importante:

1. Condit , ia ca modulele s˘a fie prime ˆıntre ele dou˘a cˆate dou˘ este esent , ial˘a.
a
2. Dac˘a aceast˘a condit , ie nu este ˆındeplinit˘a, sistemul poate avea zero, una sau mai multe
solut , ii.