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
< ? php function findCountOfSolutions ( $ n , $ p ) { $ ans = 0 ; for ( $ x = 1 ; $ x < $ p ; $ x ++ ) { if ( ( $ x * $ x ) % $ p == 1 ) { $ last = $ x + $ p * ( $ n / $ p ) ; if ( $ last > $ n ) $ last -= $ p ; $ ans += ( ( $ last - $ x ) / $ p + 1 ) ; } } return $ ans ; } $ n = 10 ; $ p = 5 ; echo findCountOfSolutions ( $ n , $ p ) ; ? >