Finding solutions to $h(j)=15+j^2 \mod 17, j \in \mathbb{N}$

Question

I have a function such as this: $$h(j)=15+j^2 \mod 17, j \in \mathbb{N}$$

When $h(j)=7$ I know that there is a solution to this as: $h(3)=15+(3)^2 \mod{17}=7$

How can I prove that there no solutions to this for $h(j)=4$?

Answer 1

If $h(j)=4$, then this means \begin{align*} 15+j^2 & \equiv 4 \pmod{17}\\ j^2 & \equiv 6 \pmod{17} \end{align*} But if you consider the squares mod $17$ you get $\{0^2,1^2,2^2, \ldots , 8^2\}=\{0,1,4,9,16,8,2,15,13\}$. This means $6$ has no square root hence the equation has no solution.

Answer 2

$h(j) = 4\to 15+j^2 = 4\pmod {17} \to 15+j^2-4 = 17k \to 11+j^2=17k$. Best way is the check case by case $11+1^2, 11+2^2,\cdots , 11+16^2 \pmod {17}$, and find out yourself that none of them is $0\pmod {17}$

Answer 3

We have $$ h(j)=4\iff j^2\equiv4-15\equiv17-11=6\pmod{17} $$ Using the Jacobi Symbol and its properties we then have $$ \begin{align} \left(\frac{6}{17}\right)&=\left(\frac{2}{17}\right)\left(\frac{3}{17}\right)\\ &=\left(\frac{3}{17}\right)\\ &=\left(\frac{17}{3}\right)\\ &=\left(\frac{2}{3}\right)\\ &=-1 \end{align} $$ telling that $6$ is a quadratic non-residue modulo $17$. So no solution exists.

---

Here is a summary of the properties, I have used above:

1. If $n$ is odd and $a\equiv b\pmod n$, then $$\left(\frac{a}{n}\right)=\left(\frac{b}{n}\right)$$
2. If $n$ is odd, then $$\left(\frac{2}{n}\right)=\begin{cases}1&\quad\text{if }n\equiv\pm1\pmod8\\-1&\quad\text{if }n\equiv\pm3\pmod8\end{cases}$$
3. If $n$ is odd and $a=2^kb$, then $$\left(\frac{a}{n}\right)=\left(\frac{2}{n}\right)^k\left(\frac{b}{n}\right)$$
4. If $a,n$ are odd, then $$\left(\frac{a}{n}\right)=\begin{cases}-\left(\frac{n}{a}\right)&\quad\text{if }a\equiv n\equiv3\pmod4\\\left(\frac{n}{a}\right)&\quad\text{otherwise}\end{cases}$$

Answer 4

Hint $\,\ {\rm mod}\ 17\!:\,\ j^{\,\large 2}\equiv 6\,\overset{\Large (\ \ )^{8}\!\!}\Rightarrow 1\equiv j^{\,\large 16}\equiv 6^{\large 8} \equiv 2^{\large 4}\,\Rightarrow\!\Leftarrow$