Kinesiska restklassatsen

Från Wikipedia
Hoppa till: navigering, sök

Kinesiska restklassatsen (eller Kinesiska restsatsen) inom talteorin säger att om heltalen n_1,\ldots ,n_k är parvis relativt prima och a_1,a_2,\ldots,a_k är givna heltal så har kongruenssystemet:


\begin{array}{lcl}
x &\equiv& a_1\;(\mathrm{mod}\;n_1) \\
x &\equiv& a_2\;(\mathrm{mod}\;n_2) \\
  &\vdots&                       \\
x &\equiv& a_k\;(\mathrm{mod}\;n_k) \\
\end{array}

en unik lösning modulo N = n_1 n_2 \ldots n_k.

En lösning till kongruenssystemet ges av


x = \sum_{i=1}^k a_i b_i (N/n_i)

om varje b_i är en lösning till kongruensen


b_i (N/n_i) \equiv 1\;(\mathrm{mod}\;n_i).

Enligt Eulers sats kan man, om n_i>1, exempelvis ta b_i \equiv (N/n_i)^{\varphi(n_i)-1} (mod n_i), där \varphi är Eulers fi-funktion.

Exempel[redigera | redigera wikitext]

Jag tänker på ett tal. Om jag delar det med 3 får jag resten 2. Om jag delar det med 7 får jag resten 3. Om jag delar det med 10 får jag resten 3. Vilket är talet?

Vi formulerar problemet som ett kongruenssystem:


\begin{array}{lcl}
x &\equiv& 2\;(\mathrm{mod}\;3) \\
x &\equiv& 3\;(\mathrm{mod}\;7) \\
x &\equiv& 3\;(\mathrm{mod}\;10) \\
\end{array}

Eftersom 3, 7, 10 är parvis relativt prima säger kinesiska restsatsen att det finns en unik lösning modulo deras produkt, det vill säga 210. Vi har \varphi(3)=2,\ \varphi(7)=6,\ \varphi(10)=4, så vi tar b_1\equiv 70^1\equiv 1 (mod 3), b_2\equiv 30^5\equiv 2^5=8\cdot 4\equiv 4 (mod 7), b_3\equiv 21^3\equiv 1 (mod 10). Då är alltså enligt ovan


x = 2\cdot 1\cdot 70 + 3\cdot 4\cdot 30 + 3\cdot 1\cdot 21 = 563

en lösning. Men lösningen är inte unik: genom att lägga på multipler av 210 får vi nya lösningar. Exempelvis är 563-2\cdot 210 = 143 en lösning. Enligt satsen får vi alla lösningar genom att lägga på multipler av 210, så 143 är den minsta positiva lösningen.

Externa länkar[redigera | redigera wikitext]

http://solmu.math.helsinki.fi/2012/3/kiinalainen.pdf