LearnMathOnline

In this section we discuss techniques to solve quadratic congruences: \(ax^2+bx+c \equiv 0 \:\left(\mathrm{mod}\: n \right)\). We assume \(a\not\equiv 0 \:\left(\mathrm{mod}\: n \right)\). Otherwise \(ax^2+bx+c \equiv 0 \:\left(\mathrm{mod}\: n \right)\) reduces to the linear congruence \(bx+c \equiv 0 \:\left(\mathrm{mod}\: n \right)\). Note that solving \(ax^2+bx+c \equiv 0 \:\left(\mathrm{mod}\: n \right)\) is equivalent to solving the following system \[ y^2\equiv b^2-4ac \:\left(\mathrm{mod}\: n \right),\; 2ax\equiv y-b \:\left(\mathrm{mod}\: n \right).\]

Case 1. \(\gcd(4a,n)=1\). Then \[ \begin{align*} ax^2+bx+c \equiv 0 \:\left(\mathrm{mod}\: n \right) &\iff 4a(ax^2+bx+c) \equiv 4a\cdot 0 \:\left(\mathrm{mod}\: n\right)\\ &\iff (2ax+b)^2\equiv b^2-4ac \:\left(\mathrm{mod}\: n \right)\\ &\iff y^2\equiv b^2-4ac \:\left(\mathrm{mod}\: n\right),\; 2ax\equiv y-b \:\left(\mathrm{mod}\:n\right). \end{align*}\] Case 2. \(\gcd(4a,n)>1\). Then \(4a=kd\) where \(\gcd(k,n)=1\). Similarly we can show that \[ ax^2+bx+c \equiv 0 \:\left(\mathrm{mod}\:n \right) \iff y^2\equiv b^2-4ac \:\left(\mathrm{mod}\: dn \right),\; 2ax\equiv y-b \:\left(\mathrm{mod}\: dn \right).\]

Because of the above equivalency we concentrate on a quadratic congruence of the form \(x^2 \equiv a \:\left(\mathrm{mod}\: n \right)\) where \(n\) is an odd prime that does not divide \(a\). Note that if \(n\) is an odd prime and \(n\nmid a\), then \(\gcd(4a,n)=1\) and we get the above equivalent system. Also note that if \(n\vert a\), then \(x^2 \equiv a \:\left(\mathrm{mod}\: n \right)\) becomes \(x^2 \equiv 0 \:\left(\mathrm{mod}\: n \right)\) giving a unique solution \(x \equiv 0 \:\left(\mathrm{mod}\: n \right)\).

Example. Let us solve \(x^2+4x+3 \equiv 0 \:\left(\mathrm{mod}\: 5\right)\).

Since \(\gcd(4\cdot 1,5)=1\), it is equivalent to \[ y^2\equiv 4^2-4\cdot 1\cdot 3 \:\left(\mathrm{mod}\: 5\right),\; 2\cdot 1\cdot x\equiv y-4 \:\left(\mathrm{mod}\: 5 \right).\] \(y^2\equiv 4 \:\left(\mathrm{mod}\: 5 \right)\) has two solutions \(y\equiv \pm 2\equiv 2, 3 \:\left(\mathrm{mod}\: 5\right)\). Now for each \(y\), we solve \(2x\equiv y-4 \:\left(\mathrm{mod}\: 5 \right)\). For \(y=2\), \(2x\equiv -4 \:\left(\mathrm{mod}\: 5 \right)\implies x\equiv -2\equiv 3 \:\left(\mathrm{mod}\: 5\right)\). Similarly for \(y=3\), \(2x\equiv -1\equiv 4 \:\left(\mathrm{mod}\: 5 \right) \implies x\equiv 2 \:\left(\mathrm{mod}\: 5\right)\). Thus solutions are \(x\equiv 2,3\:\left(\mathrm{mod}\: 5\right)\).

Proposition. Let \(p\) be an odd prime and \(p\nmid a\). Then \(x^2 \equiv a \:\left(\mathrm{mod}\: p \right)\) has either no solution or exactly two incongruent nonzero solutions of the form \(\pm x_0\).

Proof. If \(x_0\) is a solution (which is obviously nonzero as \(p\nmid a\) ), then so is \(-x_0\equiv p-x_0 \:\left(\mathrm{mod}\: p\right)\). Note that \(x_0\) is incongruent to \(-x_0\) modulo \(p\) because \[ x_0\equiv -x_0 \:\left(\mathrm{mod}\: p \right)\implies 2x_0\equiv 0 \:\left(\mathrm{mod}\:p\right) \implies x_0\equiv 0 \:\left(\mathrm{mod}\: p\right).\] To show there are exactly two incongruent solutions, let \(z\) be a solution. Then \[ \begin{align*} z^2\equiv x_0^2 \equiv a \:\left(\mathrm{mod}\: p \right) &\implies (z+x_0)(z-x_0)=z^2-x_0^2 \equiv 0 \:\left(\mathrm{mod}\:p\right)\\ & \implies p\vert (z+x_0) \text{ or } p\vert (z-x_0)\\ & \implies z\equiv -x_0 \:\left(\mathrm{mod}\: p \right) \text{ or } z\equiv x_0 \:\left(\mathrm{mod}\: p\right). \blacksquare & \end{align*} \]

Quadratic Congruences