Wyznaczanie reszty z dzielenia

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Wyznaczanie reszty z dzielenia

Post autor: edaro »

Mam znaleźć resztę z dzielenia liczby \(\displaystyle{ 2^{11}}\) przez 47.

Rozumiem, że na początku korzystamy z małego twierdzenia Fermata, tzn. mamy, że \(\displaystyle{ 2^{46} \equiv 1 \ (mod \ 47)}\). Co dalej?
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Wyznaczanie reszty z dzielenia

Post autor: »

Można tak:
\(\displaystyle{ 2^{5} \equiv -15 \pmod{47}\\
2^{10}\equiv (-15)^2=225 \equiv -10 \pmod{47}\\
2^{11}\equiv 2\cdot (-10)=-20\equiv 27 \pmod{47}}\)


Q.
ODPOWIEDZ