1
$\begingroup$

I am working through a modulo tutorial and have become stuck here: $ 11^{32}(\operatorname{mod}13) = (11^{16})^2(\operatorname{mod}13)= 3^2(\operatorname{mod}13)= 9(\operatorname{mod}13) $

My question is, how does $(11^{16})^2(\operatorname{mod}13)$ get reduced to $3^2(\operatorname{mod}13)$?

3 Answers 3

0

Looks like everyone else is stumped by that step as well. Maybe wherever you got that problem had $11^{16}$ previously calculated. I would do the original problem similar to Bill.

$11^{32}=(11^{12})^2\times11^8\equiv11^8\equiv[(-2)^4]^2\equiv3^2\equiv9\pmod{13}$

3

Fermat's Little Theorem tells us that $11^{12} \equiv 1 \pmod {13}$, so $11^{16} \equiv 11^4 \equiv (-2)^4 \equiv 16 \equiv 3 \pmod {13}$

3

Hint $\ $ By $\mu\!$ Fermat, $\rm\: mod\ 13\!:\ 11^{12}\equiv 1\:$ so $\rm\:11^{16}\equiv 11^{12}\cdot 11^4\equiv 1\cdot(-2)^4\equiv 3$

Generally, mod prime $\rm P\!:\ A\not\equiv0 \ \Rightarrow\ A^{P-1}\equiv 1\ \Rightarrow\ A^N \equiv\: A^{(N\ mod\ P-1)}$

Note also the use of least (balanced) residues $\rm\:11\equiv -2\pmod {13}\:$ to simplify calculations.