Tw. chińskie o resztach
Jeśli $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.
powrót do spisu
