youproof.orgDeep Math. Human Access.

Bizonyítás

Az A=[a]_p és B=[b]_q maradékosztályok metszete pontosan azokat az egész számokat fogja tartalmazni, amelyek mindkét maradékosztályban benne vannak. Ezek ugye az alábbi kongruenciarendszert kielégítő egész számok lesznek:

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

A kínai maradéktétel alapján ezek az egész számok pontosan egy modulo pq maradékosztályt alkotnak, azaz valóban A\cap B\in \Z/pq\Z.

Most igazoljuk, hogy a tételben megadott képlet valóban az A\cap B maradékosztály egy reprezentánselemét adja. Ehhez azt kell megmutatni, hogy az aqx_2 + bpx_1 egész szám benne van ebben a halmazban. A halmazok közötti metszetképzésről szóló 19.3. Definíció alapján ez pontosan akkor teljesül, ha teljesül az alábbi mindkét feltétel:

\begin{aligned}aqx_2 + bpx_1 &\in A \\ aqx_2 + bpx_1 &\in B\end{aligned}

Nézzük először az első feltételt: Mivel az A halmaz egy modulo p maradékosztály, amelynek az a egész szám egy reprezentánseleme, ezért ez a feltétel pontosan akkor teljesül, ha fennáll az alábbi kongruencia:

aqx_2 + bpx_1 \equiv a\pmod p

A kongruencia baloldalán szereplő összeg második, bpx_1 tagja ugye p-nek többszöröse, így ő 0-val kongruens modulo p. Az összeg első, aqx_2 tagjában viszont a qx_2 tényező a tétel szövege alapján 1-gyel, és így ez a tag a-val kongruens modulo p. Összefoglalva tehát valóban teljesül a fenti kongruencia, mivel:

a\cdot \underbrace{qx_2}_{\equiv 1} + \underbrace{bpx_1}_{\equiv 0} \equiv a\pmod p

Most nézzük a második feltételt: Mivel a B halmaz egy modulo q maradékosztály, amelynek a b egész szám egy reprezentánseleme, ezért ez a feltétel pontosan akkor teljesül, ha fennáll az alábbi kongruencia:

aqx_2 + bpx_1 \equiv b\pmod q

A kongruencia baloldalán szereplő összeg első, aqx_2 tagja ugye q-nak többszöröse, így ő 0-val kongruens modulo q. Az összeg második, bpx_1 tagjában viszont a px_1 tényező a tétel szövege alapján 1-gyel, és így ez a tag b-vel kongruens modulo q. Összefoglalva tehát valóban teljesül a fenti kongruencia, mivel:

\underbrace{aqx_2}_{\equiv 0} + b\cdot \underbrace{px_1}_{\equiv 1} \equiv b\pmod q

A aqx_2 + bpx_1 összeg tehát benne van az A\cap B metszethalmazban, amely – mint láttuk – egy modulo pq maradékosztály, és így valóban annak egy reprezentánselemét adja.

∎