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

Given two integers n and p, find the number of integral solutions to x2 = 1 (mod p) in the closed interval [1, n].

Examples:

```Input : n = 10, p = 5
Output : 4
There are four integers that satisfy the equation
x2 = 1. The numbers are 1, 4, 6 and 9.

Input : n = 15, p = 7
Output : 5
There are five integers that satisfy the equation
x2 = 1. The numbers are 1, 8, 15, 6 and 13.
```

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.

Below is implementation of the idea.

## C++

 `// C++ program to count number of values ` `// that satisfy x^2  = 1 mod p where x lies ` `// in range [1, n] ` `#include ` `using` `namespace` `std; ` `typedef` `long` `long` `ll; ` ` `  `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 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; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``ll n = 10, p = 5; ` `    ``printf``(````"%lld "````, findCountOfSolutions(n, p)); ` `    ``return` `0; ` `} `

## Java

 `// Java program to count  ` `// number of values that  ` `// satisfy x^2 = 1 mod p  ` `// where x lies in range [1, n] ` `import` `java.io.*; ` ` `  `class` `GFG ` `{ ` `static` `int` `findCountOfSolutions(``int` `n,  ` `                                ``int` `p) ` `{ ` `    ``// Initialize result ` `    ``int` `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` `(``int` `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] ` `            ``int` `last = x + p * (n / p); ` `            ``if` `(last > n) ` `                ``last -= p; ` ` `  `            ``// Add count of numbers  ` `            ``// of the form x + p*i.  ` `            ``// 1 is added for x itself. ` `            ``ans += ((last - x) / p + ``1``); ` `        ``} ` `    ``} ` `    ``return` `ans; ` `} ` ` `  `// Driver code ` `public` `static` `void` `main (String[] args)  ` `{ ` `    ``int` `n = ``10``; ` `    ``int` `p = ``5``; ` `    ``System.out.println( ` `               ``findCountOfSolutions(n, p)); ` `} ` `} ` ` `  `// This code is contributed by ajit `

/div>

## Python3

 `# Program to count number of  ` `# values that satisfy x^2 = 1  ` `# mod p where x lies in range [1, n] ` ` `  `def` `findCountOfSolutions(n, p): ` `     `  `    ``# Initialize result ` `    ``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` `x ``in` `range``(``1``, 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] ` `        ``if` `((x ``*` `x) ``%` `p ``=``=` `1``): ` `             `  `            ``# The largest number in the ` `            ``# form of x + p*i in range ` `            ``# [1, n] ` `            ``last ``=` `x ``+` `p ``*` `(n ``/` `p); ` `            ``if` `(last > n): ` `                ``last ``-``=` `p; ` ` `  `            ``# Add count of numbers of  ` `            ``# the form x + p*i. 1 is  ` `            ``# added for x itself. ` `            ``ans ``+``=` `((last ``-` `x) ``/` `p ``+` `1``); ` `    ``return` `int``(ans); ` ` `  `# Driver code ` `n ``=` `10``; ` `p ``=` `5``; ` `print``(findCountOfSolutions(n, p)); ` `     `  `# This code is contributed by mits `

## C#

 `// C# program to count  ` `// number of values that  ` `// satisfy x^2 = 1 mod p  ` `// where x lies in range [1, n] ` `using` `System; ` ` `  `class` `GFG ` `{ ` `static` `int` `findCountOfSolutions(``int` `n,  ` `                                ``int` `p) ` `{ ` `    ``// Initialize result ` `    ``int` `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` `(``int` `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] ` `            ``int` `last = x + p * (n / p); ` `            ``if` `(last > n) ` `                ``last -= p; ` ` `  `            ``// Add count of numbers  ` `            ``// of the form x + p*i.  ` `            ``// 1 is added for x itself. ` `            ``ans += ((last - x) / p + 1); ` `        ``} ` `    ``} ` `    ``return` `ans; ` `} ` ` `  `// Driver code ` `static` `public` `void` `Main () ` `{ ` `    ``int` `n = 10; ` `    ``int` `p = 5; ` `    ``Console.WriteLine( ` `            ``findCountOfSolutions(n, p)); ` `} ` `} ` ` `  `// This code is contributed by ajit `

## PHP

 ` ``\$n``) ` `                ``\$last` `-= ``\$p``; ` ` `  `            ``// Add count of numbers of  ` `            ``// the form x + p*i. 1 is  ` `            ``// added for x itself. ` `            ``\$ans` `+= ((``\$last` `- ``\$x``) / ``\$p` `+ 1); ` `        ``} ` `    ``} ` `    ``return` `\$ans``; ` `} ` ` `  `// Driver code ` `\$n` `= 10; ` `\$p` `= 5; ` `echo` `findCountOfSolutions(``\$n``, ``\$p``); ` `     `  `// This code is contributed by ajit ` `?> `

Output:

```4
```

## tags:

Mathematical Mathematical