forum.zadania.info

Witam, mam do rozwiązania \(8^{53}+9^{101}\equiv x\pmod{73}\).

Ś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.\)