Using Euler's Theorem to Simplify Powers Modulus n
\[n\]
, \[a^{\phi(n)} \equiv 1 \; (mod \; n)\]
where \[\phi(n)\]
is the number of positive integers up to \[n\]
that are prime relative to \[n\]
.We can use Euler's Theorem in the following way.
Find
\[23^{23} \; (mod \; 15)\]
.The greatest common divisor of 15 and 23 is 1, and
\[\phi (15)=8\]
, Euler's Theorem tells us that \[23^8 \equiv 1 \; (mod \; 15)\]
. Then\[\begin{equation} \begin{aligned} 23^{23} & \equiv ((23)^8)^2 \times 23^7 \; (mod \; 15) \\ & \equiv 1^2 \times 8^7 \; (mod \; 15) \\ & \equiv 64^3 \times 8 \; (mod \; 15) \\ & \equiv 4^3 \times 8 \; (mod \; 15) \\ & \equiv 64 \times 8 \; (mod \; 15) \\ & \equiv 4 \times 8 \; (mod \; 15) \\ & \equiv 32 \; (mod \; 15) \\ & \equiv 2 \; (mod \; 15) \end{aligned} \end{equation}\]
