Duże modulo

[Konikov]

Oblicz \(\displaystyle{ (102^{70} + 1)^{35}\ mod\ 111}\).

[bm371613]

Może to sposób prymitywny, ale czemu nie policzysz tego na siłę?

To wcale nie jest dużo pracy. Obliczasz sobie potęgi liczby 102 mod 111 (np. w kolejności pierwsza, druga, czwarta, piąta, dwudziesta, dwudziestapiąta, pięćdziesiąta, siedemdziesiąta) i potem robisz to samo z potęgami liczby \(\displaystyle{ (102^{70} + 1)}\).

Skoro przez 10 dni nie wpadłeś na lepsze rozwiązanie to sobie policz te ~10 operacji

[Fingon]

Rozwiązanie zadania przy pomocy komputera tudzież ręcznie wykorzystując algorytm szybkiego potęgowania, jest proste, ale jakieś takie mało matematyczne.

[max]

Z twierdzenia chińskiego o resztach kongruencja \(\displaystyle{ x\equiv (102^{70}+1)^{35}\pmod{111}}\) jest równoważna układowi:
\(\displaystyle{ \begin{cases}x\equiv (102^{70}+1)^{35} \pmod{3}\\ x\equiv (102^{70}+1)^{35}\pmod{37}\end{cases}}\)
bo \(\displaystyle{ 111 = 3\cdot 37,}\) a \(\displaystyle{ 3,37}\) są względnie pierwsze.
Ale \(\displaystyle{ 3\mid 102}\), więc pierwsza kongruencja przerabia się na:
\(\displaystyle{ x\equiv 1\pmod{3}}\).

Co do drugiej kongruencji:
Mały Fermat daje:
\(\displaystyle{ 102^{70}\equiv (-9)^{70} \equiv (-9)^{-2}\pmod{37}}\)
Zauważamy, że \(\displaystyle{ -9\cdot 4 = -36\equiv 1\pmod{37}}\), więc \(\displaystyle{ (-9)^{-1} \equiv 4\pmod{37}}\) (możemy też to policzyć rozszerzonym algorytmem Euklidesa).
Nasza kongruencja jest więc postaci \(\displaystyle{ x\equiv 17^{35}\pmod{37}}\).
Znów mały Fermat mówi, że jest ona równoważna następującej:
\(\displaystyle{ x\equiv 17^{-1}\pmod{37}}\).

Pozostaje wyznaczyć (np rozszerzonym algorytmem Euklidesa) odwrotność \(\displaystyle{ 17}\) modulo \(\displaystyle{ 37}\) i rozwiązać układ kongruencji:
\(\displaystyle{ \begin{cases}x\equiv 1\pmod{3}\\ x\equiv 17^{-1}\pmod{37}\end{cases}}\)
co pozostawiam autorowi tematu.

[Konikov]

Znam MTF, ale nie wiem dlaczego ono daje:

Mały Fermat daje:
\(\displaystyle{ (-9)^{70} \equiv (-9)^{-2}\pmod{37}}\)

Nasza kongruencja jest więc postaci \(\displaystyle{ x\equiv 17^{35}\pmod{37}}\).
Znów mały Fermat mówi, że jest ona równoważna następującej:
\(\displaystyle{ x\equiv 17^{-1}\pmod{37}}\).

Generalnie nie rozumiem skąd się biorą ujemne potęgi...

[max]

Slow motion:
Z małego twierdzenia Fermata:
\(\displaystyle{ (-9)^{36} \equiv 1\pmod{37}}\)
Zatem
\(\displaystyle{ (-9)^{70} \equiv (-9)^{72}\cdot (-9)^{-2}\equiv ((-9)^{36})^{2}\cdot (-9)^{-2}\equiv 1\cdot (-9)^{-2}\pmod{37}}\).

W drugim miejscu robimy analogicznie.

[Konikov]

Super ;D

Po znalezieniu ważnej własności wszystko zaczęło mieć sens ;]

\(\displaystyle{ ax + by = NWD(a,b)}\)
Jeśli liczby a i b są względnie pierwsze, to liczba x jest odwrotnością modulo b liczby a.

[M4ksiu]

To bedzie delikatny "bumping", ale podjalem sie rozwiazania tego zadania, natomiast wynik nie wychodzi taki, jaki byc powinien. Nie chce spamowac tematu, dlatego dodam tylko przekierowanie. Wydaje mi sie, ze wszystko rozwiazalem jak nalezy, dlatego nie rozumiem czy i gdzie popelnilem blad.

Temat jest tutaj: 206905.htm


Z powazaniem, M4ksiu.