Determine whether $x^2 - 14x + 30 \equiv 0$ mod 1615 is solvable. If so, find its solutions...

Question

Determine whether $x^2 - 14x + 30 \equiv 0\pmod{1615}$ is solvable. If so, find its solutions.

I assume the best way to solve this is via Chinese Remainder Theorem, but first i would have to break down the mod and if there is a solution then utilize C.R.T. No quite sure how to attack this with the right numbers, any hints/help are very appreciated.

Answer 1

As the comments note, we can complete the square to get $$(x-7)^2\equiv 19\pmod{1615}$$ by applying the Quadratic Reciprocity Theorem we see that $$(19|1615)=(19|5)(19|17)(19|19)=(4|5)(2|17)(0|19)$$ where $(p|q)$ is the Jacobi Symbol. Notice that this actually gives $(19|1615)=0$ since $19|1615$. The other two factors give $1$, as $2^2\equiv 4\pmod{5}$ and $6^2\equiv 2\pmod{17}$

Since all of the Jacobi symbols come out to $0$ or $1$, we know a solution exist. To find it, we will need to apply the Chinese Remainder Theorem however, as Quadratic Reciprocity is non-constructive.

Answer 2

$y^2-14y+30=y^2-14y+49-19 = (y-7)^2-19$. So the congruence is now $(y-7)^2 \equiv 19 \mod 1615$. However, $1615$ is actually a multiple of $19$, whence we split it into congruences via CRT, $1615=19*17*5$. Call $x=y-7$ (just a shift of number, we can change it back later), then:

$x^2 \equiv 19 \mod 19$

$x^2 \equiv 19(=2) \mod 17$

$x^2 \equiv 19(=4) \mod 5$

Need simultaneous solving. Each of these can be solved, and the solutions are:

$x \equiv 0 \mod 19$

$x \equiv \pm 6 \mod 17$

$x \equiv \pm 2 \mod 5$

Now that we have these congruences, we combine them using the Chinese remainder theorem: The second two combine to give $x \equiv 23/28/57/62 \mod 85$. Note that $57$ already divides $19$, but the rest need to be augmented with a suitable multiple of $19$ to work. That requires little bit of hard work, and I can show the results here: $x \equiv \pm 57, \pm 703 \mod 1615$. To verify:

$57^2-19 = 3230=2*1615$

$703^2-19=494190=306*1615$

Of course, we have to put back the resulting $7$ shift we made earlier, and the results are:

$y=64/710/819/1565$. These are all right.

Answer 3

You want to find possible integer x's where:

$x^2 - 14x + 30 = 1615k$, where k is some integer. Our equation becomeS:

$x^2 - 14x + 30-1615k = 0$

Using our quadratic formula, we can put values of x at:

$\Large\frac{14 \pm \sqrt{196 - 4(30 - 1615k)}}{2} $

Simplifying by dividing by the 2, we get:

$7 \pm \sqrt{49 -30 + 1615k} = 7 \pm \sqrt{19 + 1615k}$

So now for x to be an integer, $\sqrt{19 + 1615k}$ has to be a perfect square.

Factors of 1615 are 1, 5, 17, 19, 323 (5 was obvious and 19 made sense :) )

So $\sqrt{19 (1 + 85k)}$ must be a perfect square

Which means $85k + 1$ should have an odd number of 19's in it, and the rest of the factors should appear even times.

I see that $85 \equiv{-10} \mod{19}$,

so $85*2 \equiv{-20} \text{ or} -1 \mod{19}$

So k = 2 works, as 85*2 + 1 = 171 = 19*9, making 19*9*19 a perfect square.

So at least two solutions exist, putting k = 2 in $7 \pm \sqrt{19 + 1615k}$

We get $7 \pm 57$, so $x = -50$ and $x = 64$ are at least 2 solutions

Answer 4

$$x^2-14x+30\equiv 0\pmod{5\cdot 17\cdot 19}$$

$$\iff (x-7)^2\equiv 19\pmod{5\cdot 17\cdot 19}$$

$$\iff \begin{cases}(x-7)^2\equiv 19\equiv 2^2\pmod{5}\\(x-7)^2\equiv 19\equiv 6^2\pmod{17}\\(x-7)^2\equiv 19\equiv 0^2\pmod{19}\end{cases}$$

$$\iff \begin{cases}x-7\equiv \pm 2\pmod{5}\\x-7\equiv \pm 6\pmod{17}\\x-7\equiv 0\pmod{19}\end{cases}$$

I used the fact that $5,17,19$ are prime and Euclid's Lemma: e.g., if $5\mid (x-7)^2-2^2=((x-7)+2)((x-7)-2)$, then $x-7\equiv \pm 2\pmod{5}$.

Now use Chinese Remainder Theorem to find all the $4$ solutions.