Find the number of solutions to a modular equation using C++

In this article we will explain what solutions to modular equations are and we will also write a program to find multiple solutions to modular equations. Here is the basic example -

Input : X = 30 Y = 2
Output : 4, 7, 14, 28
Explanation : 30 mod 4 = 2 (equals Y),
   30 mod 7 = 2 (equals Y),
   30 mod 14 = 2 (equals Y),
   30 mod 28 = 2 (equals Y)
Input : X = 30 Y = 2
Output : 4, 7, 14, 28
Explanation : 30 mod 4 = 2 (equals Y),
   30 mod 7 = 2 (equals Y),
   30 mod 14 = 2 (equals Y),
   30 mod 28 = 2 (equals Y)

As we have seen in the above example, every integer is a solution that gives a remainder Y after dividing X. In this example, dividing 30 by 4, 7, 14, and 28 gives a remainder of 2, which is equal to Y. We will solve the modular equation this way.

Method to solve

We can apply a simple method of dividing X by every integer starting from 1 and check if it gives remainder Y, or we can put X - Y) is divided by every integer, and an integer that divides (X - Y) but not X is the solution. Let's write a C program to find different solutions to a modular equation.

Example

#include 
using namespace std;
int numberofdivisor(int X, int Y){
    int N = (X - Y);
    int noOfDivisors = 1;
    for (int i = 1; i <= N/2; i++) {
        // if N is divisible by i
        if ((N % i) == 0) {
            // count if integer is greater than Y
            if (i > Y)
                noOfDivisors++;
        }
    }
    return noOfDivisors;
}
void numberofsolutions(int X, int Y){
    int noOfSolutions;
    if (X == Y)
        noOfSolutions = -1;
    if (X < Y)
        noOfSolutions = 0;
    if (X > Y)
        noOfSolutions = numberofdivisor(X, Y);
        if (noOfSolutions == -1) {
            cout << "X can take Infinitely many values"
            " greater than " << X << "\n";
    }
    else {
        cout << "Number of solution = " << noOfSolutions;
    }
}
// main function
int main(){
    int X,Y;
        cin >> X;
        cin >> Y;
    numberofsolutions(X, Y);
    return 0;
}

Output

When we write 0 as input, the program gives the following output-

X can take Infinitely many values greater than 0

When we enter other numbers , the above program will show an output like this (here we have provided 5 as input) -

Number of solution = 2

Explanation of the above code

Now we explain each function so that you can understand it easily program.

main() function

In the main function, we take the values ​​of X and Y as input and find the number of possible solutions by calling the numberofsolutions() function.

Numberofsolutions() function

This function checks whether X and Y satisfy the condition that X should be greater than Y, because we cannot find a remainder greater than the dividend. This function calls another function numberofdivisor() and gets the number of divisors of X, resulting in the remainder Y.

Numberofdivisor() Function

This function finds the number of divisors of X - Y by running a loop from 1 to (X - Y)/2 and checking whether each integer is divisible and The integer should not exactly divide X.

Conclusion

The solution to a modular equation is an integer that divides X and gets the remainder Y; we know this from various examples. The equation can have some solutions, so we find these solutions by applying simple methods.

We can write a C program to compute the solution to the modular equation. We can write the same program in other languages ​​like C, Java, Python or any other programming language. I hope you found this article helpful in understanding the concept of how to find multiple solutions to modular equations.

The above is the detailed content of Find the number of solutions to a modular equation using C++. For more information, please follow other related articles on the PHP Chinese website!