Find the remainder

Question

I need to find the remainder when $(59^{73})^{5!}$ Is divided by $37$. It has some binomial expression as well. I am not able to compute the powers.Please help

Regards

Answer 1

$37$ is prime so by Fermat's Little theorem $59^{36}\equiv 1 \bmod 37$.

notice $(59^{73})^{5!}=59^{37\cdot 120}=59^{4440}\equiv(59^{36})^{123}\cdot59^{12}\equiv 59^{12}\bmod 36$

So now we only need to calculate $59^{12} \bmod 37$. First of all notice $59\equiv12 \bmod 37$.For the rest we can use exponentiation by squaring by the following exponents: $3\leadsto 6\leadsto 12$

$59^3\equiv21^3=9261\equiv 11\bmod 37\leadsto$

$59^6\equiv(21^3)^2\equiv11^2=121\equiv 10 \bmod 37 \leadsto$

$59^{12}\equiv10^2=100\equiv 26 \bmod 37$.

So $(59^{73})^{5!}\equiv 26 \bmod 37$