Solving the congruence ax
2
+bx+c=0 (mod n), gcd(a,n)=1
First solve t
2
b
2
-4ac (mod 4n), -n < t ≤ n.
Note that t
b (mod 2).
Then solve ax
(t-b)/2 (mod n), 0 ≤ x < n.
Enter
a (nonzero):
Enter
b:
Enter
c:
Enter
n (≥ 1 and gcd(a,n)=1):
Last modified 20th January 2005
Return to main page
b2-4ac (mod 4n), -n < t ≤ n. b (mod 2). (t-b)/2 (mod n), 0 ≤ x < n.