Hondarraren txinatar teorema

**Hondarraren teorema txinatarra** kongruentzien ekuazio sistemak ebazteko balio duen teorema da. Teorema hau aplikatzeko baldintza bakarra ondokoa da: ekuazioen moduluak beraien artean lehenak izan behar dira, hau da, zkh(m_1,m_2)=1 izan behar da m ekuazio sistemetako edozein ekuazioaren modulua izanik.

Hondarraren teorema txinatarrak zera dio: demagun kongruentzia sistema bat dugula eta bertako ekuazio guztien moduluak beraien artean lehenak direla. Orduak sistemak soluzio bakarra izango du M=m_1\cdot m_2 \cdot ... \cdot m_n moduluarekiko. Existitzen diren beste soluzio guztiak x\equiv y (mod M) motakoak izango dira.

## Frogapena 
Kongruentzia sistema bat:

x \equiv b_1 (mod m_1)

x \equiv b_2 (mod m_2)

\cdots

x \equiv b_n (mod m_n)

non zkh(m_i,m_j)=1 den i\neq j denean

Izan bitez M = m_1 \cdot m_2 \cdot \ldots \cdot m_n modulu guztien biderkadura eta M_j = M/m_j \quad (j=1,2,\ldots,n)  m_j ez diren moduluen biderkadura. Hipotesiagatik badakigu zkh(m_i,m_j)=1 \quad i\neq j denean, beraz, zkh(M_j,m_j) = 1 da. Ondorioz, M_jx \equiv 1 (mod m_j)-k soluzio bat du eta bakarra da m_j moduluarekiko. Soluzio horri x_j deituko diogu.

x = b_1 M_1 x_1 + \ldots + b_n M_n x_n sistema osoaren soluzioa izango da. Soluzioa dela ikustekoa x \equiv b_i (mod m_i) betetzen dela ikusiko dugu. M_n bakoitza m_i-gatik zatigarria da M_i izan ezik. Beraz b_1 M_1 x_1 + \ldots + b_n M_n x_n \equiv b_i M_i x_i (mod m_i). x_i-k  M_i x_i \equiv 1 (mod m_i) betetzen duenez b_1 M_1 x_1 + \ldots + b_n M_n x_n \equiv b_i M_i x_i \equiv b_i (mod m_i). Beraz, x soluzioa da.

M moduluarekiko bakarra dela ziurtatzeko, x eta y, bi soluzio hartuko dutugu. Bi horiek soluzioak badira x \equiv b_j (mod m_j) eta y \equiv b_j (mod m_j) j=1,2,\ldots,n guztietarako. Beraz,  x \equiv y (mod m_j) j=1,2,\ldots,n guztietarako. Moduluak elkarrekiko lehenak direnez  x \equiv y (mod M)  dugu. Orduan, badakigu sistemaren soluzio guztiak kongruenteak direla M moduluarekiko.

## Adibidea 
Lehen esan bazala, kongruentzia linealetako sistemak ebazteko balio du teorema honek. Ebatzi dezagun, bat hondarraren teorema txinatarra nola aplikatzen den ikusteko. Demagun, hondako kongruentzia sistema dugula:

\begin{cases} x\equiv2\pmod{5} \\ x\equiv4\pmod{7} \\x\equiv3\pmod{9} \end{cases}

Lehenik eta behin kalkulatu dezagun 

M_i=5\times7\times9=315.

Ondoren kalkulatu desagua modulu bakoitza, oro har, 

m_j .

m_1=63

m_2=45

m_3=35

Has gaitezen kongruentzia lineal bakoitza bere aldetik aztertzen:

**1.kasua**

x_1\equiv1\pmod{5}

x_1\equiv0\pmod{63}

Bezouten identitatea erabiliz: 

1=3-2=3-(5-3)=2\times3-5=2(63-5\times12)-5=263-25\times5

Beraz, 

x_1=2\times63

**2.kasua**

x_2\equiv1\pmod{7}

x_2\equiv0\pmod{45}

Bezouten identitatea erabiliz: 

1=-2\times45+13\times7

Beraz, 

x_2=2\times-90

**3.kasua**

x_3\equiv1\pmod{9}

x_3\equiv0\pmod{35}

Bezouten identitatea erabiliz: 

1=-35+4\times9

Beraz, 

x_3=-35

Teoremaren frogan erabili dugun notazioarekin,

x_1 = 2\times63, x_2 = -90, x_3 = -35. Horiekin soluzio bat idatziko dugu:

x=2\times63\times2-90\times4-35\times3=102\pmod{315}

Sistemaren soluzio guztiak 

x = 102 + 315k dira,k\in Z edozein izanik

## Erabilpenak 
### Segiden zenbaketa 
Hondarraren txinatar teorema Gödelen segiden zenbaketarako erabiltzen da, Gödel-en osatugabetasunaren teoremak frogatzeko erabili zenean.

### Fourier-en transformatu azkarra (FTT) 
Faktore lehenaren FTT algoritmoak hondarraren teorema txinatarra erabiltzen du  n_1 n_2 tamainuko Fourier-en transformatu azkarraren zenbaketa txikitzeko  n_3 n_4 tamainuko zenbaketa batera,  n_3 eta  n_4 elkarrekiko lehenak direla zihurtatuz.

### Enkriptatzea 
RSAren algoritmo gehienek hondarraren teorema txinatarra erabiltzen dute HTTPS ziurtagiriak sinatzeko eta deszifratzeko.

Hondarraren teorema txinatarra mezu ezkutuak bidaltzeko ere erabil daiteke. Pertsona talde batean mezu batzuk partekatzean datza. Denek batera bidalitako mezu horietatik mezu sekretua lor dezakete. Mezu horietako bakoitza kongruentzia bat da, eta kongruentzia sistema ebaztean hondarraren teorema txinatarra erabiliz, mezu sekretua lortzen da.

## Kanpo estekak