Factorial Modulo

Sneha Mallik
Last Updated: May 13, 2022

Introduction 

 

In competitive programming, we often encounter the word modulo where we are asked to find out the answer in modulo as the answer can be huge, so we need to print out ‘modulo P’. 

To find the factorial modulo, we must first compute ‘N!’ and then calculate ‘N! % P’. This solution works well when the value of ‘N!’ is very small. The value of  ‘N! % P’ is usually wanted for larger values of ‘N’ when ‘N!’ cannot fit into a variable and reasons an overflow. Therefore, calculation of ‘N!’ and then performing modulation is not a great idea to proceed as for slightly larger values of ‘N’ and ‘R’, there will always be an overflow where ‘N’ denotes the total number of items and ‘R’ represents the number of items chosen at a time, and ‘P’ denotes the prime number.

 

CREDITS: GIPHY

 

Working of factorial modulo

 

Complex formulas modulo some prime ‘P’, comprising factorials in both the numerator and denominator, such as those found in the formula for Binomial coefficients we come around often. We consider this situation when ‘P’ is relatively small.

Only when factorials exist in both the numerator and denominator of fractions, this problem make sense. Otherwise, the value of ‘P!’ and succeeding terms will be 0. In fractions, however, the factors of ‘P’ can be cancelled, resulting in a non-zero modulo ‘P’ statement.

Hence, we have the challenge to calculate ‘N! mod P’ without considering all of the numerous factors of ‘P’ that exist in the factorial. Let us write N’s prime factorization while removing all the ‘P’ factors and computing the product modulo ‘P’. This updated factorial is denoted by ‘N! % P’.

Sieve Method

 

  • The Sieve Method

 

Here, the solution is to find all the primes smaller than ‘N’ using the sieve method for every prime ‘P’ while searching the highest power of it that divides N!.

The greatest possible power if a prime ‘P’ which divides ‘N’ is, 

[N / P] + [N / P2] + [N / P3] + … + 0

 

We can write every integer in the form of a multiplication of the powers of the prime numbers. Therefore, 

N! = P1K1 * P2K2 * P3K3 * … where,

P1, P2 and P3 ... are prime numbers and

K1, K2 and K3 are integers that are greater than or equal to 1. 

 

Example: We have an integer ‘N’ and ‘P’ as a prime number. We need to find the largest number, ‘X’, such that PX (P to the power of X) divides factorial ‘N’ .

                  ‘N’ = 7

                  ‘P’ = 3

                              We know, 7! = 5040

                              The highest power of the prime number ‘P’ that can help ‘P’ to divide 5040 completely is 2.

                  3divides 7!.

                  Hence, X = 2

 

 

Code:-

#include <bits/stdc++.h>
using namespace std;

/* 
    Function returning the highest power of factorial modulo P that 
    divides N!
*/
int highestPower(int N, int P){
    int result = 0;

    /* 
        Calculating the result,
        result = N/P + N/(P^2) + N/(P^3) + ...
    */
    while(N){
        N /= P;
        result += N;
    }
    return result;
}

// Function for modular exponentiation which will return (X^Y) % P
int modularExp(int X, int Y, int P){
    int ans = 1;

    // To update the 'X' value if it is equal or more than P
    X = X % P;
    while(Y > 0){

        // If the 'Y' value is odd, we will multiply X with the result
        if(Y & 1)
            ans = (ans * X) % P;

        // When the 'Y' value is even
        Y = Y >> 1;
        X = (X * X) % P;
    }
    return ans;
}

// Function for factorial modulo N! % P
int factorialMod(int N, int P){
    if(N >= P)
        return 0;

    int ans = 1;

    // Using sieve method to find out the prime numbers smaller than N
    bool primeNo[N + 1];
    memset(primeNo, 1sizeof(primeNo));
    for(int i = 2; i * i <= N; i++){
        if(primeNo[i]){
            for(int j = 2 * i; j <= N; j += i)
                primeNo[j] = 0;
        }
    }

    // To consider all the primes found by the Sieve method
    for(int i = 2; i <= N; i++){
        if(primeNo[i]){

        // To find the highest power of prime no. 'i' that divides N
        int s = highestPower(N, i);

        // We will multiply the result with (i ^ s) % P
        ans = (ans * modularExp(i, s, P)) % P; 
        }
    }
    return ans;
}

