Czy istnieje algorytm na obliczanie kongruencji?

[95Villain95]

Witam, chciałbym się dowiedzieć, czy istnieje uniwersalna metoda do obliczania wszystkich kongruencji postaci \(\displaystyle{ Yx \equiv A(modB)}\)
np. \(\displaystyle{ 8x\equiv5(mod11)}\).
Na forum znalazłem tylko coś takiego:

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)\}}\)

Tylko to nie jest chyba najlepszy sposób, żeby mając układ kongruencji przykładowo taki \(\displaystyle{ \begin{cases}4x = 15 (\mod 23) \\ 8x = 9 (\mod 25)\\ 12x = 3 (\mod 29) \end{cases}}\)
przekształcać wszystkie 3 kongruencję do postaci \(\displaystyle{ x \equiv C(modD)}\) i dopiero później rozwiązywać twierdzeniem chińskim?

[Premislav]

Tak, znajdujesz takie \(\displaystyle{ s}\), że \(\displaystyle{ s \cdot Y\equiv 1\pmod{B}}\) z użyciem rozszerzonego algorytmu Euklidesa, a następnie mnożysz kongruencję stronami przez takie \(\displaystyle{ s}\) i masz:
\(\displaystyle{ x\equiv s\cdot A \pmod{B}}\)
Tylko to nie działa oczywiście w przypadku, w którym en wu de \(\displaystyle{ B}\) i \(\displaystyle{ Y}\) jest większe od \(\displaystyle{ 1}\).-- 2 cze 2016, o 13:56 --Czyli jednak nie jest to w 100% uniwersalne, ale jeśli masz
\(\displaystyle{ Yx\equiv A \pmod{B}}\) i \(\displaystyle{ (B,Y)>1}\), to jeżeli \(\displaystyle{ (B,Y)}\) nie dzieli \(\displaystyle{ A}\), to masz oczywistą sprzeczność, a w przeciwnym przypadku dzielisz stronami przez to NWD.

[95Villain95]

Przepraszam, wysłałem edytowany post dopiero po Twojej odpowiedzi. Czy jest ona nadal aktualna?

[Premislav]

No wybacz, ale zapytałeś pierwotnie o kongruencję, a nie o układ kongruencji. Formułowanie pytań tak, by userzy nie musieli wyciągać kryształowej kuli jest przydatne.

-- 2 cze 2016, o 14:04 --

Ja właśnie zawsze tak rozwiązywałem układy kongruencji, że najpierw sprowadzałem do postaci
\(\displaystyle{ \begin{cases} x \equiv a_{1}\pmod{b_{1}} \\ x \equiv a_{2}\pmod{b_{2}}\\... \end{cases}}\)
gdzie \(\displaystyle{ b_{i}}\) są względnie pierwsze
i używałem chińskiego twierdzenia o resztach, ale nie mogę powiedzieć na 100%, że jest to najbardziej optymalna metoda.

[95Villain95]

No wybacz, ale zapytałeś pierwotnie o kongruencję, a nie o układ kongruencji. Formułowanie pytań tak, by userzy nie musieli wyciągać kryształowej kuli jest przydatne.

Wiem, dlatego napisałem:

Przepraszam, wysłałem edytowany post dopiero po Twojej odpowiedzi.

Ja właśnie zawsze tak rozwiązywałem układy kongruencji, że najpierw sprowadzałem do postaci
\(\displaystyle{ \begin{cases} x \equiv a_{1}\pmod{b_{1}} \\ x \equiv a_{2}\pmod{b_{2}}\\... \end{cases}}\)
gdzie \(\displaystyle{ b_{i}}\) są względnie pierwsze

Masz na myśli tę metodę?

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)\}}\)

[Premislav]

Tak, za pomocą tej właśnie metody sprowadzałem każde równanie do postaci takiej, jaką napisałem, a następnie
korzystałem z chińskiego twierdzenia o resztach (teraz już nawet nie pamiętam, jak się to dokładnie robi).