How can I calculate ${2133}^{5525}$ mod ${7387}$?

Question

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?

1. ${2133}^{5525}\pmod{7387}$
2. ${0429}^{5525}\pmod{7387}$
3. ${1126}^{5525}\pmod{7387}$

I know that the solutions are:

1. $2431$

2. $2312$

3. $1528$

Answer 1

• 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}$.

Answer 2

$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.