Count number of solutions of x^2 = 1 (mod p) in given range - GeeksforGeeks

Count number of solutions of x^2 = 1 (mod p) in given range - GeeksforGeeks
Given two integers n and p, find the number of integral solutions to x² = 1 (mod p) in the closed interval [1, n].

One simple solution is to go through all numbers from 1 to n. For every number, check if it satisfies the equation. We can avoid going through the whole range. The idea is based on the fact that if a number x satisfies the equation, then all numbers of the form x + i*p also satisfy the equation. We traverse for all numbers from 1 to p and for every number x that satisfies the equation, we find the count of numbers of the form x + i*p. To find the count, we first find the largest number for given x and then add (largest-number – x)/p to the result.

int findCountOfSolutions(int n, int p)

{

    // Initialize result

    ll ans = 0;

 

    // Traverse all numbers smaller than

    // given number p. Note that we don't

    // traverse from 1 to n, but 1 to p

    for (ll x=1; x<p; x++)

    {

        // If x is a solution, then count all

        // numbers of the form x + i*p such

        // that x + i*p is in range [1,n]

        if ((x*x)%p == 1)

        {

            // The largest number in the

            // form of x + p*i in range

            // [1, n]

            ll last = x + p * (n/p);

            if (last > n)

                last -= p;

 

            // Add count of numbers of of the form

            // x + p*i. 1 is added for x itself.

            ans += ((last-x)/p + 1);

        }

    }

    return ans;

}

Read full article from Count number of solutions of x^2 = 1 (mod p) in given range - GeeksforGeeks