youproof.orgDeep Math. Human Access.

Bizonyítás

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

x=kp+ax=kp+a

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

kp+a⏟=x≡b(modq)\underbrace{kp+a}_{=x}\equiv b \pmod q

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

kp≡b−a(modq)kp\equiv b-a\pmod q

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

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

x1≡a(modp)x1≡b(modq)\begin{aligned}x_1&\equiv a\pmod p \\ x_1&\equiv b\pmod q\end{aligned}

Másrészt:

x2≡a(modp)x2≡b(modq)\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 x1x_1 és x2x_2 egész számok kongruensek egymással mindkét modulus szerint, azaz:

x1≡x2(modp)x1≡x2(modq)\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 x1−x2x_1-x_2 különbség többszöröse pp-nek is és qq-nak is, azaz:

p∣x1−x2q∣x1−x2\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 kk egész szám, hogy

pk=x1−x2pk=x_1-x_2

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

q∣pk⏟=x1−x2q|\underbrace{pk}_{=x_1-x_2}

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

q∣kq|k

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

ql=kql=k

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

p⋅ql⏟=k=pq⋅l=x1−x2p\cdot\underbrace{ql}_{=k}=pq\cdot l=x_1-x_2

Azaz pq∣x1−x2pq|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:

x1≡x2(modpq)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 pqpq maradékosztályba esik.

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

s≡a(modp)s≡b(modq)\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 tt 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 tt ugyanabban a modulo pqpq maradékosztályban van, mint ss, ezért igaz az alábbi:

s≡t(modpq)s\equiv t\pmod{pq}

Minthogy a p∣pqp|pq valamint a q∣pqq|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:

s≡t(modp)s≡t(modq)\begin{aligned}s&\equiv t\pmod p \\ s&\equiv t\pmod q\end{aligned}

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

∎