Kongruencja, dzielenie

[laewqq]

mam taką kongruencje:
\(\displaystyle{ 6x\equiv 3 \mod{9}}\)

Czy moge podzielic przez \(\displaystyle{ 6}\) i nastepnie wyznaczyc element odwrotny do \(\displaystyle{ 6}\) i dostane wtedy to do czego przystaje \(\displaystyle{ x}\) ? czy powinienem zrobic to inaczej

[adambak]

tutaj jest trochę problem, bo \(\displaystyle{ NWD(6,9)=3}\) a więc \(\displaystyle{ 6}\) nie ma odwrotności modulo \(\displaystyle{ 9}\) więc to proste podejście z przemnożeniem stronami przez odwrotność nie zadziała, ale za to:

\(\displaystyle{ 6x\equiv{3}\mod{9} \Leftrightarrow \frac{6}{NWD(6,9)} x\equiv \frac{3}{NWD(6,9)}\mod{\frac{9}{NWD(6,9)}} \Leftrightarrow \\ 2x\equiv 1 \mod{3} \Leftrightarrow 2^{-1}\cdot 2 x \equiv 2^{-1}\cdot 1 \mod {3} \Leftrightarrow x\equiv{2} \mod 3}\)

jak łatwo sprawdzić wszystkie rozwiązania \(\displaystyle{ x=3k+2, \ k\in\mathbb{Z}}\) spełniają:
\(\displaystyle{ 6\cdot(3k+2)=18k+12\equiv 3 \mod{9}}\)


zauważ, że gdyby \(\displaystyle{ NWD(6,9)}\) nie dzieliło trójki to wtedy to równanie nie miałoby rozwiązań..