Convert the Exponent to Binary
First, we find the binary representation of the exponent, which is 55 .
$$
55_{10}=110111_2
$$
Express as a Sum of Powers of 2
The binary representation $110111_2$ shows us which powers of 2 sum up to 55 :
$$
55=(1 \cdot 32)+(1 \cdot 16)+(0 \cdot 8)+(1 \cdot 4)+(1 \cdot 2)+(1 \cdot 1)
$$
Therefore, the final product to get $a^{55}$ is:
$$
a^{55}=a^{32} \cdot a^{16} \cdot a^4 \cdot a^2 \cdot a^1
$$
Identify Calculated vs. Used Powers
To get the terms needed for the final product, we must calculate a sequence of powers by repeated squaring:
- $a^1$
- $a^2=a^1 \cdot a^1$
- $a^4=a^2 \cdot a^2$
- $a^8=a^4 \cdot a^4$
- $a^{16}=a^8 \cdot a^8$
- $a^{32}=a^{16} \cdot a^{16}$
As you can see, $a^8$ must be calculated to find $a^{16}$, but because there is a ' 0 ' in the 8 's place of the binary representation of 55 , it is not used in the final multiplication.
