This is equivalent to proving that there exists $ n$ such that $ \left( \frac{n(n+k)}{p} \right) = 1$, which is equivalent to showing the existence of a point on the curve $ x(x + k) = y^2$. Completing the square gives $ (x + k)^2 = y^2 + k^2$ and now it's enough to observe that we can find $ m, n$ such that $ k \equiv 2mn \bmod p$ for any odd prime $ p$. The result is obvious for $ p = 2$.

t0rajir0u wrote: ... $ x(x + k) = y^2$. ... $ (x + k)^2 = y^2 + k^2$ Are the two equivalent? Or were they not meant to be?

My apologies. For $ p$ odd, $ \frac{1}{2}$ exists $ \bmod p$ so we can write $ k' = \frac{k}{2}$ and $ (x + k')^2 = y^2 + k'^2$.

If $p|k$ then just take $n=p$ , now consider two sets $A,B$ such as $(\frac{n}{p})=1\implies n\in\ A$ otherwise $n\in\ B$. Now we've condition that $a,b\in\ A\implies ab\in\ A$ and $a,b\in\ B\implies ab\in\ B$ also $a\in\ A,b\in\ B \implies ab\in\ B$ and call this operation as $T$. Now assume that there doesn't exist such a $n$ at all. Now if $n+k \in\ P$ and so $n+(2x+1)k \in\ P$ also $n+2xk \in\ Q$ where $\{P,Q\}=\{A,B\}$. First if $P=A,Q=B$ then taking $n=k$ applying $T$ we get $P\cap Q \neq \phi$ otherwise taking $n=k-1$ again applying $T$ we get $P\cap Q \neq \phi$ but it's absurd, other case is similar, so we arrived at a contraction and so done.

Another proof:for odd $p$ not equal to $3$ and any $k$ there exist some $n$ such that $3n=k(mod p)$.So such $n$ exists $(\frac{n}{p})=(\frac{4n}{p})$.For $p=2,3$ we can count with hands.

very nice proof @hal9v4ik

There exists $a,b\in\mathbb{N}$ such that $ k \equiv a^2 -b^2 \ (\textrm{mod}\ p)$ $n=b^2$ complete the proof.

There is a slight theoretical issue here. Originally, Legendre defined $\genfrac {(} {)} {} {} {a} {p} \equiv a^{\dfrac {p-1}{2}} \pmod{p}$, for odd primes $p$ only. According to that, and to other approaches, $\genfrac {(} {)} {} {} {a} {p} = 0$ when $p\mid a$. If we extend the symbol to $p=2$ by $\genfrac {(} {)} {} {} {a} {2} = 1$ for $a$ odd and $\genfrac {(} {)} {} {} {a} {2} = 0$ for $a$ even, then the problem fails for $p=2$ and $k$ odd, since then, for any $n$, the numbers $n$ and $n+k$ are of different parity. For the same reason, the problem also fails for $p=3$ when $3\nmid k$. Likely, for the problem setters, since indeed $0$ is a (trivial) quadratic residue, they assumed $\genfrac {(} {)} {} {} {0} {p} = 1$, which for most authorities is wrong. So let us work with primes $p>3$ only. The idea of the post above needs clarification in its claim. Now $2$ is inversible modulo $p$. Let us take $a\equiv \dfrac {k+1}{2} \pmod{p}$ and $b\equiv \dfrac {k-1}{2} \pmod{p}$; then indeed $a^2-b^2 \equiv k \pmod{p}$. Taking $n=b^2$ we have $n+k \equiv a^2 \pmod{p}$, and so we achieve $\genfrac {(} {)} {} {} {n} {p} = 1 = \genfrac {(} {)} {} {} {n+k} {p}$, thus even more than what was asked, but that only if $p\nmid a$ and $p\nmid b$. But we cannot always avoid $p\mid a$ or $p\mid b$ if we look for $a^2-b^2 \equiv k \pmod{p}$, for example for $k=1$ and $p=5$. Therefore for $k\equiv \pm 1 \pmod{p}$ it is generally false that we can find $n$ such that $\genfrac {(} {)} {} {} {n} {p} = 1 = \genfrac {(} {)} {} {} {n+k} {p}$, so we must go back to the original requirement, and only hope for $\genfrac {(} {)} {} {} {n} {p} = \genfrac {(} {)} {} {} {n+k} {p}$, unless told to consider $\genfrac {(} {)} {} {} {0} {p} = 1$. But now hal9v4ik's idea works. Finding $3n\equiv k \pmod{p}$ makes $n+k\equiv 4n \pmod{p}$, and so $\genfrac {(} {)} {} {} {n} {p} = \genfrac {(} {)} {} {} {2^2n} {p} = \genfrac {(} {)} {} {} {n+k} {p}$ (but not necessarily of value $+1$). Addendum. The case $p=5$ is special (as already hinted at in the above). For $k\not \equiv \pm 1 \pmod{p}$ we can find $n$ such that both Legendre symbols are $+1$, as above. For $k\equiv \pm 1 \pmod{p}$ we cannot find two consecutive not-null quadratic residues, so we are left with taking $n=2$ when $k\equiv 1 \pmod{p}$, and $n=3$ when $k\equiv -1 \pmod{p}$, and thus get both Legendre symbols equal to $-1$. For $p>5$ we can however do more. Since at least one of $\{2,5,10\}$ must be a not-null quadratic residue (if $2$ and $5$ are not, then $10=2\cdot 5$ must be), and since $2=1^2+1, 5=2^2+1, 10=3^2+1$, we can actually find two consecutive not-null quadratic residues, and by this strengthen the claim of the problem.

Another solution by inspecting $p\pmod{8}$. Let $p>3$. If $p\equiv \pm 1\pmod{8}$, simply let $n=k$, as $2$ is a quadratic residue modulo $p$. If not, then start with the case $p\equiv 3\pmod{8}$. In this case, $-1$ is not a quadratic residue, and $-2$ is a quadratic residue. If $p\equiv 1\pmod{6}$ then $-3$ is a quadratic residue modulo $p$ too, so $n=-3k$ works. If $p\equiv 5\pmod{6}$, then $-3$ is not a quadratic residue, and thus, $3$ is a quadratic residue. In this case, $n=3k$ works. Now let $p\equiv 5\pmod{8}$. Similar to above, $-1$ is a quadratic residue, and $-2,2$ are not. Now if $p\equiv 1\pmod{6}$ then $-3$ is a quadratic residue as well, and thus, so do $3$. Hence, $n=3k$ works. If $p\equiv 5\pmod{6}$, then neither $-3$ nor $-2$ are quadratic residues modulo $p$, thus, $n=-3k$ works.