How to solve $x^2+3x+17\equiv 0\pmod{315}$?

Question

I’m trying to do this question, and I have no clue how to get started, I first tried to factor $315$ as $3^2, 5$ and $7$ and solve three sets of congruency but I again got stuck with the smaller cases, please help me with this $$x^2+3x+17\equiv 0\pmod{315}$$

Answer 1

If you don't want to "try all of them" as N.S. suggests, you can do it this way. The quadratic formula applied to $x^2 + 3x + 17 = 0$ yields $$ x = \dfrac{-3 \pm \sqrt{-59}}{2}$$ This will actually work modulo any odd number (it needs to be odd because you can't divide by $2$ modulo an even number): if $-59$ is a square mod $n$, it will give you solutions mod $n$ (i.e. if $y^2 \equiv -59 \mod n$, $x \equiv 2^{-1} (-3 + y)$ will be a solution mod $n$), and if $-59$ is not a square mod $n$ there will be no solutions.

$-59 \equiv 1 \mod 5$. That's a square, and the square roots of $1$ mod $5$ are $1$ and $4$. So $y \equiv 1$ or $4 \mod 5$, and correspondingly $x \equiv 2^{-1}(-3 + 1) \equiv 4$ or $3 \mod 5$.

$-59 \equiv 4 \mod 7$. The square roots of $4$ mod $7$ are $2$ and $5$. So $y \equiv 2$ or $5 \mod 7$, and correspondingly $x \equiv 3$ or $1 \mod 7$.

$-59 \equiv 4 \mod 9$. The square roots of $4$ mod $9$ are $2$ and $7$. So $y \equiv 2$ or $7 \mod 9$, and correspondingly $x \equiv 4$ or $2 \mod 9$.

Finally, use the Chinese Remainder Theorem with your choice of the possibilities mod $5$, mod $7$ and mod $9$.

Answer 2

Hint $$x^2+3x+17\equiv 0\pmod{5,7,9}$$ can only have $5,7$ or $9$ solutions. Try all of them.

Alternately: $$x^2+3x+17\equiv 0\pmod{315} \Leftrightarrow \\ 4x^2+12x+68 \equiv 0\pmod{315} \Leftrightarrow \\ (2x+3)^2 \equiv 256=16^2 \pmod{315}$$

You can immediatelly see that $16,-16$ are square roots of $256$, which immediately tells you that there are at least 2 solutions. Since $3,5,7$ do not divide $256$ it is easy to deduce that there must be 8 solutions, you just need to find the rest.

Answer 3

It's convenient to rewrite it first as $4x^2+12x+68\equiv0$ mod $315$, and then as

$$u^2\equiv-59\mod315$$

with $u=2x+3$. Since $-59\equiv1$ mod $5$ and $4$ mod both $7$ and $9$, we have $u\equiv\pm1$ mod $5$ and $u\equiv\pm2$ mod $7$ and mod $9$. At this point, the Chinese Remainder Theorem can be applied systematically to find the eight different values for $u$ mod $315$. But with numbers this small, it's just as easy to find the values by playing around with combinations (and, maybe, getting lucky). Here's what I mean:

By looking at numbers of the form $63k\pm2$, we easily see $u=\pm61$ as one solution and $u=\pm191$ as another (i.e., $61\equiv191\equiv1$ mod $5$). This already gives us four out of the eight solutions mod $315$. To find the other four, we might notice that the relatively small number $16$ fits the bill, so $u\equiv\pm16$ is a solution. Test-adding $63$ gives us $u\equiv\pm79$ as another. In total, we have solutions

$$2x+3\equiv \begin{cases} \pm61\\ \pm191\\ \pm331\\ \pm79\\ \end{cases}\mod315$$

where we've rewritten $16$ as $16+315=331$, for reasons that will soon be apparent. From this we get

$$2x\equiv \begin{cases} 58\\ -64\\ 188\\ -194\\ 328\\ -334\\ 76\\ -82 \end{cases}\mod315$$

and finally, since the numbers were all "engineered" to be even,

$$x\equiv \begin{cases} 29\\ -32\\ 94\\ -97\\ 164\\ -167\\ 38\\ -41 \end{cases}\mod315$$

If you like, you can make all the values positive by adding $315$ to the ones that are negative, and you can sort them in ascending order to get the set $\{29,38,94,148,164,218,274,283\}$.

The takehome message is that the theory and a small amount of computation will tell you how many solutions to expect, but to find the solutions explicitly, you have to be willing to do the extra work that's called for. There are systematic algorithms that'll let you plow through to an answer, but when the numbers involved are reasonably small you can sometimes organize things to get by with a modest amount of trial and error.

