Reducing Large Powers using Modular Relations

Purpose
The purpose of this activity is give some strategies to reducing large powers using modular relations.

Reduction Techniques for a^b \mod m.
(1) Reduce the base of exponentiation a modulo m.
(2) Look at powers of a \mod m, then split the power with respect to a nice power of a \mod m.
(3) If m is a prime, apply Fermat’s Little Theorem.

Example 1: Determine 30^{70} \mod 27.
Using Technique (1), 30 \equiv 3 \mod 27, therefore,

    \[30^{70} \equiv 3^{70} \mod 27\]


Using Technique (2), observe that

    \begin{align*}3^1 &\equiv 3 \mod 27 \\3^2 &\equiv 9 \mod 27 \\3^3 &\equiv 0 \mod 27 \end{align*}


It is much easier to compute 0^n then it is 3^n. Therefore, we split the power with respect to 3, i.e. 70=3(23)+1. Therefore,

    \begin{align*}3^{70} &\equiv 3^{3(23)+1} \mod 27 \\& \equiv (3^3)^{23}\cdot 3^1 \mod 27 \\& \equiv 0^{23}\cdot 3 \mod 27 \\& \equiv 0 \mod 27\end{align*}

Example 2: Determine 125^{801}\mod 21.
Using Technique (1), 125=5^3, therefore,

    \[125^{801}\equiv 5^{2403} \mod 21\]


Using Technique (2), observe that

    \begin{align*}5^1 &\equiv 5 \mod 21 \\5^2 &\equiv 4 \mod 21 \\5^3 &\equiv 20 \mod 21 \\\end{align*}


Note that -1\equiv 20\mod 21. Therefore, 5^6 \equiv 1 \mod 21 and 2403=6(400)+3,

    \begin{align*}5^{2403} &\equiv 5^{6(400)+3} \mod 21 \\ &\equiv (5^6)^{400}\cdot 5^3 \mod 21 \\&\equiv 1^{400}\cdot 20 \mod 21 \\&\equiv 20 \mod 21\end{align*}