układ kongruencji

[Kasik22]

Mam takie pytanie, czy ten układ równań ma rozwiązania?


\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 1111)\\ x \equiv 22 (mod 22222) \\x \equiv 555 (mod 555555)
\end{cases}}\)

Jeśli ma, bądź też nie ma rozwiązań proszę o komentarz do tego, z góry dziękuje

[Rogal]

Znasz twierdzenie chińskie o resztach?

[Kasik22]

tak i wiem, że powyższy układ nie ma rozwiązań, ponieważ liczby przy modulach nie są parami względnie pierwsze
pozdrawiam

[Rogal]

A to twierdzenie rozstrzyga co się dzieje, gdy moduły nie są parami względnie pierwsze?

[Kasik22]

Niestety nie:/, wówczas należy spróbować rozwiązać ten układ kongruencji i czasem znajdziemy rozwiązanie, a czasem nie. Trzeba być ostrożnym

[JakimPL]

Mamy:

\(\displaystyle{ \begin{cases} x \equiv 1 \pmod {1111}\\ x \equiv 22 \pmod {22222} \\x \equiv 555 \pmod {555555} \end{cases}}\)

Z pierwszego mamy oczywiście \(\displaystyle{ x=1111n_1+1}\), wstawiamy to do drugiego:

\(\displaystyle{ 1111n_1+1\equiv 22\pmod {22222}}\)

Po rozwiązaniu mamy \(\displaystyle{ n_1=22222 n_2 + 10901}\). Stąd \(\displaystyle{ x=1111(22222 n_2 + 10901)+1}\). Wstawiając do ostatniego:

\(\displaystyle{ 1111(22222 n_2 + 10901)+1\equiv 555 \pmod{555555}\\
24688642 n+12110457\equiv 0 \pmod{555555}}\)

No i tu już rozwiązań nie ma (widać, dlaczego?).