Page 29 - MATINF Nr. 13-14

˘
ARTICOLE SI NOTE DE INFORMATICA
,

a
Teorema chinezeasc˘ a resturilor

Viorel P˘aun 1

Teorema chinezeasc˘a a resturilor (sau Lema chinez˘a) este unul dintre cele mai vechi s , i
faimoase rezultate din teoria numerelor, avˆand o istorie care se ˆıntinde pe aproape dou˘a
a
milenii. Prima ment , iune documentat˘ a unei probleme de acest tip apare ˆın lucrarea ,,Sun Zi
Suanjing” (Manualul matematic al lui Sun Zi), scris˘a ˆın secolul al III-lea.

Problema clasic˘a: Avem un num˘ar necunoscut de obiecte. Dac˘ le num˘ar˘am cˆate 3, r˘amˆan
a
a
2; dac˘a le num˘ar˘am cˆate 5, r˘amˆan 3; dac˘ le num˘ar˘am cˆate 7, r˘amˆan 2. Cˆate obiecte sunt?
O legend˘a popular˘a spune c˘a generalii chinezi din acea period˘a (secolul al III-lea) foloseau
aceast˘ metod˘ pentru a afla num˘arul de soldat , i f˘ar˘ a-i num˘ara, cerˆandu-le doar s˘ se grupeze
a
a
a
a
ˆın 3 coloane, apoi ˆın 5 coloane s , i apoi ˆın 7 coloane s , i num˘arˆand resturile corespunz˘atoare r˘amase.
a
a
Exemplu: Generalul are o armat˘ de 1000-1100 soldat , i s , i vrea s˘ afle num˘arul lor exact.
El le cere soldat , ilor s˘a se grupeze astfel:
1. Cˆate 3: r˘amˆan 2 soldat , i.
2. Cˆate 5: r˘amˆan 3 soldat , i.
3. Cˆate 7: r˘amˆan 2 soldat , i.

Prin simpla observare a resturilor, generalul putea afla num˘arul exact al soldat , ilor (pentru
a
acest exemplu, cu o armat˘ de minim 1000 si maxim 1100, num˘arul exact de soldat , i este 1073).
Metoda de calcul (Algoritmul ,,Sun Zi”) se baza pe utilizarea unor ,,numere magice” desco-
perite de Sun Zi (bineˆınt , eles, valabile doar pentru grup˘ari cˆate 3, 5 s , i respective 7) s , i anume:
70, 21 s , i 15.

Aceste numere au urm˘atoarele propriet˘at , i:

70 se ˆımparte exact la 5 s , i la 7 s , i d˘a restul 1 la imp˘art , irea cu 3;

21 se ˆımparte exact la 3 s , i la 7 s , i d˘a restul 1 la imp˘art , irea cu 5;
15 se ˆımparte exact la 3 s , i la 5 s , i d˘a restul 1 la imp˘art , irea cu 7;

Metoda de calcul propus˘ este urm˘atoarea:
a
ˆ
1. Inmult , im fiecare ,,num˘ar magic” cu restul corespunz˘ator astfel:
70*2 (unde 2 este restul imp˘art , irii la 3)=140;

1
Lect. univ. dr., Universitatea Nat , ional˘a de S , tiint , ˘a s , i Tehnologie POLITEHNICA Bucures , ti, Centrul
Universitar Pites , ti, viop23@yahoo.com

29