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\). |
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 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}\).
Calculate
