youproof.orgDeep Math. Human Access.

Bizonyítás

Először a kongruenciarendszer megoldhatóságát igazoljuk. Az első kongruenciát pontosan az a egész szám által reprezentált [a]_p maradékosztály elemei elégítik ki. Ezek a 20.4. Tétel alapján épp azok az x egész számok lesznek, amelyek felírhatók az alábbi alakban valamilyen alkalmasan megválasztott k paraméterrel:

x=kp+a

Ezt behelyettesítve a második kongruenciába:

\underbrace{kp+a}_{=x}\equiv b \pmod q

Azt kell tehát igazolnunk, hogy létezik ilyen k. Vegyük észre, hogy a kongruencia mindkét oldalából a-t kivonva az alábbi lineáris kongruenciát kapjuk:

kp\equiv b-a\pmod q

Ez viszont a 20.13. Tétel alapján megoldható k-ra, hiszen a tétel szövege szerint ugye p és q egymáshoz relatív prímek, azaz (p,q)\sim 1, ami nyilván osztója a kongruencia jobboldalának, azaz b-a-nak.

Másodszor azt mutatjuk meg, hogy minden, a kongruenciarendszert kielégítő egész szám ugyanabból a modulo pq maradékosztályból származik. Legyen ezért x_1 és x_2 két tetszőleges egész szám, amelyek mindkét kongruenciát kielégítik. Azaz egyrészt:

\begin{aligned}x_1&\equiv a\pmod p \\ x_1&\equiv b\pmod q\end{aligned}

Másrészt:

\begin{aligned}x_2&\equiv a\pmod p \\ x_2&\equiv b\pmod q\end{aligned}

Ez a 20.2. Tétel 3. pontja alapján azt jelenti, hogy az x_1 és x_2 egész számok kongruensek egymással mindkét modulus szerint, azaz:

\begin{aligned}x_1&\equiv x_2\pmod p \\ x_1&\equiv x_2\pmod q\end{aligned}

Ez a 20.1. Tétel 3. pontja alapján azt jelenti, hogy az x_1-x_2 különbség többszöröse p-nek is és q-nak is, azaz:

\begin{aligned}p&|x_1-x_2 \\ q&|x_1-x_2\end{aligned}

Az első oszthatóság azt jelenti, hogy létezik olyan k egész szám, hogy

pk=x_1-x_2

Következésképp a második oszthatóság így írható fel:

q|\underbrace{pk}_{=x_1-x_2}

Mivel q és p egymáshoz relatív prímek, ezért az Euklidészi lemma alapján:

q|k

Azaz létezik olyan l egész szám, hogy:

ql=k

Ezt behelyettesítve a pk=x_1-x_2 egyenletbe az alábbit kapjuk:

p\cdot\underbrace{ql}_{=k}=pq\cdot l=x_1-x_2

Azaz pq|x_1-x_2, ami a 20.1. Tétel 3. pontja alapján azt jelenti, hogy valóban teljesül az alábbi kongruencia:

x_1\equiv x_2\pmod{pq}

Tehát valóban igaz, hogy bármely két, a tételben szereplő kongruenciarendszert kielégítő egész szám ugyanabba a modulo pq maradékosztályba esik.

Végül azt kell igazolni, hogy ennek a bizonyos modulo pq maradékosztálynak minden eleme kielégíti a kongruenciarendszert. Tegyük fel ezért, hogy s egy olyan egész szám ebben a maradékosztályban, amelyre teljesül a kongruenciarendszer, azaz:

\begin{aligned}s&\equiv a\pmod p \\ s&\equiv b\pmod q\end{aligned}

Tegyük fel ezenkívül indirekt, hogy létezik olyan t egész szám ugyanebben a maradékosztályban, amelyre viszont nem teljesül legalább az egyik a tételben szereplő kongruenciák közül. Mivel t ugyanabban a modulo pq maradékosztályban van, mint s, ezért igaz az alábbi:

s\equiv t\pmod{pq}

Minthogy a p|pq valamint a q|pq oszthatóságok a 16.2. Tétel 7. pontja alapján teljesülnek, ezért a 20.2. Tétel 7. pontja miatt teljesülnek az alábbi kongruenciák is:

\begin{aligned}s&\equiv t\pmod p \\ s&\equiv t\pmod q\end{aligned}

Azaz t egyrészt ugyanabba a modulo p maradékosztályba esik, mint s, vagyis a 20.8. Definíció utáni megjegyzés alapján ő kielégíti az x\equiv a\pmod p kongruenciát. Másrészt ehhez hasonlóan t ugyanabba a modulo q maradékosztályba is esik, mint s, ezért ő kielégíti az x\equiv b\pmod q kongruenciát is. Így tehát t mégiscsak kielégíti a tételben szereplő kongruenciarendszert, ami ellentmond az indirekt feltételezésünknek. Az [s]_{pq} maradékosztálynak tehát valóban minden eleme kielégíti a kongruenciarendszert, ahogyan a tétel állítja.

∎