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.
Kongruencja, problem z algorytmem
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Kongruencja, problem z algorytmem
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.
Ale moim zdaniem, do takich przykładów zdecydowanie lepiej sprawdza się chińskie twierdzenie o resztach.