Dzielenie kongruencji stronami

[niunix98]

Cześć,

Jestem nowy w tematyce kongruencji i mam pytanie, jak rozwiązać następujące zadanie:

\(\displaystyle{ 30 \cdot 17 \equiv 81 \cdot 197 \pmod{6}}\)?

Na kole słyszałem, że kongruencje można dzielić stronami, ale wtedy i tylko wtedy, gdy któreś dwie liczby są względnie pierwsze. Nie mogę sobie tylko teraz przypomnieć które, a internet nie pomaga

Mój sposób rozumowania był taki:

\(\displaystyle{ 30 \cdot 27 \equiv 81 \cdot 197 \pmod{6} ||81 \Leftrightarrow 10 \equiv 197 \pmod{6}}\), co jest oczywiście nieprawdą. W głowie cały czas miałem, że nie mogę tego zrobić, ale uznałem to za dość intuicyjne w tym przypadku.

[Jan Kraszewski]

Zauważ, że \(\displaystyle{ ac\equiv bc\pmod{k}}\) dokładnie wtedy, gdy \(\displaystyle{ k\mid(a-b)\cdot c}\). Jeśli zatem \(\displaystyle{ k}\) i \(\displaystyle{ c}\) są względnie pierwsze, to \(\displaystyle{ k\mid(a-b)}\), czyli \(\displaystyle{ a\equiv b\pmod{k}}\).

Kongruencję \(\displaystyle{ ac\equiv bc\pmod{k}}\) możesz zatem podzielić obustronnie przez \(\displaystyle{ c}\), gdy \(\displaystyle{ k}\) i \(\displaystyle{ c}\) są względnie pierwsze.

JK

[niunix98]

Czyli moje rozumowanie jest błędne, bo \(\displaystyle{ NWD(6,81)\ne 1}\)?

[Jan Kraszewski]

Tak.

JK

[niunix98]

Powrót do pytania - czy dzielenie kongruencji stronami jest przejściem równoważnym? Wydaje się to oczywiste, ale wolę zapytać...

[Jan Kraszewski]

Tak, ale tylko we wspomnianej powyżej sytuacji.

JK

[PoweredDragon]

Przy dzieleniu przez WD modułu, można też podzielić moduł, ale przejście równoważne to to nie jest - raczej implikacja