Zadanie z wyznaczaniem układu kongruencji

[Alis9]

Wyznacz najmniejsze nieujemne rozwiązanie układu kongruencji:

\( \begin{cases}
x = 1 \pmod 5 \\
x = 3 \pmod 7 \\
x = 5 \pmod{13} \\
x = 6 \pmod{23}
\end{cases} \)

[grdv10]

Jest to zadanie na zastosowanie chińskiego twierdzenia o resztach. Na podlinkowanej stronie masz opisany algorytm. Prześledź opis i spróbuj zrobić to samodzielnie. Sam napisałem poniżej rozwiązanie, żeby przypomnieć sobie to twierdzenie.

Z pierwszego równania mamy \(x=5a+1\). Znajdziemy najmniejsze \(a\), dla którego zachodzi drugie równanie. Jest to \(a=6\). Tak więc \(5a+1=31\), skąd\[x\equiv 31\pmod{5\cdot 7}.\]Zatem\[x=35a+31.\]Teraz znajdujemy najmniejsze \(a\), żeby takie \(x\) spełniało i trzecie równanie. Widzimy, że już \(a=0\) je spełnia. Mamy więc \(35a+31=31\) i dalej\[x\equiv 31\pmod{5\cdot 7\cdot 13}.\]Tak więc\[x=455a+31\] i szukamy najmniejszego \(a\), dla którego takie \(x\) spełnia ostatnie równanie. Jest to \(a=5\). Mamy więc \(455a+31=2306\) i ostatecznie\[x=2306.\] Można sprawdzić, że \(x=2306\) spełnia ten układ kongruencji.

Ogólnie ten układ spełniają wszystkie liczby nieujemne postaci \(x=2306+5\cdot 7\cdot 13\cdot 23 a=2306+10465a.\)