Rozwiąż kongurencje

[Kanodelo]

\(\displaystyle{ 14x\equiv 22(mod36)}\)
Nie wiem, na prawdę nie wiem, poddaje się ;(

[norwimaj]

Można podzielić przez \(\displaystyle{ 2}\):

\(\displaystyle{ 7x\equiv11\pmod{18}}\).

Dalej znajdź odwrotność do \(\displaystyle{ 7}\) modulo \(\displaystyle{ 18}\) i pomnóż przez nią obie strony.

[Kanodelo]

Jak tą odwrotność znaleść?

Można tak:
\(\displaystyle{ 7x-11=18k \\
7x=18k-11}\)
no to np x=1 spełnia równanie, więc 1 będzie odwrotnościa?

[Vax]

Nie, jeżeli a jest odwrotnością \(\displaystyle{ 7}\) modulo \(\displaystyle{ 18}\) to musi zachodzić:

\(\displaystyle{ 7a \equiv 1 (mod \ 18)}\)

Skąd otrzymujemy \(\displaystyle{ a=13}\) (w innym temacie podałem 2 metody, jak do tego szybko dojść) czyli naszą odwrotnością jest 13, mnożymy teraz przez to naszą kongruencje:

\(\displaystyle{ 7x \equiv 11 (mod \ 18)}\)

\(\displaystyle{ 91x \equiv 143 (mod \ 18)}\)

\(\displaystyle{ x \equiv 17 (mod \ 18)}\)

Pozdrawiam.

[95Villain95]

Czy poprawną odpowiedzią nie będzie przypadkiem \(\displaystyle{ x \equiv 17 (mod \ 36)}\)?

[Premislav]

Nie, nie będzie. Tzn. każda liczba tej postaci jest rozwiązaniem kongruencji z tego wątku, ale ta formuła nie wyczerpuje rozwiązań. Np. \(\displaystyle{ 35}\) nie daje reszty \(\displaystyle{ 17}\) z dzielenia przez \(\displaystyle{ 36}\), a niewątpliwie jest rozwiązaniem.
Może nie zrozumiałeś, co stało się w drugim poście:
zapis \(\displaystyle{ 14x \equiv 22\pmod{36}}\) oznacza, że dla każdego \(\displaystyle{ x}\) spełniającego tę zależność istnieje taka liczba całkowita \(\displaystyle{ t(x)}\), że \(\displaystyle{ 14x=36\cdot t(x)+22}\). No i teraz tę równość dzielimy stronami przez dwa, tak, jak pisał norwimaj (zwykle gdy ma się już trochę wprawy, to tak się tego nie rozpisuje, ale wprawa przychodzi wraz z rozwiązywaniem).

A dzielimy przez dwa, bo \(\displaystyle{ gcd(14,36)\neq 1}\) i nie moglibyśmy zastosować tej metody, o którą pytałeś w innym wątku.

[95Villain95]

Czyli do sprowadzania kongruencji do postaci \(\displaystyle{ x \equiv a_{1}\pmod{b_{1}}}\) nie mogę używać metody, o którą pytałem w innym poście jedynie, gdy \(\displaystyle{ gcd\neq 1}\)? Rozumiem, że w przypadku, gdy mam już każde równanie w układzie kongruencji sprowadzone do takiej postaci, to twierdzenie o chińskich resztach jest uniwersalne i możliwe do zastosowania w każdym przypadku? Przepraszam za ciągnięcie tematu, ale chciałbym sobie to uporządkować w głowie.

[Premislav]

Chińskie twierdzenie o resztach ma swoje założenia, konkretnie zaś \(\displaystyle{ b_{i}}\) muszą być parami względnie pierwsze.
Przykładowo, w układzie
\(\displaystyle{ \begin{cases}3x \equiv{15}\pmod{36} \\13x\equiv 2 \pmod{17}\\ 5x\equiv 1\pmod{4}\end{cases}}\)
każdą pojedynczą kongruencję można sprowadzić do postaci \(\displaystyle{ x\equiv a_{i}\pmod{b_{i}}}\), ale co z tego, skoro \(\displaystyle{ gcd(4,12)=4>1}\).

[95Villain95]

Czyli reasumując, do sprowadzania kongruencji do postaci \(\displaystyle{ x \equiv a_{1}\pmod{b_{1}}}\) nie mogę używać metody, o którą pytałem w innym poście jedynie, gdy \(\displaystyle{ gcd\neq 1}\), natomiast użycie chińskiego twierdzenia o resztach jest możliwe jedynie, gdy \(\displaystyle{ b_{i}}\) są parami względnie pierwsze?-- 5 cze 2016, o 11:11 --Jeżeli odpowiedzi na moje pytania są pozytywne, to czy istnieje uniwersalna metoda sprowadzania kongruencji do postaci \(\displaystyle{ x \equiv a_{1}\pmod{b_{1}}}\),
gdy nie mogę użyć tej:

Jest sposób. Jeśli mamy równanie \(\displaystyle{ ax \equiv b \pmod {n}}\)
i \(\displaystyle{ d=gcd(a,n)}\) oraz \(\displaystyle{ d | b}\) to wtedy:
1. obliczamy takie \(\displaystyle{ r}\) i \(\displaystyle{ s}\) z rozszerzonego algorytmu Euklidesa,
że \(\displaystyle{ ra+sn=d}\) ( ... _algorithm)
2. obliczamy \(\displaystyle{ x=\frac{rb}{d}}\)
3. inne rozwiązania, jeśli istnieją, są kongruentne z \(\displaystyle{ x}\) modulo \(\displaystyle{ \frac{n}{d}}\) i należą
do zbioru \(\displaystyle{ \{0,...,(n-1)\}}\)

Dodatkowo, jaki sposób jest najlepszy do rozwiązywania układó∑ kongruencji, gdy \(\displaystyle{ b_{i}}\) nie są parami względnie pierwsze i niemożliwe jest użycie chińskiego twierdzenia?