I would like to calculate the modulus of a large number using my calculator. Considering my calculator does not support the modulus operator, I have no other choice than using this method:
To Calculate:
$41mod5$
1) I start by dividing the number by the modulus
$41 / 5=8.2$
2)Remove the integer part of the answer
$0.2$
3) Multiply by the modulus
$0.2 * 5 = 1$
This method works great for small modulus calculations, but I can't wrap my head around how to do it with bigger numbers since I can't get the non-integer part of the number
To Calculate:
$785^{13}mod1763$
1) I start by dividing the number by the modulus
$4.298387234*10^{37}$
2) Remove the integer part of the answer
???
You can easily do this in a calculator by dividing the exponent into pieces.
For example: Let's say we have to calculate 5^23 mod 221.
Divide 23 into as many pieces as you want, for example 23 = 7 + 8 + 8. The bigger the exponent, more the numbers you should divide it in. Now, calculate 5^7 mod 221, 5^8 mod 221 and 5^8 mod 221 (All three of which can easily be calculated using your method in any calculator).
5^7 mod 221 = 112
5^8 mod 221 = 118
5^8 mod 221 = 118
Now multiply all the three values, 112118118, and take its mod with 221 again. The final answer will give you your answer. So, 112 x 118 x 118 = 1559488
1559488 mod 221 = 112 which is the correct answer for 5^23 mod 221.