Fölérendelt lap:22.3. TételA kínai maradéktétel alternatív megfogalmazása

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.

∎

Iratkozz fel a hírlevelünkre