Bizonyítás
A tétel bizonyításához az alábbi két állítást kell igazolni:
- Az X maradékosztály valóban az (A;B)\in \Z/p\Z\times \Z/q\Z maradékosztálypár metszete, azaz X=A\cap B.
- Nincs másik olyan maradékosztálypár a \Z/p\Z\times \Z/q\Z halmazban, amelynek X a metszete lenne.
Az 1. állítás: a 19.2. Definíció utáni megjegyzés 5. pontja alapján X és A\cap B akkor és csak akkor egyezik meg, ha egymásnak részhalmazai, azaz teljesülnek az alábbiak:
Az X\sube A\cap B tartalmazási reláció a 19.2. Definíció alapján azt jelenti, hogy az X=[s]_{pq} maradékosztály minden eleme egyúttal az A=[s]_p-nek is és B=[s]_q-nak is eleme. Legyen például t\in X egy tetszőleges elem az X=[s]_{pq} maradékosztályban. Ezt úgy is megfogalmazhatjuk, hogy t ugyanúgy az X maradékosztályt reprezentálja, mint s. Azaz [s]_{pq}=[t]_{pq}, ami ugye az alábbi kongruenciát jelenti:
Mivel azonban a p|pq és q|pq oszthatóságok nyilvánvalóan teljesülnek, ezért a 20.2. Tétel 7. pontja miatt teljesülnek az alábbi kongruenciák is:
Tehát t benne van az A=[s]_p és B=[s]_q maradékosztályokban, azaz valóban teljesül az X\sube A\cap B tartalmazási reláció.
Most az A\cap B\sube X tartalmazási relációt igazoljuk. Ez a 19.2. Definíció alapján azt jelenti, hogy az A=[s]_p és B=[s]_q maradékosztályok közös elemei egyúttal az X=[s]_{pq} maradékosztálynak is elemei. Legyen például t\in A\cap B egy tetszőleges elem az A=[s]_p és B=[s]_q maradékosztályok metszetében. Ezt úgy is megfogalmazhatjuk, hogy t ugyanúgy benne van mind az A, mind pedig a B maradékosztályokban, mint s.
Az A=[s]_p maradékosztályba pontosan azok az egész számok tartoznak bele, amelyeket az alábbi kongruenciába az x ismeretlen helyére behelyettesítve a kongruencia teljesül:
Ehhez hasonlóan a B=[s]_q maradékosztályba pontosan azok az egész számok tartoznak bele, amelyeket az alábbi kongruenciába az x ismeretlen helyére behelyettesítve a kongruencia teljesül:
A fentebb említett t tehát s-sel karöltve kielégíti az iménti két kongruenciából álló rendszert. Ám a kínai maradéktétel állítása szerint minden ilyen tulajdonságú egész szám ugyanabba az egyetlen modulo pq maradékosztályba esik. Az nyilvánvaló, hogy s\in X, hiszen a tétel szövege alapján ő épp az X maradékosztály reprezentánseleme. Következésképp t is szükségképpen X-ben van, azaz valóban teljesül az A\cap B\sube X tartalmazási reláció.
Mivel mindkét irányú tartalmazási reláció teljesül X és A\cap B között, ezért a két halmaz valóban megegyezik.
A 2. állítás: Tegyük fel indirekt, hogy létezik egy (A;B)-től különböző (C;D) maradékosztálypár a \Z/p\Z\times \Z/q\Z halmazban, amelynek X a metszete, azaz:
Tegyük fel továbbá, hogy a C maradékosztályt a c egész számmal, míg a D maradékosztályt a d egész számmal reprezentáljuk, azaz:
Legyen t egy tetszőleges elem az X=[s]_{pq} maradékosztályban. Egyrészt a fentebb egyszer már leírt gondolatmenetet megismételve ez az alábbi kongruenciákat jelenti:
Másrészt viszont az indirekt feltételezésünk miatt X a C=[c]_p és D=[d]_q maradékosztályok metszete. Emiatt t ugyanúgy benne van a C=[c]_p maradékosztályban, mint c, valamint ugyanúgy benne van a D=[d]_q maradékosztályban, mint d. Teljesülnek tehát az alábbi kongruenciák:
A 20.2. Tétel 3. pontja miatt teljesülnek tehát az alábbi kongruenciák is:
Azaz egyrészt az s által reprezentált modulo p maradékosztály – ez ugye az A halmaz – megegyezik a c által reprezentált modulo p maradékosztállyal – ez pedig ugye a C halmaz. Másrészt az s által reprezentált modulo q maradékosztály – ez ugye a B halmaz – megegyezik a d által reprezentált modulo q maradékosztállyal – ez pedig ugye a D halmaz.
Minthogy A=C és B=D, ezért indirekt feltételezésünkkel ellentétben az (A;B) maradékosztálypár mégiscsak megegyezik a (C;D) maradékosztálypárral. Azaz a 2. állításnak megfelelően az (A;B) páron kívül nincs másik olyan maradékosztálypár a \Z/p\Z\times \Z/q\Z halmazban, amelynek X a metszete lenne.
∎