// Main program
int main(){
    int N = 6;
    int P = 11;
    cout << "The result of " << N << "! % " << P << " is " 
    << factorialMod(N, P) << ".";
    return 0;
}

 

Output:

The result of 6! % 11 is 5.

Time Complexity:

The time complexity is O(N log log N).

 

     {(N / 2) + (N / 3) + (N / 5) + (N / 7) + … + (N / P)}, 

where ‘P’ is the highest prime number, ‘P’ <= ‘N’

=> N {(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)}

where {(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)} 

is the harmonic progression of sum of primes

 

=> N (log (log N))

as {(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)} = log(log(N))

=> O(N log log N) time complexity

Space Complexity:

To find out the prime numbers from 1 to ‘N’, the space complexity is O(N) since we are creating an array of size ‘N’. It also means that if ‘N’ is constant, then the space complexity is O(1). 

 

Wilson’s Theorem Method

 

  • Wilson’s Theorem Method

 

This theorem states that natural number ‘P’ > 1 is a prime number if and only if, 

(P - 1) ! 𝞝 -1 % P, or

(P - 1) ! 𝞝 (P - 1) % P

 

If N >= P, then N! % P = 0.

This method is possible when P is relatively close to the input number N.

 

Example: 28! = 1

 

Code:-

#include <bits/stdc++.h>
using namespace std;

// Function for modular exponentiation which will return (X^Y) % P
int modularExp(int X, unsigned int Y, int P){
    int ans = 1;

    // To update the 'X' value if it is equal or more than P
    X = X % P;
    while(Y > 0){

        // If the 'Y' value is odd, we will multiply X with the result
        if(Y & 1)
            ans = (ans * X) % P;

        // When the 'Y' value is even
        Y = Y >> 1;
        X = (X * X) % P;
    }
    return ans;
}
/* 
    Function returning the modular inverse of modulo P assuming P is 
    prime( using Fermat's method)
*/
int inverseMod(int N, int P){
    return modularExp(N, P - 2, P);
}

// Function for factorial modulo N! % P
int factorialMod(int N, int P){
    if(N >= P)
        return 0;
    // To initialise the result as (P - 1)! , i.e., -1 or (P - 1)
    int ans = (P - 1);

    // To multiply the modulo inverse of all the no.s from (N + 1)
    for(int i = N + 1; i < P; i++){
        ans = (ans * inverseMod(i, P)) % P; 
    }
    return ans;
}

// Main program
int main(){
    int N = 6;
    int P = 11;
    cout << "The result of " << N << "! % " << P << " is " 
    << factorialMod(N, P) << ".";
    return 0;
}

 

Output:

The result of 6! % 11 is 5.

 

Time Complexity:

The time complexity for this approach will be O((P - N)* log N).

As, (P - 1)! = (P - 1) (P - 2) (P - 3) … 3 x 2 x 1

            = (P - N) x (log N), where ’P’ is the prime number.

 

Space Complexity:

To find out the prime numbers from 1 to ‘N’, the space complexity is O(N) since we are creating an array of size ‘N’. It also means that if ‘N’ is constant, then the space complexity is O(1). 

 

Algorithm for factorial modulo using Brute-force Approach

Simple Method

The method is to multiply the result one by one with ‘i’ under the modulo ‘P’. Therefore, the value of the result does not exceed ‘P’ before the next iteration. 

Example:  ‘N’ = 5

                  ‘P’ = 13

                  ‘N! % P’ = 120 % 13  = 3 

 

 

  • The concept here is to apply the brute force approach.
  • We can consider computing N! first and then move on to find modulo P. But this could cause the overflow hassle because N! might be a large number. So, computing N! and then applying % is not a good idea.
  • We can conquer this hassle via using the modulo operator in each iteration. In other words, we can multiply one by one with ‘i’ under modulo ‘P’.
  • We will first declare a variable ‘ans’ = 1.
  • We then run a loop from ‘i’ = 1 to ‘i’ <= N, at each iteration do:

