I am learning for an exam and want to understand this:
Calculate $3^{142} \mod 50$.
Solution:
$\operatorname{HCF}(3, 50) = 1$
$\varphi(50) = \varphi(5 \cdot 5 \cdot 2) = \varphi(5^2 \cdot 2) = \varphi(5^2) \cdot \varphi(2) = 20 \implies$
$3^{20}\equiv 1 \mod 50$ // <- oO
$3^{142} = 3^{140+2} = 3^{7\cdot 20} \cdot 9 \equiv 9 \mod 50.$
I solved it for myself and I struggle when the solution says $3^{20} \equiv 1 \mod 50$. Please help me to understand this step.
Thanks in advance.
