Kinesiska restklassatsen

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif
icon_anmal.gif
rp-wp-sv.gif

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 bi är en lösning till kongruensen

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

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

Exempel

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.

Hämtad från "https://sv.rilpedia.org/wiki/Kinesiska_restklassatsen"
Personliga verktyg