Modular Algebra with Powers?

Question

Is it possible to calculate by modular algebra rules (with no calculators) numbers with powers $\textrm{mod}\ n$? Something like: $7^{127} \textrm{mod}\ 11$. If so, how it can be done? Any explanation will be apriciated!

Answer 1

First, $$7^{127} \equiv 8 \cdot 7 \cdot 7^{127} \equiv 8 \cdot 7^{128} \equiv 8 \cdot 7^{2^7} \pmod{11}$$

Now, step by step: $$7^2 \equiv 49 \equiv 5 \pmod{11}$$ $$5^2 \equiv 25 \equiv 3 \pmod{11}$$ $$3^2 \equiv 9 \equiv -2 \pmod{11}$$ $$(-2)^2 \equiv 4 \pmod{11}$$ $$4^2 \equiv 16 \equiv 5 \pmod{11}$$ You have still two squares to compute, but you can find them already computed above: $$5^2 \equiv 25 \equiv 3 \pmod{11}$$ $$3^2 \equiv 9 \equiv -2 \pmod{11}$$

Now, we have squared $7$ times, so we have computed: $$\left(\left(\left(\left(\left(\left(7^2\right)^2\right)^2\right)^2\right)^2\right)^2\right)^2 \equiv 7^{2^7} \equiv -2 \pmod{11}$$

And finally $$7^{127} \equiv 8 \cdot 7^{128} \equiv 8 \cdot -2 \equiv -16 \equiv 6 \pmod{11}$$

Answer 2

Using Fermat's Little Theorem, $7^{10}\equiv1\pmod {11}$ as $(7,11)=1$

So, $7^{127}=(7^{10})^{12}\cdot 7^7\equiv 7^7\pmod {11}$

$7^1\equiv7 \pmod {11}, 7^2=49\equiv5, 7^4\equiv 5^2\equiv 3$ $\implies 7^7=7^1\cdot7^2\cdot7^4\equiv 7\cdot 5\cdot 3\pmod{11}\equiv105\equiv6$

Answer 3

Little Fermat $\rm\:\Rightarrow\:mod\ 11\!:\ \color{#c00}{2^{10}}\!\equiv 1\:\Rightarrow\: 7^{127}\!\equiv (-2^2)^{127}\!\equiv 2^{254}\!\equiv - 2^4 (\color{#c00}{2^{10}})^{25}\!\equiv -16\equiv 6$

Remark $\ $ For small numbers one may often employ intuition to find optimizations like this. Otherwise one may employ brute-force algorithms such as exponentiation by repeated squaring.

Answer 4

$7^3 \equiv 2 (\mod 11)$

$2^5 \equiv (-1 \mod 11) \implies7^{15} \equiv -1 \implies7^{120} \equiv1 (\mod 11)$

$7^3 \times 7^3 \times 7 \equiv 2 \times 2 \times 7 (\mod 11) \equiv11 \cdot2+6 (\mod 11)$

$7^7 \equiv 6 (\mod 11) \implies 7^{127} \equiv 6 (\mod 11)$