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 » 26 cze 2010, o 12:12

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ł: 1380 razy

Kongruencja liniowa z dużymi liczbami

Post autor: BettyBoo » 26 cze 2010, o 12:15

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 » 26 cze 2010, o 12:26

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ł: 1380 razy

Kongruencja liniowa z dużymi liczbami

Post autor: BettyBoo » 26 cze 2010, o 12:33

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