Solving the quadratic congruence x² ≡ a (mod m)

• p does not divide a:
  • p odd: If a^(p-1)/2 ≡ 1 (mod p), there are two solutions (mod pⁿ).
  • p=2:
    • n=1: x ≡ 1 (mod 2);
    • n=2: x ≡ ±1 (mod 4), if a=4k+1;
    • n>2: two solutions (mod 2^n-1) if a=8k+1.
• p divides a:
  • pⁿ divides a:
    • n=2m+1: x ≡ 0 (mod p^m+1);
    • n=2m: x ≡ 0 (mod p^m).
  • gcd(a,pⁿ)=p^r, 0 < r < n:
    • r odd: no solution.
    • r=2m: let x=p^mX, a=p^2mA.
      • p odd: two solutions (mod p^n-m).
      • p=2:
        • 1 solution (mod 2) if n-2m=1;
        • 2 solutions (mod 4) if n-2m=2 and A=4k+1;
        • 2 solutions (mod 2^n-m-1) if n-2m > 2 and A=8k+1.

Last modified 25th February 2012
Return to main page