Answer 4

It probably easiest to rely on the Chinese Remainder Ther and solve in $\mod 5,\mod 7$, and $\mod 9$ first.

But in general we can solve using the quadratic formula just like "regular arithmetic" provided you have very careful not to abuse concept.

$x^2+3x + 17\equiv 0 \pmod {315}$ would mean

$x \equiv \frac {-3\pm \sqrt{9-4*17}}2 \pmod {315}$

!!!IF!!! we can assume the following:

1) There is a number we can refer to as "$\frac 12$" which is not the fraction $\frac 12$ but a residue class of an integer $a$ so that $2a \equiv 1 \pmod{315}$. Such an integer exists if and only if $\gcd(2,315)=1$. Which is does so we can.

2) There is an residue class of an integer $b$ so that $b^2 \equiv 9-4*17\equiv -59\equiv 256\pmod {315}$. Now we must be careful as there may be many such $b$ and not just $2$.

1) is fine we have $\gcd(315,2)=1$ and solving for $2a\equiv 1\pmod {315}$ is just a matter of noting $1 \equiv 316 =2*158$ so $"\frac 12" \equiv 158\pmod{315}$.

2) if $b^2 \equiv 256 \pmod {315}$ then $b^2 - 256=(b-160)(b+16)\equiv 0 \pmod{315}$ and $315|(b-16)(b+16)$ which work for a variety cases. $b\equiv 16$ or $b\equiv -16$ are obvious. but we could also have $k|b-16$ and $\frac {315}k|b+16$...

So we have $x \equiv \frac {-3+b}2 \pmod {315}$ where $b$ is such that $315|(b-16)(b+16)$. (and if $-3+b$ is odd we have $x \equiv \frac {-3+b-315}2$.

Bearing in mind $\gcd(b-16,b+16)=\gcd(2b, b+16)=\gcd(32,b+16)$ is a power of $2$ so

our solutions for $b$ are

$315|b\pm 16$ and $b\equiv \pm 16$ and so x \equiv \frac {13}2; \frac {-19}2\equiv 6+158; -9-158\equiv 164; -167$.

$5|b\pm 16; 63|b\mp 16$.

If $5|b+16$ then $b\equiv 4 \pmod 5$ and $63|b-16$ so $b\equiv 16\pmod {63}$ and so $b\equiv 79\pmod{63,5} and $b\equiv 79$ and $x\equiv \frac {76}2\equiv 38$.

if $5|b-16$ then $b\equiv 1\pmod 5$ and $b\equiv -16\equiv 47\pmod {63}$. And $47 + 3*63$ will have final digit of $6$ so $b\equiv 236\equiv -79\pmod{315}\equiv $ and so $x\equiv \frac {-82}2\equiv -41$.

Or $7|b\pm 16$ and $45|b\mp 16$.

so $b\equiv 16\equiv 2\pmod 7$ and $b\equiv -16\equiv 29\pmod {45}$

Need $29 + 45k = 2+7m$ so $(28-1) +(3+6*7)k = 7m$ so $-1 + 3k=7(m-6k-4)$. If we let $k=-2$ and $m-6k-4=m+8=-1$ or $m =-9$ and $b\equiv -61$

so $x \equiv -\frac {64}2\equiv 32$

or $b\equiv -16\equiv 5\pmod 7$ and $b \equiv 16\pmod {45}$

Need $16+45k = 5+7m$ so $11 + 45k = 7m$ so $4+(42+3)k=7(m-1)$ or $4+3k=7(m-1-6k)$ so $k=1$ and $m-1-6k=m-7=1$ so $m=8$ and $b \equiv 61\pmod{315}$.

so $x\equiv 29$.

And if $9|b\pm 16$ and $35|b\mp 16$.

If $b\equiv 16\equiv 7\pmod 9$ and $b\equiv -16\equiv 19\pmod {35}$

then $7+9k = 19+35m$ or $9k = 12+35m$ or $9(k-1-4m)=3-m$ so let $m=-6$ and $k-1+24 = 1$ so $k=-22$ and $b\equiv -191$

$x \equiv -\frac {194}2 \equiv -97$.

And if $b\equiv -16\equiv 2\pmod 9$ and $b\equiv 16\pmod {35}$ we'd have

$2+9k = 16+35m$ so $9k = 14+35m$ so 9(k-1-4m)= 5-m$ so $m=-4$ and $b\equiv -124\equiv 191$ so $x \equiv 94$

so the eight solutions are $x \equiv 164,-167, 38,-41,32,29,-97,94$