# Computing large modular numbers

How do you compute large modular arithmetic such as $8^{128}$ $mod$ $100$ or $10^{111}$ $mod$ $137$ or $3^{100}$ mod $17$? I know that one way is repeated squaring. For the first one, my book says 16, for the second 96, and third 13. It gives the answers but does not show how to do any of the three, the procedure, or even a example. If anyone could show me how the answers are derived, that would be wonderful!!

• With Fermat's little theorem you can considerably reduce the size of exponents without doing massive computations. – TMM Apr 25 '13 at 19:27

Using Fermat's little theorem, we know $a^b \equiv a^{(b \mod \phi(c))} \mod c$. So we can reduce exponents by subtracting any multiple of $\phi(c)$ until we get a number between $0$ and $\phi(c) - 1$.

1. First, $\phi(100) = \phi(2^25^2) = \frac{1}{2} \cdot \frac{4}{5} \cdot 100 = 40$ so $8^{128} \equiv 8^{128 - 3 \cdot 40} \equiv 8^8 \mod 100$. Now we do need a few computations, for instance using that $2^{10} = 1024$: $$8^8 \equiv 2^{24} \equiv 2^{10} \cdot 2^{10} \cdot 2^4 \equiv (1024) \cdot (1024) \cdot 16 \equiv 24 \cdot 24 \cdot 16 \equiv 16 \cdot 16 \equiv 16 \mod 100.$$

2. Since $111 < \phi(137)$, the trick of subtracting multiples of $\phi(137)$ does not help here. But doing a few computations by hand gives us $10^3 = 1000 \equiv 41 \mod 137$ and $10^4 \equiv 410 \equiv -1 \mod 137$ which is a really nice, small number. So: $$10^{111} = 10^{108} \cdot 10^3 \equiv (10^4)^{27} \cdot 41 \equiv (-1)^{27} \cdot 41 \equiv -41 \equiv 96 \mod 137.$$

3. Finally, $\phi(17) = 16$ and $100 = 6 \cdot 16 + 4$, so $$3^{100} \equiv (3^{16})^6 \cdot 3^4 \equiv 3^4 \equiv 81 \equiv 13 \mod 17.$$

Hint $\rm\ \ mod\ 25\!:\ 2^{10}\! \equiv 1024\equiv -1.\ \ \ mod\ 137\!:\ 10^4\! \equiv (-37)^2\!\equiv -1.\ \ \ mod\ 17\!:\ 3^{16}\!\equiv 1$

Main way to calculate large powers: repeated squares, as you said.

Examples of using:

$8^{128} \mod 100$.
Let's construct table of powers $1,2,4,8,16,32,64,128$:

$\begin{array}{c|c|lr} & 8^1 & \equiv 8 & \mod 100 \\ & 8^2 & \equiv (8)^2 = 64 & \mod 100 \\ & 8^4 & \equiv (8^2)^2 = 64^2 = 4096 \equiv 96 & \mod 100 \\ & 8^8 & \equiv (8^4)^2 \equiv 96^2 \equiv (-4)^2 = 16 & \mod 100 \\ & 8^{16} & \equiv (8^8)^2 \equiv 16^2 = 256 \equiv 56 & \mod 100 \\ & 8^{32} & \equiv (8^{16})^2 \equiv 56^2 = 3136 \equiv 36 & \mod 100 \\ & 8^{64} & \equiv (8^{32})^2 \equiv 36^2 = 1296 \equiv 96 & \mod 100 \\ \checkmark & 8^{128} & \equiv (8^{64})^2 \equiv 96^2 \equiv (\mbox{look at }8^8) \equiv 16 & \mod 100 \end{array}$

So, $8^{128}\equiv16 \mod 100$.

$-$$-$$-$$-$$-$

$10^{111} \mod 137$.
$111$ is not clear power of $2$, so we will decompose it (binary base): $$111=64+32+8+4+2+1.$$ We'll construct table of powers $1,2,4,8,\ldots$, up to $64$; and will check our powers $1,2,4,8,32,64$.

$\begin{array}{c|c|lr} \checkmark & 10^1 & \equiv10 & \mod 137 \\ \checkmark & 10^2 & \equiv(10)^2 = 100 & \mod 137 \\ \checkmark & 10^4 & \equiv (10^2)^2 = 100^2 \equiv (-37)^2=1369\equiv 136 \equiv -1 & \mod 137 \\ \checkmark & 10^8 & \equiv (10^4)^2 \equiv (-1)^2 = 1 & \mod 137 \\ & 10^{16} & \equiv (10^8)^2 \equiv 1^2 = 1 & \mod 137 \\ \checkmark & 10^{32} & \equiv (10^{16})^2 \equiv 1^2 = 1 & \mod 137 \\ \checkmark & 10^{64} & \equiv (10^{32})^2 \equiv 1^2 = 1 & \mod 137 \\ \end{array}$

So, $10^{111} \equiv 10^{1+2+4+8+32+64} \equiv 10^1\cdot 10^2\cdot 10^4\cdot 10^8\cdot 10^{32}\cdot 10^{64} \equiv 10 \cdot 100 \cdot (-1) \cdot 1 \cdot 1 \cdot 1 \equiv 41 \cdot (-1) \equiv -41 \equiv 96 \mod 137.$

(Sometimes we can use negative numbers to simplify calculations, but correct answer must be positive finally).

$-$$-$$-$$-$$-$

$3^{100} \mod 17$.
Try to calculate it manually using this method.