youproof.orgDeep Math. Human Access.

22.3. Tétel

A kínai maradéktétel alternatív megfogalmazása

Legyenek p>0p\gt 0 és q>0q\gt 0 valamilyen pozitív egész számok, továbbá tegyük fel, hogy pp és qq egymáshoz relatív prímek. Ekkor minden (A;B)∈Z/pZ×Z/qZ(A;B)\in \Z/p\Z \times \Z/q\Z rendezett pár esetén A∩B∈Z/pqZA\cap B\in \Z/pq\Z.

Tegyük fel, hogy az x1x_1 és x2x_2 egész számok kielégítik az alábbi kongruenciákat:

px1≡1(modq)qx2≡1(modp)\begin{aligned}px_1&\equiv 1\pmod q \\ qx_2&\equiv 1\pmod p\end{aligned}

Amennyiben az AA és BB maradékosztályokat rendre valamilyen aa és bb egész számokkal reprezentáljuk – azaz A=[a]pA=[a]_p és B=[b]qB=[b]_q –, akkor az alábbi képlet az A∩BA\cap B maradékosztály egy reprezentánselemét szolgáltatja:

A∩B=[aqx2+bpx1]pqA\cap B=[aqx_2 + bpx_1]_{pq}

♣