Kongruencja, problem z algorytmem

[mar123zaj]

Witam, na matematyka.pl w jednym z tematów zetknąłem się z sprytnym algorytmem liczenia kongruencji, jak dotąd wszystkie przykłady ładnie mi wychodziły, natknąłem się jednak na taki, w którym w pewnym momencie nie wiem, co zrobić:

\(\displaystyle{ \begin{cases}
x\equiv 3 \pmod{7}\\
x\equiv 4 \pmod{9}\\
x\equiv 5 \pmod{11}
\end{cases}}\)

Łącze dwa równania i otrzymuję:
\(\displaystyle{ \begin{cases}
9x\equiv 27 \pmod{7 \cdot 9}\\
7x\equiv 28 \pmod{9 \cdot 7}
\end{cases}}\)

Z tych równań
\(\displaystyle{ 2x\equiv 62 \pmod{7 \cdot 9}\\}\)

Łączę to z ostatnim równaniem:

\(\displaystyle{ \begin{cases}
22x\equiv 682 \pmod{693}\\
63x\equiv 315 \pmod{693}
\end{cases}}\)

Co daje mi:

\(\displaystyle{ 41x\equiv 326 \pmod{693}}\)

I tu pojawia się mój problem, bowiem zawsze otrzymywałem na końcu x i to było poprawnym wynikiem, teraz jednak otrzymałem 41x i nie wiem co z tym zrobić. Z góry dziękuję za pomoc.

[bakala12]

Musisz wyznaczyć element odwrotny do \(\displaystyle{ 41}\) mod \(\displaystyle{ 693}\). Aby to zrobić należy skorzystać z rozszerzonego algorytmu Euklidesa. Mając element odwrotny mnożysz przez przez niego ostatnią kongruencję i dostajesz wynik.

Ale moim zdaniem, do takich przykładów zdecydowanie lepiej sprawdza się chińskie twierdzenie o resztach.