Czy ktoś mógłby zaproponować w jaki sposób rozwiązać
\(\displaystyle{ 154x \equiv 1(mod 801)}\)
Kongruencja liniowa z dużymi liczbami
-
- 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
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.
Pozdrawiam.
-
- Użytkownik
- Posty: 2
- Rejestracja: 26 cze 2010, o 11:53
- Płeć: Mężczyzna
- Lokalizacja: Gieradów
Kongruencja liniowa z dużymi liczbami
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?
-
- 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
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.
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.