0
$\begingroup$

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

???

$\endgroup$
5
  • 1
    $\begingroup$ Don't a calculator $\endgroup$
    – user251257
    Oct 17, 2016 at 19:33
  • 1
    $\begingroup$ Your calculator is not the best tool for the job. If you want to do it on your calculator though. Find $785^2\pmod{1763}. 785^3\pmod {1763} \equiv 785(785^2\pmod{1763})\pmod{1763}$ Repeat as necessary. $\endgroup$
    – Doug M
    Oct 17, 2016 at 19:35
  • 2
    $\begingroup$ To continue the comment of @DougM, if you're going for high exponents, the fastest way is something called repeated squaring: Instead of calculating $785^3 = 785^2\cdot 785$ and then $785^4 = 785^3\cdot 785$ and so on, you can move faster to higher indices by calculating $785^4 = 785^2\cdot 785^2, 785^8 = 785^4\cdot785^4$ and so on (of course reducing modulo $1763$ at all steps). That way you get to $785^{13}$ doing not $12$ multiplications, but rather $5$ (three multiplications to find $785^2, 785^4, 785^8$, and then two more multiplications for $785^{13} = 785\cdot 785^4\cdot785^8$). $\endgroup$
    – Arthur
    Oct 17, 2016 at 19:44
  • $\begingroup$ If you just need to calculate powers modulo some number, wolfram alpha has built-in modular exponentiation. But if you only have access to a pocket calculator (e.g. in an exam), or you're supposed to show your work, use the repeated squaring method described by Arthur above. $\endgroup$
    – cardboard_box
    Oct 17, 2016 at 19:47
  • 1
    $\begingroup$ If you were doing this with pencil and paper you would say $1763=41\cdot43, 785^{13}\equiv 24\pmod{41}, 785^{13}\equiv 4\pmod{43}, 43\equiv 2\pmod{41} \implies 785^{13}\equiv 10\cdot 43 +4 \pmod{1763}$ $\endgroup$
    – Doug M
    Oct 17, 2016 at 21:15

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ For some basic information about writing mathematics at this site see, e.g., here, here, here and here. $\endgroup$
    – Another User
    May 1 at 21:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .