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?
Wyznaczanie reszty z dzielenia
-
- 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
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.
\(\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.