Reszta z dzielenia - duże liczby - kongruencja

lucky44 · Post autor: **lucky44** » 13 kwie 2014, o 10:28

Witam, nie umiem zrobić takiego przykładu. Męczę się od wczoraj. Proszę o pomoc.
Mam obliczyć resztę z dzielenia liczby a przez liczbę b.

\(\displaystyle{ a=5555^{7777} , b=191}\)

bakala12 · Post autor: **bakala12** » 13 kwie 2014, o 11:34

Wykorzystaj małe twierdzenie Fermata, bo \(\displaystyle{ 191}\) jest liczbą pierwszą.

lucky44 · Post autor: **lucky44** » 13 kwie 2014, o 12:25

Ok, dziękuję, ale wobec tego co w przypadku gdy liczba b nie będzie liczbą pierwszą np.
\(\displaystyle{ a= 1946^{1972} , b=26}\) ?

bakala12 · Post autor: **bakala12** » 13 kwie 2014, o 14:29

Niestety w tym przypadku \(\displaystyle{ NWD\left( 1946,26\right)=2}\) więc można oddzielnie wyznaczyć oddzielnie \(\displaystyle{ a \pmod{13}}\) oraz \(\displaystyle{ a \pmod{2}}\) a następnie zastosować chińskie twierdzenie o resztach.

lucky44 · Post autor: **lucky44** » 13 kwie 2014, o 15:04

Dziękuję za odzew i pomoc. Generalnie w tym pierwszym przykładzie utknąłem.

Robię tak:

\(\displaystyle{ 5555 ^{190} \equiv 1 \pmod{191}}\)

Rozpisuje \(\displaystyle{ 5555 ^{7777}=5555 ^{190 \cdot 40 + 177} = (5555 ^{190})^{40} \cdot 5555 ^{177}=5555 ^{177} ...}\)

Jestem na dobrym tropie czy całkowicie źle? Co zrobić z tym dalej. Proszę o rozpisanie, chciałbym to zrozumieć.

bakala12 · Post autor: **bakala12** » 13 kwie 2014, o 15:36

\(\displaystyle{ 5555 \equiv 16 \pmod{191}}\)
Mamy więc:
\(\displaystyle{ 5555^{177} \equiv 16^{177} \equiv 256^{88} \cdot 16 \equiv 65^{88} \cdot 16 \equiv 23^{44} \cdot 16 \equiv 26^{11} \cdot 16 \equiv \left( 26^{3}\right)^{3} \cdot 26^{2} \cdot 16 \equiv 4^{3} \cdot 26^{2} \cdot 16 \equiv 4^{3} \cdot 120 \equiv 40 \pmod{191}}\)
Mam nadzieje, że się nie pomyliłem.