1. ## a difficult problem

Find all solutions of the congruence x^2 + 6x − 31 = 0 (mod 72).

2. Originally Posted by silentbob
Find all solutions of the congruence x^2 + 6x − 31 = 0 (mod 72).
Getting rid of the modulo then solving as per usual works, although not all of my answers are whole numbers.

3. Originally Posted by silentbob
Find all solutions of the congruence x^2 + 6x − 31 = 0 (mod 72).
Complete the square and solve a congruence of the form $X^2\equiv K\,(\bmod\,72).$

This is standard method for solving general quadratic congruences, as found in any good number-theory textbook.

4. Okay, I’ve tried the problem myself and found that it’s not very straightforward (I believe it’s because the modulus is not a prime). Here’s my solution.

$x^2 + 6x - 31 \equiv 0\,(\bmod\,72)$

$x^2 + 6x + 9 \equiv 40\,(\bmod\,72)$

$(x+3)^2 \equiv 40\,(\bmod\,72)$

$X^2 \equiv 40\,(\bmod\,72)$

where $X=x+3.$ It is clear that $X$ must be even so let $X=2Y.$

$4Y^2 \equiv 40\,(\bmod\,72)$

$Y^2 \equiv 10\,(\bmod\,18)$

Again we see that $Y$ must be even, say $Y=2Z.$

$4Z^2 \equiv 10\,(\bmod\,18)$

$2Z^2 \equiv 5\,(\bmod\,9)$

$2Z^2 \equiv 14\,(\bmod\,9)\quad(\because\ 5\equiv14\,(\bmod\,9))$

$Z^2 \equiv 7\,(\bmod\,9)\quad(\because\ \gcd(2,9)=1)$

Trying $1^2,\,2^2,\,3^2,\,\ldots,\,8^2$ in turn, we find that $Z=4,\,5$ are the only solutions between 1 and 8. Hence the general solution is

$Z\,=\,4+9n,\,5+9n$

$\implies\ Y\,=\,2Z\,=\,8+18n,\,10+18n$

$\implies\ X\,=\,2Y\,=\,16+36n,\,20+36n$

$\implies\ X-3\,=\,\fbox{x\,=\,13+36n,\,17+36n}$

Maybe someone has a neater solution?