youproof.orgDeep Math. Human Access.

Bizonyítás

A tétel bizonyításához az alábbi két állítást kell igazolni:

  1. Az XX maradékosztály valóban az (A;B)∈Z/pZ×Z/qZ(A;B)\in \Z/p\Z\times \Z/q\Z maradékosztálypár metszete, azaz X=A∩BX=A\cap B.
  2. Nincs másik olyan maradékosztálypár a Z/pZ×Z/qZ\Z/p\Z\times \Z/q\Z halmazban, amelynek XX a metszete lenne.

Az 1. állítás: a 19.2. Definíció utáni megjegyzés 5. pontja alapján XX és A∩BA\cap B akkor és csak akkor egyezik meg, ha egymásnak részhalmazai, azaz teljesülnek az alábbiak:

X⊆A∩BX⊇A∩B\begin{aligned} X&\sube A\cap B \\ X&\supe A\cap B \end{aligned}

Az X⊆A∩BX\sube A\cap B tartalmazási reláció a 19.2. Definíció alapján azt jelenti, hogy az X=[s]pqX=[s]_{pq} maradékosztály minden eleme egyúttal az A=[s]pA=[s]_p-nek is és B=[s]qB=[s]_q-nak is eleme. Legyen például t∈Xt\in X egy tetszőleges elem az X=[s]pqX=[s]_{pq} maradékosztályban. Ezt úgy is megfogalmazhatjuk, hogy tt ugyanúgy az XX maradékosztályt reprezentálja, mint ss. Azaz [s]pq=[t]pq[s]_{pq}=[t]_{pq}, ami ugye az alábbi kongruenciát jelenti:

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

Mivel azonban a p∣pqp|pq és q∣pqq|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:

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

Tehát tt benne van az A=[s]pA=[s]_p és B=[s]qB=[s]_q maradékosztályokban, azaz valóban teljesül az X⊆A∩BX\sube A\cap B tartalmazási reláció.

Most az A∩B⊆XA\cap B\sube X tartalmazási relációt igazoljuk. Ez a 19.2. Definíció alapján azt jelenti, hogy az A=[s]pA=[s]_p és B=[s]qB=[s]_q maradékosztályok közös elemei egyúttal az X=[s]pqX=[s]_{pq} maradékosztálynak is elemei. Legyen például t∈A∩Bt\in A\cap B egy tetszőleges elem az A=[s]pA=[s]_p és B=[s]qB=[s]_q maradékosztályok metszetében. Ezt úgy is megfogalmazhatjuk, hogy tt ugyanúgy benne van mind az AA, mind pedig a BB maradékosztályokban, mint ss.

Az A=[s]pA=[s]_p maradékosztályba pontosan azok az egész számok tartoznak bele, amelyeket az alábbi kongruenciába az xx ismeretlen helyére behelyettesítve a kongruencia teljesül:

x≡s(modp)x\equiv s\pmod p

Ehhez hasonlóan a B=[s]qB=[s]_q maradékosztályba pontosan azok az egész számok tartoznak bele, amelyeket az alábbi kongruenciába az xx ismeretlen helyére behelyettesítve a kongruencia teljesül:

x≡s(modq)x\equiv s\pmod q

A fentebb említett tt tehát ss-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 pqpq maradékosztályba esik. Az nyilvánvaló, hogy s∈Xs\in X, hiszen a tétel szövege alapján ő épp az XX maradékosztály reprezentánseleme. Következésképp tt is szükségképpen XX-ben van, azaz valóban teljesül az A∩B⊆XA\cap B\sube X tartalmazási reláció.

Mivel mindkét irányú tartalmazási reláció teljesül XX és A∩BA\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)(A;B)-től különböző (C;D)(C;D) maradékosztálypár a Z/pZ×Z/qZ\Z/p\Z\times \Z/q\Z halmazban, amelynek XX a metszete, azaz:

C∩D=XC\cap D=X

Tegyük fel továbbá, hogy a CC maradékosztályt a cc egész számmal, míg a DD maradékosztályt a dd egész számmal reprezentáljuk, azaz:

C=[c]pD=[d]q\begin{aligned}C&=[c]_p \\ D&=[d]_q\end{aligned}

Legyen tt egy tetszőleges elem az X=[s]pqX=[s]_{pq} maradékosztályban. Egyrészt a fentebb egyszer már leírt gondolatmenetet megismételve ez az alábbi kongruenciákat jelenti:

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

Másrészt viszont az indirekt feltételezésünk miatt XX a C=[c]pC=[c]_p és D=[d]qD=[d]_q maradékosztályok metszete. Emiatt tt ugyanúgy benne van a C=[c]pC=[c]_p maradékosztályban, mint cc, valamint ugyanúgy benne van a D=[d]qD=[d]_q maradékosztályban, mint dd. Teljesülnek tehát az alábbi kongruenciák:

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

A 20.2. Tétel 3. pontja miatt teljesülnek tehát az alábbi kongruenciák is:

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

Azaz egyrészt az ss által reprezentált modulo pp maradékosztály – ez ugye az AA halmaz – megegyezik a cc által reprezentált modulo pp maradékosztállyal – ez pedig ugye a CC halmaz. Másrészt az ss által reprezentált modulo qq maradékosztály – ez ugye a BB halmaz – megegyezik a dd által reprezentált modulo qq maradékosztállyal – ez pedig ugye a DD halmaz.

Minthogy A=CA=C és B=DB=D, ezért indirekt feltételezésünkkel ellentétben az (A;B)(A;B) maradékosztálypár mégiscsak megegyezik a (C;D)(C;D) maradékosztálypárral. Azaz a 2. állításnak megfelelően az (A;B)(A;B) páron kívül nincs másik olyan maradékosztálypár a Z/pZ×Z/qZ\Z/p\Z\times \Z/q\Z halmazban, amelynek XX a metszete lenne.

∎