ma nadzieje, że nie utracilem sprawnosci rachunkowej
Zadanie:
wyznacz resztę z dzielenia \(\displaystyle{ 13^{141}}\) przez \(\displaystyle{ 32}\)
otóż z tw Eulera \(\displaystyle{ 13^{\phi(32)}\equiv 1 \mod 32}\)
\(\displaystyle{ \phi(2^5)=2^5-2^4=32-16=16}\)
\(\displaystyle{ 13^{16}\equiv 1 \mod 32}\)
Prowadzę rachunki
\(\displaystyle{ 13^{141}=\left1(3^{16}\right)^8\cdot 13^{13}\equiv 13^{13}}\)
\(\displaystyle{ x\equiv 13^{13}}\)
stąd
\(\displaystyle{ 13^3 x \equiv 13^{16}\equiv 1 \mod 32}\)
\(\displaystyle{ 169\cdot 13 x \equiv 1 \mod 32}\)
\(\displaystyle{ 9\cdot 13 x \equiv 1 \mod 32}\)
\(\displaystyle{ 117 x \equiv 1 \mod 32}\)
\(\displaystyle{ 21 x \equiv 1 \mod 32}\)
\(\displaystyle{ x=29}\)
odp: \(\displaystyle{ 13^{141}\equiv 29 \mod 32}\)
tw eulera
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
tw eulera
Dobrze, ale da się szybciej. Z funkcji Carmichaela otrzymujemy \(\displaystyle{ 13^{\lambda(32)} \equiv 1\pmod{32} \iff 13^{8} \equiv 1\pmod{32}/^{17} \Rightarrow \\ 13^{136} \equiv 1\pmod{32} /\cdot 13^5 \Leftrightarrow 13^{141} \equiv 13^5 \equiv 13\cdot 169^2 \equiv 13\cdot 9^2 \equiv 13\cdot 17 \equiv 29\pmod{32}}\)