Twierdzenie chińskie o resztach

Tw. chińskie o resztach

Jeżeli $n_{1}, …, n_{k}$ są parami względnie pierwsze oraz $r_{1}, … ,r_{k}$ są liczbami całkowitymi, to istnieje liczba całkowita $x$ taka, że $$\begin{cases} x \equiv r_{1} \ ({\bmod {\ }}n_{1})\\ x \equiv r_{2} \ ({\bmod {\ }}n_{2})\\ \vdots\\ x \equiv r_{k} \ ({\bmod {\ }}n_{k})\\ \end{cases} $$ Liczba $x$ jest wyznaczona jednoznacznie modulo $n_{1}\cdot … \cdot n_{k}$.

Przykładowe zadania

Zadanie 1.
Liczba kostek w bardzo dużej czekoladzie równa jest $x$. Jeśli podzielić czekoladę na 3 części, to zostanie 1 kostka. Przy podziale na 5 części zostaną 3 kostki, a w przypadku podziału na 7 części zostaną 2 kostki. Ile kostek ma czekolada?
Należy rozwiązać układ kongruencji:
$$\begin{cases} x \equiv 1 \ ({\bmod {\ }}3)\\ x \equiv 3 \ ({\bmod {\ }}5)\\ x \equiv 2 \ ({\bmod {\ }}7)\\ \end{cases} $$ Analizujemy pierwszą kongruencję $$x\equiv 1 \ ({\bmod {\ }}3) \Rightarrow x =3k+1$$ Wstawiamy tak obliczone $x$ do drugiej kongruencji $$3k+1 \equiv 3 \ ({\bmod {\ }}5) \Rightarrow 3k \equiv 2\ ({\bmod {\ }}5) $$ Szukamy odwrotności liczby 3 w zbiorze modulo 5, innymi słowy szukamy takiej liczby $a^{’}$, że
$3 \cdot a^{’} = 1 $. Metodą prób i błędów dowiadujemy się, że $a^{’}=2$. Zatem mnożymy obie strony kongruencji przez 2. $$1\cdot k \equiv 4 \ ({\bmod {\ }}5) \Rightarrow k = 5\cdot u + 4 $$ Zatem $$x =3(5u+4)+1=15u+13$$ Wstawiamy do trzeciej kongruencji $$15u+13 \equiv 2 \ ({\bmod {\ }}7)\Rightarrow 14u+u +14-1 \equiv 2 \ ({\bmod {\ }}7)\Rightarrow$$ $$ u-1 \equiv 2 \ ({\bmod {\ }}7) \Rightarrow u \equiv 3 \ ({\bmod {\ }}7)\Rightarrow u = 7t+3$$ Ostatecznie $$x=15(7t+3)+13 = 105t+58.$$ Odp.
Czekolada ma 58 kostek.

Zadanie 2

W sadzie zebrano jabłka, których nie było więcej niż 1000. Gdyby podzielić jabłka równo do 7 koszy, to zostanie 1 jabłko. Gdyby podzielić jabłka równo do 13 koszy, to zostanie 6 jabłek. Można jednak podzielić jabłka równo na 11 części. Ile zebrano jabłek?
Należy rozwiązać układ kongruencji:
$$\begin{cases} x \equiv 1 \ ({\bmod {\ }}7)\\ x \equiv 6 \ ({\bmod {\ }}13)\\ x \equiv 0 \ ({\bmod {\ }}11)\\ \end{cases} $$ Analizujemy pierwszą kongruencję
$$x \equiv 1 \ ({\bmod {\ }}7) \Rightarrow x = 7k + 1$$ Wstawiamy tak obliczone $x$ do drugiej kongruencji $$7k+1 \equiv 6 \ ({\bmod {\ }}13) \Rightarrow 7k \equiv 5({\bmod {\ }}13) \Rightarrow k \equiv 10({\bmod {\ }}13) $$ Zatem $$k=13s+10\Rightarrow x=7(13s+10)+1=7\cdot 13s+71 $$ Wstawiamy do trzeciej kongruencji $$91s+71 \equiv 0 \ ({\bmod {\ }}11)$$ $$91s \equiv -71 \ ({\bmod {\ }}11) \Rightarrow 88s+3s \equiv 77-71 \ ({\bmod {\ }}11)\Rightarrow 3s\equiv 6 \ ({\bmod {\ }}11)$$ czyli $$s \equiv 2 \ ({\bmod {\ }}11) \Rightarrow s=11t+2$$ Ostatecznie $$x=91(11t+2)+71=1001s+182+71=1001s+253$$ Odp.
W sadzie zebrano 253 jablek.