Fermat, a liczba nie-pierwsza

[kasia00]

Witam. Mam do obliczenie \(\displaystyle{ 8 ^{33} mod 25}\). Wiem jak działa to dla modulo liczba pierwsza, jednak \(\displaystyle{ 25}\) nie jest liczbą pierwszą, jak się do tego zabrać?

[Premislav]

Małe Twierdzenie Fermata, o którym piszesz, jest szczególnym przypadkiem twierdzenia Eulera:
... a_liczb%29

Można to zadanie zrobić z użyciem tego twierdzenia.

[kasia00]

Małe Twierdzenie Fermata, o którym piszesz, jest szczególnym przypadkiem twierdzenia Eulera:
... a_liczb%29

Można to zadanie zrobić z użyciem tego twierdzenia.

Ok, dochodzę do momentu \(\displaystyle{ 8 ^{13} mod 25}\) i co dalej?

[Premislav]

No to trzeba jednak trochę policzyć, nie wiedziałem, że aż tak brzydko wychodzi.
Wiadomo, że \(\displaystyle{ 8^{13}=(2^{3})^{13}=2^{39}\equiv 2^{19}\pmod{25}}\) ponownie z twierdzenia Eulera. No a \(\displaystyle{ 2^{19}=2^{9}\cdot 2^{10}}\) i \(\displaystyle{ 2^{10}=1024\equiv -1\pmod{25}}\) oraz \(\displaystyle{ 2^{9}=512\equiv 12\pmod{25}}\), więc\(\displaystyle{ 2^{19}\equiv -1\cdot 12\pmod{25}}\), czyli \(\displaystyle{ 2^{19}\equiv 13\pmod{25}}\), zatem i \(\displaystyle{ 8^{33}\equiv 13\pmod{25}}\)

[Milczek]

Ja mam takie coś, zrobiłem w ramach ćwiczenia :

\(\displaystyle{ 8 ^{33}\equiv2^{99} \pmod {25}}\)

I mamy że \(\displaystyle{ 2^{10} \equiv 1024 \equiv -1 \pmod {25}}\) czyli mamy że
\(\displaystyle{ 2^{90}\equiv -1 \pmod {25}}\)

Natomiast \(\displaystyle{ 2^{9} \equiv 512 \equiv 12 \pmod {25}}\)

Ostatecznie \(\displaystyle{ 2^{99} \equiv -12 \equiv 13 \pmod {25}}\)

edit. zostałem wyprzedzony , ale nie ma twierdzenia Eulera bądź Fermata

[Premislav]

Racja, w tym zadaniu zgrabniej jest nie powoływać się na twierdzenie Eulera, bo i tak bez tego \(\displaystyle{ 2^{10}\equiv -1\pmod{25}}\) wiele nie zdziałamy, a ta własność pozwala od razu na rozwiązanie zadania.