Number Theory Home

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*}

Last edited