Solving the congruence x2 
a (mod m)
This works for m with up to say 20 digits, due to the limitations of the program used to factor m.
Using the Chinese remainder theorem, the problem is reduced to the case of a prime power pn:
- p does not divide a:
- p odd: If a(p-1)/2 1 (mod p), there are two solutions (mod pn).
- p=2:
- n=1: x 1 (mod 2).
- n=2: x ±1 (mod 4), if a=4k+1.
- n>2: two solutions (mod 2n-1) if a=8k+1.
- p divides a:
- pn divides a:
- n=2m+1: x 0 (mod pm+1);
- n=2m: x 0 (mod pm).
- gcd(a,pn)=pr, 0 < r < n:
- r odd: no solution.
- r=2m: let x=pmX, a=p2mA.
- p odd: two solutions (mod pn-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 2n-m-1) if n-2m > 2 and A=8k+1.
Last modified 20th January 2005
Return to main page