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, ${\displaystyle 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 ${\displaystyle M=m_{1}\cdot m_{2}\cdot ...\cdot m_{n}}$ moduluarekiko. Existitzen diren beste soluzio guztiak ${\displaystyle x\equiv y(modM)}$ motakoak izango dira.

Frogapena

Kongruentzia sistema bat:

${\displaystyle x\equiv b_{1}}$ (mod ${\displaystyle m_{1}}$)

${\displaystyle x\equiv b_{2}}$ (mod ${\displaystyle m_{2}}$)

${\displaystyle \cdots }$

${\displaystyle x\equiv b_{n}}$ (mod ${\displaystyle m_{n}}$)

non ${\displaystyle zkh(m_{i},m_{j})=1}$ den ${\displaystyle i\neq j}$ denean

Izan bitez ${\displaystyle M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n}}$ modulu guztien biderkadura eta ${\displaystyle M_{j}=M/m_{j}\quad (j=1,2,\ldots ,n)}$ ${\displaystyle m_{j}}$ ez diren moduluen biderkadura. Hipotesiagatik badakigu ${\displaystyle zkh(m_{i},m_{j})=1\quad i\neq j}$ denean, beraz, ${\displaystyle zkh(M_{j},m_{j})=1}$ da. Ondorioz, ${\displaystyle M_{j}x\equiv 1}$ (mod ${\displaystyle m_{j}}$)-k soluzio bat du eta bakarra da ${\displaystyle m_{j}}$ moduluarekiko. Soluzio horri ${\displaystyle x_{j}}$ deituko diogu.

${\displaystyle x=b_{1}M_{1}x_{1}+\ldots +b_{n}M_{n}x_{n}}$ sistema osoaren soluzioa izango da. Soluzioa dela ikustekoa ${\displaystyle x\equiv b_{i}}$ (mod ${\displaystyle m_{i}}$) betetzen dela ikusiko dugu. ${\displaystyle M_{n}}$ bakoitza ${\displaystyle m_{i}}$-gatik zatigarria da ${\displaystyle M_{i}}$ izan ezik. Beraz ${\displaystyle b_{1}M_{1}x_{1}+\ldots +b_{n}M_{n}x_{n}\equiv b_{i}M_{i}x_{i}}$ (mod ${\displaystyle m_{i}}$). ${\displaystyle x_{i}}$-k ${\displaystyle M_{i}x_{i}\equiv 1}$ (mod ${\displaystyle m_{i}}$) betetzen duenez ${\displaystyle b_{1}M_{1}x_{1}+\ldots +b_{n}M_{n}x_{n}\equiv b_{i}M_{i}x_{i}\equiv b_{i}}$ (mod ${\displaystyle m_{i}}$). Beraz, ${\displaystyle x}$ soluzioa da.

${\displaystyle M}$ moduluarekiko bakarra dela ziurtatzeko, x eta y, bi soluzio hartuko dutugu. Bi horiek soluzioak badira ${\displaystyle x\equiv b_{j}}$ (mod ${\displaystyle m_{j}}$) eta ${\displaystyle y\equiv b_{j}}$ (mod ${\displaystyle m_{j}}$) ${\displaystyle j=1,2,\ldots ,n}$ guztietarako. Beraz, ${\displaystyle x\equiv y}$ (mod ${\displaystyle m_{j}}$) ${\displaystyle j=1,2,\ldots ,n}$ guztietarako. Moduluak elkarrekiko lehenak direnez ${\displaystyle x\equiv y}$ (mod ${\displaystyle M}$) dugu. Orduan, badakigu sistemaren soluzio guztiak kongruenteak direla ${\displaystyle 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:

${\displaystyle {\begin{cases}x\equiv 2{\pmod {5}}\\x\equiv 4{\pmod {7}}\\x\equiv 3{\pmod {9}}\end{cases}}}$

Lehenik eta behin kalkulatu dezagun ${\displaystyle M_{i}=5\times 7\times 9=315}$.

Ondoren kalkulatu desagua modulu bakoitza, oro har, ${\displaystyle m_{j}}$ .

${\displaystyle m_{1}=63}$

${\displaystyle m_{2}=45}$

${\displaystyle m_{3}=35}$

Has gaitezen kongruentzia lineal bakoitza bere aldetik aztertzen:

1.kasua

${\displaystyle x_{1}\equiv 1{\pmod {5}}}$

${\displaystyle x_{1}\equiv 0{\pmod {63}}}$

Bezouten identitatea erabiliz: ${\displaystyle 1=3-2=3-(5-3)=2\times 3-5=2(63-5\times 12)-5=263-25\times 5}$

Beraz, ${\displaystyle x_{1}=2\times 63}$

2.kasua

${\displaystyle x_{2}\equiv 1{\pmod {7}}}$

${\displaystyle x_{2}\equiv 0{\pmod {45}}}$

Bezouten identitatea erabiliz: ${\displaystyle 1=-2\times 45+13\times 7}$

Beraz, ${\displaystyle x_{2}=2\times -90}$

3.kasua

${\displaystyle x_{3}\equiv 1{\pmod {9}}}$

${\displaystyle x_{3}\equiv 0{\pmod {35}}}$

Bezouten identitatea erabiliz: ${\displaystyle 1=-35+4\times 9}$

Beraz, ${\displaystyle x_{3}=-35}$

Teoremaren frogan erabili dugun notazioarekin,${\displaystyle x_{1}=2\times 63,x_{2}=-90,x_{3}=-35}$. Horiekin soluzio bat idatziko dugu:

${\displaystyle x=2\times 63\times 2-90\times 4-35\times 3=102{\pmod {315}}}$

Sistemaren soluzio guztiak ${\displaystyle x=102+315kdira,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 ${\displaystyle n_{1}n_{2}}$ tamainuko Fourier-en transformatu azkarraren zenbaketa txikitzeko ${\displaystyle n_{3}n_{4}}$ tamainuko zenbaketa batera, ${\displaystyle n_{3}}$ eta ${\displaystyle 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

• Datuak: Q193878