Kongruencja liniowa z dużymi liczbami

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
gilberto
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 26 cze 2010, o 11:53
Płeć: Mężczyzna
Lokalizacja: Gieradów

Kongruencja liniowa z dużymi liczbami

Post autor: gilberto »

Czy ktoś mógłby zaproponować w jaki sposób rozwiązać
\(\displaystyle{ 154x \equiv 1(mod 801)}\)
BettyBoo
Użytkownik
Użytkownik
Posty: 5356
Rejestracja: 10 kwie 2009, o 10:22
Płeć: Kobieta
Lokalizacja: Gliwice
Pomógł: 1381 razy

Kongruencja liniowa z dużymi liczbami

Post autor: BettyBoo »

A dlaczego nie wprost? Liczby nie są aż tak duże, żeby się tym przejmować. Są gotowe wzory na rozwiązania równań diofantycznych liniowych, więc z nich możesz skorzystać.

Pozdrawiam.
gilberto
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 26 cze 2010, o 11:53
Płeć: Mężczyzna
Lokalizacja: Gieradów

Kongruencja liniowa z dużymi liczbami

Post autor: gilberto »

rozwiązując równanie diofantyczne \(\displaystyle{ 154x-801y=1}\) wyszło mi x=-26 i y=5 więc wszystko się zgadza, jednak nie ma może jakiejś szybszej metody?
BettyBoo
Użytkownik
Użytkownik
Posty: 5356
Rejestracja: 10 kwie 2009, o 10:22
Płeć: Kobieta
Lokalizacja: Gliwice
Pomógł: 1381 razy

Kongruencja liniowa z dużymi liczbami

Post autor: BettyBoo »

Raczej \(\displaystyle{ x_0=-26,\ y_0=-5}\).

Można oczywiście rozłożyć moduł na iloczyn liczb względnie pierwszych i w efekcie rozłożyć kongruencję na układ kongruencji. Tyle, że potem trzeba to złożyć z powrotem i jeśli nie dostaniesz jakichś fajnych kongruencji, to w ogólności do tego składania z powrotem służy chińskie twierdzenie o resztach. A to na pewno jest dużo dłużej niż skorzystanie z równań diofantycznych

Pozdrawiam.
ODPOWIEDZ