On the Quadratic Formula Modulo N

Abstract

Let $a,b,c,$ and $n$ be integers, with $a$ nonzero and $n$ at least two. Necessary and sufficient conditions on these parameters are derived which guarantee that all solutions of the congruence \[ ax^2+bx+c \equiv 0\ \textrm{mod}\ n \] are given precisely by the solutions of \[ 2ax\equiv -b+s \ \textrm{mod}\ n, \] where $s$ varies over all solutions of \[ x^2\equiv b^2-4ac \ \textrm{mod}\ n. \] Corollaries of this result are deduced for prime-power moduli and some illustrative examples are also presented.

arXiv comment25 pages, one table