CODEWITHSUNDEEP
calgorithm
cosmos
cosmos

Reputation: 2303

how to calculate modulus division

I am stuck in a program while finding modulus of division.

Say for example I have:

((a*b*c)/(d*e)) % n

Now, I cannot simply calculate the expression and then modulo it to n as the multiplication and division are going in a loop and the value is large enough to not fit even in long long.

As clarified in comments, n can be considered prime.

I found that, for multiplication, I can easily calculate it as:

((a%n*b%n)%n*c%n)%n

but couldn't understand how to calculate the division part then.

The problem I am facing is say for a simple example:

((7*3*5)/(5*3)) % 11

The value of above expression would be 7

but if I calculate the multiplication, modulo, it would be like:

((7%11)*(3%11))%11 = 10
((10%11)*(5%11))%11 = 6

now I am left with 6/15 and I have no way to generate correct answer.

Could someone help me. Please make me understand the logic by above example.

Upvotes: 3

Views: 1224

Answers (7)

jxh
jxh

Reputation: 70362

Since 11 is prime, Z11 is a field. Since 15 % 11 is 4, 1/15 equals 3 (since 3 * 4 % 11 is 1). Therefore, 6/15 is 6 * 3 which is 7 mod 11.

In your comments below the question, you clarify that the modulus will always be a prime.

To efficiently generate a table of multiplicative inverses, you can raise 2 to successive powers to see which values it generates. Note that in a field Zp, where p is an odd prime, 2p-1 = 1. So, for Z11:

 2^1 = 2
 2^2 = 4
 2^3 = 8
 2^4 = 5
 2^5 = 10
 2^6 = 9
 2^7 = 7
 2^8 = 3
 2^9 = 6

So the multiplicative inverse of 5 (which is 24) is 26 (which is 9).

So, you can generate the above table like this:

power_of_2[0] = 1;
for (int i = 1; i < n; ++i) {
    power_of_2[i] = (2*power_of_2[i-1]) % n;
}

And the multiplicative inverse table can be computed like this:

mult_inverse[1] = 1;
for (int i = 1; i < n; ++i) {
    mult_inverse[power_of_2[i]] = power_of_2[n-1-i];
}

Upvotes: 5

fuch
fuch

Reputation: 156

As n is prime, dividing an integer b is simply multiplying b's inverse. That is:

(a / b) mod n = (a * inv(b)) mod n

where

inv(b) = (b ^ (n - 2)) mod n

Calculating inv(b) can be done in O(log(n)) time using the Exponentiation by squaring algorithm. Here is the code:

int inv(int b, int n)
{
    int r = 1, m = n - 2;
    while (m)
    {
        if (m & 1) r = (long long)r * b % n;
        b = (long long)b * b % n;
        m >>= 1;
    }
    return r;
}

Why it works? According to Fermat's little theorem, if n is prime, b ^ (n - 1) mod n = 1 for any positive integer b. Therefore we have inv(b) * b mod n = 1.

Another solution for finding inv(b) is the Extended Euclidean algorithm, which needs a bit more code to implement.

Upvotes: 2

user2566092
user2566092

Reputation: 4661

I think the way the question is asked, it should be assumed that the numerator is divisible by the denominator. In that case the finite field solution for prime n and speculations about possible extensions and caveats for non-prime n is basically overkill. If you have all the numerator terms and denominator terms stored in arrays, you can iteratively test pairs of (numerator term, denominator term) and quickly find the greatest common divisor (gcd), and then divide the numerator term and denominator term by the gcd. (Finding the gcd is a classical problem and you can easily find a simple solution online.) In the worst case you will have to iterate over all possible pairs but at some point, if the denominator indeed divides the numerator, then you'll eventually be left with reduced numerator terms and all denominator terms will be 1. Then you're ready to apply multiplication (avoiding overflow) the way you described.

Upvotes: 2

Pieter Geerkens
Pieter Geerkens

Reputation: 11883

In your example, since 15 = 4 mod 11, you actually end up with having to evaluate (6/4) mod 11.

In order to find an exact solution to this, rearrange it as 6 = ( (x * 4) mod 11), which makes clearer how the modulo division works.

If nothing else, if the modulus is always small, you can iterate from 0 to modulus-1 to get the solution.

Note that when the modulus is not prime, there may be multiple solutions to the reduced problem. For instance, there are two solutions to 4 = ( ( x * 2) mod 8): 2 and 6. This will happen for a reduced problem of form:

  a = ( (x * b) mod c)

whenever b and c are NOT relatively prime (ie whenever they DO share a common divisor).

Similarly, when b and c are NOT relatively prime, there may be no solution to the reduced problem. For instance, 3 = ( (x * 2) mod 8) has no solution. This happens whenever the largest common divisor of b and c does not also divide a.

These latter two circumstances are consequences of the integers from 0 to n-1 not forming a group under multiplication (or equivalently, a field under + and *) when n is not prime, but rather forming simply the less useful structure of a ring.

Upvotes: 2

DarenW
DarenW

Reputation: 16906

Instead of dividing, think in terms of multiplicative inverses. For each number in a mod-n system, there ought to be an inverse, if certain conditions are met. For d and e, find those inverses, and then it's all just multiplying. Finding the inverses is not done by dividing! There's plenty of info out there...

Upvotes: 0

Eric Kim
Eric Kim

Reputation: 41

I think the problem you had was that you picked a problem that was too simple for an example. In that case the answer was 7 , but what if a*b*c was not evenly divisible by c*d ? You should probably look up how to do division with modulo first, it should be clear to you :)

Upvotes: 0

Niklas R
Niklas R

Reputation: 16860

I think you can distribute the division like

z = d*e/3
(a/z)*(b/z)*(c/z) % n

Remains only the integer division problem.

Upvotes: 0

Related Questions