Skip to main content
It looks like you're using Internet Explorer 11 or older. This website works best with modern browsers such as the latest versions of Chrome, Firefox, Safari, and Edge. If you continue with this browser, you may see unexpected results.

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