# Modular Numbers and Cryptography

## Modular Exponential

Since an exponent can be expressed as repeated multiplication, we can perform modular exponents

 Property of Exponentiation in Modular Arithmetic: If $$a \equiv b \pmod{N}$$, then $$a^k \equiv b^k \pmod{N}$$ for any positive integer $$k$$.

### Examples

1. What is $$5^4 \pmod{3}$$?

Since the exponent $$5^4$$ is a repeated multiplication $$5\times5\times5\times5$$, we can perform the modular arithmetic on the product or each term of the multiplication.

For example, $$5^4=5\times 5\times 5\times 5=625$$, $$625 \pmod{3} \equiv 1 \pmod{3}$$

We can also break the exponent into the product of modulo 3s.

$$5^4 \pmod{3} =5 \pmod{3}\times 5\pmod{3} \times 5\pmod{3} \times 5\pmod{3}$$

$$\equiv 2 \pmod{3} \times 2 \pmod{3} \times 2 \pmod{3} \times 2 \pmod{3} \equiv 16 \pmod{3} \equiv 1 \pmod{3}$$.

We can even find the residue first before finding the exponent.

$$5^4 \pmod{3} \equiv [5 \pmod{3}]^4 \pmod{3} \equiv 2^4 \pmod{3} \equiv 16 \pmod{3} \equiv 1 \pmod{3}$$

2. What is $$6^{16} \pmod{7}$$?

Exponents will get large very quickly, so it helps to break it down.

$$6^{16} = \left(6^2\right)^8 = 36^8$$, so

\begin{align} &6^{16} \pmod{7} \\ \equiv &\left(6^2\right)^8 \pmod{7} \\ \equiv &36^8 \pmod{7} \\ \equiv &[36 \pmod{7}]^8 \pmod{7} \\ \equiv &(1)^8 \pmod{7} \\ \equiv &1 \pmod{7} \end{align}

3. What is $$64^{72} \pmod{13}$$?

Sometimes the exponent cannot be computed on your calculator, so you have to break the exponent down.

\begin{align} &64^{72} \pmod{13} \\ \equiv &\left(64^2\right)^{36} \pmod{13} \\ \equiv &4096^{36} \pmod{13} \\ \equiv &[4096 \pmod{13}]^{36} \pmod{13} \\ \equiv &(1)^{36} \pmod{13} \\ \equiv &1 \pmod{13} \end{align}

### Division

Division in arithmetic does not apply to all numbers. Mainly you can see that the behaviour of the $$\equiv$$ is not the same as =.

For example, consider $$4 \equiv 8 \pmod{4}$$. If we divide both sides of the equation by 2, $$2 \not\equiv 4 \pmod{4}$$.

## Practice Questions

Calculate

1. $$5^9 \mod{42}$$
2. $$2^{16} \mod{123}$$
3. $$3^{14} \mod{30}$$
4. $$15^{19} \mod{37}$$
5. $$81^{80} \mod{29}$$