cyberangles blog

Counting the Number of Solutions of \(x^{2}\equiv1\pmod{p}\) in a Given Range

In number theory, congruence equations play a crucial role. One such fundamental congruence is (x^{2}\equiv1\pmod{p}), where (p) is a prime number. Understanding the number of solutions of this congruence and then extending it to count the number of solutions within a given range is an interesting problem. This blog will explore the concepts, methods, and examples related to this topic.

2026-07

Table of Contents#

  1. Solving (x^{2}\equiv1\pmod{p}) - Basic Case
  2. Generalizing to a Given Range
  3. Common Practices and Best Practices
  4. Example Usage
  5. References

1. Solving (x^{2}\equiv1\pmod{p}) - Basic Case#

Theory#

Let (p) be a prime number. We want to find all integers (x) such that (x^{2}-1=(x - 1)(x + 1)\equiv0\pmod{p}). By the property of prime numbers, if (ab\equiv0\pmod{p}), then either (a\equiv0\pmod{p}) or (b\equiv0\pmod{p}). So, (x^{2}\equiv1\pmod{p}) implies (x\equiv1\pmod{p}) or (x\equiv - 1\pmod{p}). When (p = 2), (x^{2}\equiv1\pmod{2}) has one solution ((x\equiv1\pmod{2})), because (1^{2}\equiv1\pmod{2}) and (0^{2}\equiv0\pmod{2}). For (p>2), we have two distinct solutions: (x_{1}\equiv1\pmod{p}) and (x_{2}\equiv p - 1\pmod{p}) (since (-1\equiv p - 1\pmod{p})).

Mathematical Formulation#

For a prime (p), the set of solutions of (x^{2}\equiv1\pmod{p}) is (S=\begin{cases}{1},&p = 2\{1,p - 1},&p>2\end{cases})

2. Generalizing to a Given Range ([a,b])#

Method#

Let (p) be a prime. To count the number of solutions of (x^{2}\equiv1\pmod{p}) in the range ([a,b]), we first find the solutions (x_{1}) and (x_{2}) (as described above) modulo (p). Then we find the smallest non - negative integers (k_{1}) and (k_{2}) such that (x_{1}+k_{1}p\geq a) and (x_{2}+k_{2}p\geq a). Similarly, we find the largest non - negative integers (m_{1}) and (m_{2}) such that (x_{1}+m_{1}p\leq b) and (x_{2}+m_{2}p\leq b).

The number of solutions from the first residue class (x_{1}) (mod (p)) is (n_{1}=\left\lfloor\frac{b - x_{1}}{p}\right\rfloor-\left\lceil\frac{a - x_{1}}{p}\right\rceil + 1) (if (x_{1}\in[a,b]), otherwise we adjust the formula based on the position of (x_{1}) relative to the interval ([a,b])). Similarly for the second residue class (x_{2}) (mod (p)).

Algorithm#

  1. Check if (p = 2):
    • If (p = 2), the solution is (x = 1). Check if (1\in[a,b]). If yes, the count is (1), else (0).
  2. For (p>2):
    • Let (x_{1}=1) and (x_{2}=p - 1).
    • For (x_{1}):
      • (k_{1}=\max\left(0,\left\lceil\frac{a - 1}{p}\right\rceil\right))
      • (m_{1}=\left\lfloor\frac{b - 1}{p}\right\rfloor)
      • (n_{1}=m_{1}-k_{1}+1) (if (1+(k_{1})p\leq b) and (1+(m_{1})p\geq a))
    • For (x_{2}):
      • (k_{2}=\max\left(0,\left\lceil\frac{a-(p - 1)}{p}\right\rceil\right))
      • (m_{2}=\left\lfloor\frac{b-(p - 1)}{p}\right\rfloor)
      • (n_{2}=m_{2}-k_{2}+1) (if ((p - 1)+(k_{2})p\leq b) and ((p - 1)+(m_{2})p\geq a))
    • The total number of solutions (N=n_{1}+n_{2}) (after checking for overlaps. In most cases, since (x_{1}\not\equiv x_{2}\pmod{p}) for (p>2), there are no overlaps)

3. Common Practices and Best Practices#

Common Practices#

  • Pre - compute Prime Numbers: If you are dealing with multiple ranges and primes, it is useful to pre - compute a list of prime numbers (using algorithms like the Sieve of Eratosthenes) within a certain bound.
  • Modular Arithmetic Libraries: In programming, use built - in modular arithmetic functions (e.g., in Python, the % operator for basic modulo operations) to simplify calculations.

Best Practices#

  • Error Handling: When dealing with ranges where (a>b), return (0) immediately. Also, handle the case (p = 1) (though (p = 1) is not a prime, but in some incorrect inputs) gracefully.
  • Efficiency: If the range ([a,b]) is large, avoid iterating through each number in the range. Use the formula - based approach described above.

4. Example Usage#

Example 1: (p = 3), ([a,b]=[5,10])#

  • For (p = 3), the solutions of (x^{2}\equiv1\pmod{3}) are (x_{1}=1) and (x_{2}=2).
  • For (x_{1}=1):
    • (k_{1}=\left\lceil\frac{5 - 1}{3}\right\rceil=\left\lceil\frac{4}{3}\right\rceil = 2)
    • (m_{1}=\left\lfloor\frac{10 - 1}{3}\right\rfloor=\left\lfloor3\right\rfloor = 3)
    • (n_{1}=3 - 2+1=2) (the numbers are (1+2\times3=7) and (1+3\times3 = 10))
  • For (x_{2}=2):
    • (k_{2}=\left\lceil\frac{5 - 2}{3}\right\rceil=\left\lceil1\right\rceil = 1)
    • (m_{2}=\left\lfloor\frac{10 - 2}{3}\right\rfloor=\left\lfloor\frac{8}{3}\right\rfloor = 2)
    • (n_{2}=2 - 1+1=2) (the numbers are (2+1\times3=5) and (2+2\times3 = 8))
  • Total number of solutions (N=2 + 2=4) (the solutions are (5,7,8,10))

Example 2: (p = 2), ([a,b]=[3,5])#

  • For (p = 2), the solution is (x = 1). Since (1\notin[3,5]), the number of solutions is (0)

5. References#

  • Number Theory Textbooks: "An Introduction to the Theory of Numbers" by G.H. Hardy and E.M. Wright provides a comprehensive treatment of congruence equations and prime numbers.
  • Online Resources: Websites like Project Euler and Brilliant.org have problems and discussions related to modular arithmetic and counting solutions of congruences.

This blog has covered the fundamental concepts of solving (x^{2}\equiv1\pmod{p}) and extending it to count solutions in a given range. The methods and examples provided can be used as a starting point for further exploration in number - theoretic problems involving modular congruences.