How to calculate $32^{61} \bmod 85$ by hand ?
85 = 5 * 17
can anyone show me the steps in detail ?
Asked
Active
Viewed 56 times
1
-
What have you tried? Where are you stuck? – Ѕᴀᴀᴅ Oct 06 '18 at 08:30
3 Answers
2
Use Euler's theorem:
$\varphi(85)=\varphi(5)\,\varphi(17)=64$, so as $32$ and $85$ are coprime, $$32^{61}\equiv32^{-3}=(32^{-1})^3.$$ Now the extended Euclidean algorithm yields the Bézout's identity: $$8\cdot 32 -3\cdot 85=1,$$ so $32^{-1}\equiv8\mod85$, so $$32^{61}\equiv 2^9=512\equiv 2 \mod 85.$$
Bernard
- 175,478
0
Note that: $$32^{61}=(2^5)^{61}=2^{305};\\ 2^8\equiv 1 \pmod{85} \Rightarrow (2^8)^{38}\cdot 2\equiv 1^{38}\cdot 2\equiv 2 \pmod{85}.$$
farruhota
- 31,482
-
@BillDubuque, it is kind of you, indeed. Yes, I noticed all answers had been downvoted as soon as I saw it. Usually, the users with high (or very high) reputation are more open, generous and helpful in terms of proofreading (remarking, assisting, etc). I thought the downvotes were for the OP's not attempting much and answerers' not encouraging him/her much. Thank you for reminding about the tools. Best regards. – farruhota Oct 08 '18 at 14:21
0
$\!\bmod 5\ \&\ 17\!:\ \color{#c00}{2^{\large 4}}\equiv \pm1\Rightarrow 2^{\large 1+8n}\!\equiv 2(\color{#c00}{2^{\large 4}})^{\large 2n}\!\equiv 2,\,$ so $\,5,17\mid 2^{\large 1+8n}\!-\!2\,$ so lcm $=85$ divides it too
Bill Dubuque
- 272,048
-
Indeed, $2^4\equiv 1 \pmod{5}$ and $2^4\equiv -1 \pmod{17}$ is good to notice. The OP started/enquired your method: $85=5\cdot 17$. So, +1 (upvoted yesterday). – farruhota Oct 08 '18 at 07:27