How the property of modulous (A*B)%m = (A%m * B%m) %m is used to find the mod of very large numbers

aravind ks 0
Viewed 31

I saw the property of mod where

(A*B)%m = (A%m * B%m) %m

And this property is used in the below algorithm to find the mod of very large numbers.

  1. Get one variable to store the answer initialized to zero.

  2. Scan the string from left to right,

  3. every time multiply the answer by 10 and add the next number and take the modulo and store this as the new answer.

But I'm unable to understand this algorithm . How the property is connected to the algorithm here?

It will be helpful if used an example to understand the underneath math behind the algorithm , for example 12345%100

mod number-theory math numbers algorithm
1 Answers

Using this algorithm, 23 % k is computed as

(2%k * 10 + 3)%k
((2%k * 10)%k + 3)%k        // because (a+b)%k = (a%k + b)%k  (1)
(((2%k)%k * 10%k)%k + 3)%k  // because (a*b)%k = (a%k * b%k)%k  (2)
((2%k * 10%k)%k + 3)%k      // because (a%k)%k = a%k  (trivial)
((2 * 10)%k + 3)%k          // because (a%k * b%k)%k = (a*b)%k  (2)
(2 * 10 + 3)%k              // because (a%k + b)%k = (a+b)%k  (1)
23%k

In other words, (a%k * p + b)%k = (a * p + b)%k thanks to that property (2). b is the last digit of a number in base p (p = 10 in your example), and a is the rest of the number (all the digits but the last).

In my example, a is just 2, but if you apply this recursively, you have your algorithm. The point is that a * p + b might be too big to handle, but a%k * p + b probably isn't.

Nelfeal0
Related