Determine whether $x^2 - 14x + 30 \equiv 0$ mod 1615 is solvable. If so, find its solutions... 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.
 A: $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.
A: $$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.
A: 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.
A: 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
