a difficult problem

**silentbob** · June 22nd 2009, 08:29 PM

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

**Swlabr** · June 22nd 2009, 11:27 PM

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.

**TheAbstractionist** · June 23rd 2009, 03:46 AM

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.

**TheAbstractionist** · June 23rd 2009, 04:52 AM

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?

Thread: a difficult problem

LinkBack

Thread Tools

Display

a difficult problem

Similar Math Help Forum Discussions

difficult problem

Difficult problem

a difficult problem

Difficult problem

A very difficult problem for me

Search Tags