Count number of solutions of x ^ 2 = 1 ( mod p ) in given range | Program to count number of values that satisfy x ^ 2 = 1 mod p where x lies in range [ 1 , n ] ; Initialize result ; Traverse all numbers smaller than given number p . Note that we don 't traverse from  1 to n, but 1 to p ; 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 ] ; The largest number in the form of x + p * i in range [ 1 , n ] ; Add count of numbers of the form x + p * i . 1 is added for x itself . ; Driver code
def findCountOfSolutions ( n , p ) : NEW_LINE INDENT ans = 0 ; NEW_LINE for x in range ( 1 , p ) : NEW_LINE INDENT if ( ( x * x ) % p == 1 ) : NEW_LINE INDENT last = x + p * ( n / p ) ; NEW_LINE if ( last > n ) : NEW_LINE INDENT last -= p ; NEW_LINE DEDENT ans += ( ( last - x ) / p + 1 ) ; NEW_LINE DEDENT DEDENT return int ( ans ) ; NEW_LINE DEDENT n = 10 ; NEW_LINE p = 5 ; NEW_LINE print ( findCountOfSolutions ( n , p ) ) ; NEW_LINE