Strona 1 z 1
Kongruencja liniowa z dużymi liczbami
: 26 cze 2010, o 12:12
autor: gilberto
Czy ktoś mógłby zaproponować w jaki sposób rozwiązać
\(\displaystyle{ 154x \equiv 1(mod 801)}\)
Kongruencja liniowa z dużymi liczbami
: 26 cze 2010, o 12:15
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.
Kongruencja liniowa z dużymi liczbami
: 26 cze 2010, o 12:26
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?
Kongruencja liniowa z dużymi liczbami
: 26 cze 2010, o 12:33
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.