Episode I

Alice és Bob

. rész: A kínai maradéktétel alternatív megfogalmazása

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

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

\begin{aligned}p\cdot x_1&\equiv 1\pmod q \\ q\cdot x_2&\equiv 1\pmod p\end{aligned}

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

A\cap B=[a\cdot q\cdot x_2 + b\cdot p\cdot x_1]_{pq}