Kongruencja - rozwiązywanie równania modularnego

[adi333344]

Witam!
Mam takie o to zadanie: \(\displaystyle{ 788x = 24 (\bmod 1647)}\). Nie jestem wstanie go rozwiązać, próbowałem szukać na internecie, jednak tam rozwiązania były do prostych przykładów które łatwo się redukowało do prostszej postaci lub były z 1. Próbowałem użyć algorytmu EXTENDED_EUCLID.
Czy ktoś może mi pomóc na jakimś przykładzie, niekoniecznie tym które podałem, gdyż zależy mi na zrozumieniu. Proszę o uniwersalny sposób, bez zgadywania wyniku.

[niunix98]

Proponuję zacząć od podzielenia kongruencji stronami przez \(\displaystyle{ 4}\). Mniejsze liczby zawsze łatwiej ogarnąć. Następnie skorzystaj z algorytmu Euklidesa.

[adi333344]

\(\displaystyle{ ax = b (\bmod n)}\)
\(\displaystyle{ 788x = 24 (\bmod 1647)}\)
Redukujemy przez \(\displaystyle{ 4}\)

\(\displaystyle{ 197x = 6 (\bmod 1647)}\)

Używam Extended_Euclidean

Kod: Zaznacz cały

https://ibb.co/rZ3VQFw

\(\displaystyle{ d = 1}\), więc rozpatruje tylko jedno rozwiązanie

\(\displaystyle{ x_0 = x' \cdot \frac{b}{d} \bmod n }\)
\(\displaystyle{ x_0 = 719 \cdot 6 \bmod 1647 = 1020 }\)