Kongruencja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Kongruencja
Witam, mam do rozwiązania \(8^{53}+9^{101}\equiv x\pmod{73}\).
Ostatnio zmieniony 22 sty 2020, 18:35 przez grdv10, łącznie zmieniany 1 raz.
-
grdv10
- Fachowiec
- Posty: 1039
- Rejestracja: 04 sty 2020, 12:47
- Podziękowania: 9 razy
- Otrzymane podziękowania: 388 razy
- Płeć:
Re: Kongruencja
Ściślej mówiąc, masz do wyznaczenia resztę z dzielenia liczby \(8^{53}+9^{101}\) z dzielenia przez \(73.\) Jak pokazuję poniżej, wynosi ona \(56.\)
Przez \(a\equiv b\) dla uproszczenia zapisu będę rozumiał przystawanie modulo \(73.\)
Łatwo widać, że \(2^9=512=7\cdot 73+1\equiv 1\), więc \[8^{53}=2^{159}=2^{9\cdot 17+6}=\bigl(2^9)^{17}\cdot 2^6\equiv 1^{17}\cdot 64=64.\]Z kolei \(3^4\equiv 8\), więc \(3^6\equiv 8\cdot 9=72\equiv -1.\)Dlatego\[9^{101}=3^{202}=3^{6\cdot 33+4}=\bigl(3^6)^{33}\cdot 81\equiv (-1)^33\cdot 8=-8\equiv 65.\]Dlatego \(8^{53}+9^{101}\equiv 64+65=129=73+56\equiv 56.\)
Tak więc \(x=56.\)
Przez \(a\equiv b\) dla uproszczenia zapisu będę rozumiał przystawanie modulo \(73.\)
Łatwo widać, że \(2^9=512=7\cdot 73+1\equiv 1\), więc \[8^{53}=2^{159}=2^{9\cdot 17+6}=\bigl(2^9)^{17}\cdot 2^6\equiv 1^{17}\cdot 64=64.\]Z kolei \(3^4\equiv 8\), więc \(3^6\equiv 8\cdot 9=72\equiv -1.\)Dlatego\[9^{101}=3^{202}=3^{6\cdot 33+4}=\bigl(3^6)^{33}\cdot 81\equiv (-1)^33\cdot 8=-8\equiv 65.\]Dlatego \(8^{53}+9^{101}\equiv 64+65=129=73+56\equiv 56.\)
Tak więc \(x=56.\)