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.
Kongruencja - rozwiązywanie równania modularnego
-
- Użytkownik
- Posty: 15
- Rejestracja: 22 lis 2018, o 12:37
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 6 razy
Kongruencja - rozwiązywanie równania modularnego
Ostatnio zmieniony 25 cze 2020, o 18:41 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- niunix98
- Użytkownik
- Posty: 96
- Rejestracja: 19 lis 2017, o 20:25
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
- Pomógł: 17 razy
Re: Kongruencja - rozwiązywanie równania modularnego
Proponuję zacząć od podzielenia kongruencji stronami przez \(\displaystyle{ 4}\). Mniejsze liczby zawsze łatwiej ogarnąć. Następnie skorzystaj z algorytmu Euklidesa.
-
- Użytkownik
- Posty: 15
- Rejestracja: 22 lis 2018, o 12:37
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 6 razy
Re: Kongruencja - rozwiązywanie równania modularnego
\(\displaystyle{ ax = b (\bmod n)}\)
\(\displaystyle{ 788x = 24 (\bmod 1647)}\)
Redukujemy przez \(\displaystyle{ 4}\)
\(\displaystyle{ 197x = 6 (\bmod 1647)}\)
Używam Extended_Euclidean
\(\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 }\)
\(\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 }\)
Ostatnio zmieniony 25 cze 2020, o 21:36 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.