CODEWITHSUNDEEP
javacalgorithmmathdata-structures
someone
someone

Reputation: 19

Issue with inverse modulo where gcd(denominator,mod)!=1

How do I compute F(n)%mod where mod is a prime number. and F(n)=n!/(q!^r)%mod....(x^r stands for pow(x,r)).

I'm trying it with fermat's little theorem for computing the inverse modulo but the problem I'm facing is that fermat is applicable only if gcd(denominator,mod)=1.

So is there any other way to solve this.

Upvotes: 1

Views: 1396

Answers (3)

AlexAlvarez
AlexAlvarez

Reputation: 829

As you are trying to compute this quotient modulo p (for a certain prime), let me assume that you know the result is an integer.

As people have mentioned, if q >= p, then you cannot compute the inverse of the denominator, as q! is not coprime with the modulo, so this number is not invertible. But that does not mean that you cannot compute the whole quotient modulo p.

Let a, b be the number of p factors in the numerator and the denominator, respectively. As the result is an integer, we have a >= b. If the inequality is strict, then the result is 0. Otherwise, if equality holds we can remove those factors from numerator and denominator and proceed, as now the denominator is coprime with p.

So let me start with the method for computing those a, b numbers efficiently. The key is known as De Polignac's formula, and it says that for a given k, the number of p factors in k! can be calculated like this:

int polignac(int k, int p) {
  int res = 0, power = p;
  while (k >= power) {
    res += k/power;
    power *= p;
  }
  return res;
}

So with this we obtain the p factors for both n! and q!, so it is trivial to obtain the p factors of q!^r (just multiply by r).

In the strict inequality case, we are done. If not, we have to compute the modulo of both numerator and denominator "dropping" all the p factors. This can also be efficiently solved. We can write k! like this:

k! = 1 x 2 x 3 x ... x p x (p + 1) x (p + 2) ... x (p^2) x ...

If we remove the p factors and apply modulo, we have the following:

k! = 1 x 2 x 3 x ... x (nothing here, just a 1) x 1 x 2 ... x (another 1) x ...

Therefore, the same product keeps repeating until the end. So calculate 1 x 2 x ... x (p - 1) modulo p, raise it to the proper power modulo p (using fast exponentiation) and just multiply it be the "reamaining" terms, as in general k is not divisible by p.

Upvotes: 0

Louis Wasserman
Louis Wasserman

Reputation: 198093

There is no modular inverse if the gcd is not 1. Right at the top of the Wikipedia page:

The multiplicative inverse of a modulo m exists if and only if a and m are coprime (i.e., if gcd(a, m) = 1).

Upvotes: 1

user448810
user448810

Reputation: 17876

If the modulus is prime, you can compute the inverse using the extended Euclidean algorithm:

function inverse(x, m)
    a, b, u = 0, m, 1
    while x > 0
        q = b // x # integer division
        x, a, b, u = b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

If the modulus is composite, this algorithm will still work as long as x and m are coprime. If they share a factor, then the inverse does not exist.

Upvotes: 1

Related Questions