Kongruencja, małe problemy z modulo

[kkk123]

Witam,

Egzamin zbliża się nieubłaganie, a ja proszę Was o pomoc:

\(\displaystyle{ 5x\equiv -7 \pmod{12}}\)

Z tego co dziś wyczytałem (czytałem naprawdę dużo to jest kilka metod na obliczenie tego, ale ja użyłem takiej):

\(\displaystyle{ NWD(5,12)=1}\)

\(\displaystyle{ 5x \equiv -7 \pmod{12}\\
a \cdot 5 \equiv -7 \pmod{12}\\
5 \cdot 5x \equiv -7 \pmod{12}\\
x \equiv -35 \pmod{12} \\
x = 1 \pmod{12}}\)

w miejscu gdzie wychodzi \(\displaystyle{ a=5}\), ale nie wiem dlaczego :/
tylko dlaczego ujemne modulo wychodzi jakoś dziwnie?


i jeszcze \(\displaystyle{ 5x \equiv 3 \pmod{9}}\)
robię \(\displaystyle{ NWD(5,9)}\) wychodzi \(\displaystyle{ 1}\) i co dalej?

[kamil13151]

\(\displaystyle{ 5x \equiv -7 \pmod{12} \\ 5x \equiv 5 \pmod{12} \\ x \equiv 1 \pmod{12} \\ x=12k+1 \ \ k \in \mathbb{Z} \\ \\ 5x \equiv 3 \pmod{9} \\ 4x \equiv 6 \pmod{9} \\ 2x \equiv 3 \pmod{9} \\ 2x \equiv -6 \pmod{9} \\ x \equiv -3 \equiv 6 \pmod{9} \\ x=9k+6 \ \ k \in \mathbb{Z}}\)

[kkk123]

Dzięki wielkie, ale mam jedno pytanie;
a mianowicie przejście z

\(\displaystyle{ 5x \equiv 3\pmod{9}}\)

do

\(\displaystyle{ 4x \equiv 6\pmod{9}}\)

dlaczego tak to robisz?

-- 16 wrz 2012, o 19:26 --

ja zrobiłem inną metodą ten drugi przykład możesz rzucić okiem?

\(\displaystyle{ 5x \equiv 3\pmod{9} \\ 5x \equiv 30\pmod{9} \\ x\equiv 6\pmod{9}}\)

tu drugi przykład podobną metodą:

\(\displaystyle{ 43 \equiv 4\pmod{17} \\ (43\pmod{17}=9) \\ 9x \equiv = 4\pmod{17} \\ 9x \equiv 72\pmod{17} \\ x \equiv 8\pmod{17}}\)

[kamil13151]

dlaczego tak to robisz?

Szerzej wygląda to tak: \(\displaystyle{ 5x \equiv -4x \pmod{9} \\ 3 \equiv -6 \pmod{9}}\), stąd: \(\displaystyle{ -4x \equiv -6 \pmod{9}}\) i mnożymy przez \(\displaystyle{ (-1)}\).

Pierwsze jak najbardziej dobrze, zdecydowanie ładniej niż ja (choć ja to raczej tzw. pałowałem). W drugim popraw błędy w zapisie, bo nie idzie się połapać.

[kkk123]

\(\displaystyle{ 43x \equiv 4\pmod{17}}\)

zniwelowanie duzej liczby 43 poprzez modulo
\(\displaystyle{ (43\pmod{17}=9) \\ \\ 9x \equiv = 4\pmod{17} \\ 9x \equiv 72\pmod{17} \\ x \equiv 8\pmod{17}}\)

[kamil13151]

Dobrze.

[kkk123]

A jak sobie poradzić z takim działaniem?

\(\displaystyle{ 5x+3 \equiv 2\pmod{7}}\)
?

[TMac]

Przenosisz 3 na drugą stronę...
\(\displaystyle{ 5x+3 \equiv 2\pmod{7}\\
5x \equiv -3 + 2\pmod{7}\\
5x \equiv -1\pmod{7}}\)
...i pozostała część jak poprzednio.

[kkk123]

\(\displaystyle{ 5x \equiv -1\pmod{7} \\ 5x \equiv -15\pmod{7} \\ x \equiv -3\pmod{7}}\)

dobrze?

[TMac]

Operacje modulo są o tyle fajne, że sam możesz sprawdzić w taki sposób:
Na początek może zauważ, że \(\displaystyle{ x \equiv -3\pmod{7} \Leftrightarrow x \equiv 4\pmod{7}}\) (wiesz dlaczego?). Jakie liczby to spełniają? No \(\displaystyle{ 4, 11, 18...}\). To wstawmy sobie 4 do pierwszego równania i sprawdźmy czy działa.
\(\displaystyle{ 5x \equiv -1\pmod{7} \Leftrightarrow 5 \cdot 4 \equiv -1\pmod{7} \Leftrightarrow 20 \equiv -1\pmod{7}\\ \Leftrightarrow 6 \equiv -1\pmod{7} \Leftrightarrow 6 \equiv 6\pmod{7}}\).
Czyli działa.
Jeszcze mnie ciekawi o co chodziło z tym "a" w 1. poście?
Tak poza tym jak zrobiłeś takie podstawowe praktyczne zadanie to moja rada: powtórz teorię od początku, bo teraz będziesz to bardziej czuł i znajdował sobie analogię ("o, to faktycznie tak robiłem i wyszło"), przez co zrozumiesz więcej np. stąd:
... oria_liczb
... a_liczb_II
Z 1. linku to tak na pierwszy raz do algorytmu Euklidesa włącznie i z 2. do rozwiązywania równań modularnych przede wszystkim, a jak już to będziesz potrafił to ile dasz radę z reszty . (+ wiadomo, przeglądanie zadań z działu "Teoria Liczb" w "Algebrze").

[kkk123]

przejście

\(\displaystyle{ 20 \equiv -1\pmod{7}}\)

na

\(\displaystyle{ 6 \equiv -1\pmod{7} \\ 6 \equiv 6\pmod{7}}\)

jest dlatego, że \(\displaystyle{ 20}\) podzieliłeś przez modulo \(\displaystyle{ 7}\), prawda?

[TMac]

Tak można powiedzieć, innymi słowy reszta z dzielenia \(\displaystyle{ 6}\) przez \(\displaystyle{ 7}\) jest taka sama jak reszta z dzielenia \(\displaystyle{ 20}\) przez \(\displaystyle{ 7}\) i wynosi \(\displaystyle{ 6}\) (wynika to z tego, że \(\displaystyle{ 20 = 14 + 6}\) no a reszta z dzielenia \(\displaystyle{ 14}\) przez \(\displaystyle{ 7}\) to \(\displaystyle{ 0}\), więc zostaje \(\displaystyle{ 6}\) - a to z kolei, że można tak rozbić \(\displaystyle{ 20}\) wynika już z jednego z podstawowych praw operacji modulo).