ans = (ans * i) % P

  • We will then return the ‘ans’.

As we know, 

(A * B) % M == ((A % M) * (B % M)) % M

For the factorial,

N! = 1 * 2 * 3 * … * (N - 1) * N

Therefore, we get

N! % M = (((((((1 * 2) % M) * 3) % M) * … * N -1) % M) * N) % M

 

 

Implementation of factorial modulo in C++

#include <bits/stdc++.h>
using namespace std;

// Computes the value of N! % P
int factorialModulo(int N, int P){
    if(N >= P){
        return 0;
    }
    int ans = 1;


    for(int i = 1; i <= N; i++){
        ans = (ans * i) % P;
    }
    return ans;
}

// Driver code
int main(){
    int N = 6;
    int P = 11;
    cout << "The result of " << N << "! % " << P << " is " 
    <<factorialModulo(N, P)<<".";
    return 0;
}

 

OUTPUT-

The result of 6! % 11 is 5.

 

Time Complexity 

The time complexity for this problem is O(N). As we are using one single iteration from 1 to ‘N’.

Space Complexity 

The space complexity for this algorithm is O(1) as the space required by the above algorithm to process the data is constant.

 

Frequently Asked Questions

What is meant by ‘ print in modulo 10+ 7 ’?

(10+ 7) is the first ten-digit prime number, and printing the answer in modulo ensures that the answer fits in the maximum value that our system can store, which is generally consistent with the question setter's code or case tester's code. This also makes sure that it prevents ‘integer overflow’ during the compilation process as it takes significant effort to store and process actual huge value.

What is the need for modulo?

We need modulo to avoid ‘integer overflow’ as in C / C++, the largest integer data type is of 64 bit (unsigned long long int), which can only handle data from 0 to 264 - 1.

In several problems, to compute the end result, modulo inverse is wanted, and (10+ 7) is the number that helps in this case as it is prime and large enough or else modular inverse strategies can also additionally fail in some situations.

List out some properties of modulo.

Some properties of modulo are following:-

(A + B) % C = ((A % C) + (B % C)) % C

(A * B) % C = ((A % C) * (B % C)) % C

(A - B) % C = ((A % C) - (B % C)) % C

(A / B) % C ≠ ((A % C) / (B % C)) % C

(A / B) % C = (A * ( B-1 )) % C

Note: The result of (A % B) is always less than B.

What is Wilson’s theorem?

This theorem states that a natural number N > 1 is a prime number if and only if the product of all the positive numbers less than N is one less than the multiple of N. 

(N - 1)! = 1 * 2 * 3 * .... * (N - 1) satisfies

(N - 1)! 𝞝 -1 (mod N)

Here, ‘N’ is a prime number.

 

Or, we can say, any number ‘N’ is a prime number iff (N - 1)! + 1 is divisible by N.

 

What is the multiplicity of P?

We need VP, the multiplicity of P, for computing the binomial coefficient modulo P.

                                                                                                                             

int multiplicityFactorial(int N, int P){
    int count = 0;
    do {
        N /= P;
        count += N;
    }
    while(N);
    return count;
}

The idea behind this is to remove all the elements that do not contain the factor P. This leaves [N / P] elements remaining. If we remove the factor P from each, we get the product as 1 * 2 * 3 * … * [N / P] = [N / P]! using the recursion process.

Key Takeaways

In this blog, we learned about implementing factorial modulo, the working of factorial modulo and some basic concepts. If you want to know more about Modulo Arithmetic then you can visit modulo arithmetic for a sound knowledge of concepts of factorial modulo.

If you want to practice more problems then you can visit CodeStudio to understand the working concept of factorial modulo. 

CREDITS: GIPHY

 

By Sneha Mallik

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think