How can I calculate ${2133}^{5525}$ mod ${7387}$? I would like to calculate the modulus of a large number.
How can I do it? Is there an easy way to calculate it, without really using the calculator? How can I get these solutions?


*

*${2133}^{5525}\pmod{7387}$ 

*${0429}^{5525}\pmod{7387}$

*${1126}^{5525}\pmod{7387}$
I know that the solutions are:


*

*$2431$

*$2312$

*$1528$
 A: $7387=(83)(89)$
Start by reducing exponentiation
$\begin{cases}
2133^{5525}\pmod{83}\equiv(2133\pmod{83})^{5525\pmod{82}}\equiv 58^{31}\pmod{83}\equiv 28\pmod{83}\\
2133^{5525}\pmod{89}\equiv(2133\pmod{89})^{5525\pmod{88}}\equiv 86^{69}\pmod{89}\equiv 24\pmod{89}
\end{cases}$
By Chinese remainder theorem then $2133^{5525}\pmod{7387}\equiv 2431\pmod{7387}$
For the intermediate calculations (of $24$ and $28$) there are still some calculation to do, exploit small congruences (for instance $86\equiv -3\pmod{89}$) and dichotomy on the exponent.
I let you do the other ones.
A: *

*First of all, $7387$ is not a prime number, it is $83*89$. You need to calculate the answer module these primes. Then, by CRT, the answer will follow to the given number.

*You may need to use Fermat Theorem which says $a^{p-1} \equiv 1 \pmod p$ if $\gcd(a,p) = 1$ to reduce these huge powers. For example, with the prime $83$, you may notice that $5525=62*88+69$. Now, $2133^{5525} \equiv (2133^{88})^{62} \times 2133^{69} \equiv 2133^{69} \pmod {89}$. Now, $2133^{69}$still big for the calculator?, we can use the following trick. It is called repeated squaring.
I will solve $2133^{69}$ using this method, the others you just follow it up. Now, $2133^2 \equiv 9 \pmod {89}$ and $9^2 \equiv -8 \pmod {89}$ and $(-8)^2 \equiv 64 \pmod {89}$. This way, we have calculated $2133^{2^{2^{2}}} = 2133^{16}$. Now, we can multiply this number $\pmod {89}$ 4 times to get $2133^{16+16+16+16} = 2133^{64}$. This yields $2133^{64} \equiv 4 \pmod {89}$. Further, we need to multiply it by $2133^5 = 2133^{4+1} \equiv -8*2133 \equiv 24 \pmod {89}$.
