All the variables I deal with are integers. Given $q \geq 2, |k| \geq 2$, impose a constraints that we have an integer $p$ such that $q^2=1+pk=1\pmod k.$ For example, $3^2=1+1\cdot8, 5^2=1+3\cdot8.$ Now

I suspect that given the triple $(q,k,p)$, then at least one of the following is true.

(1) there is a shift integer $u$ such that $(q+ku)^2=1+p_1k$ where $p_1$ is a square

(2) there is a shift integer $u$ such that $(-q+ku)^2=1+p_1k$ where $p_1$ is a square.

For example, given $q=5, k=8, p=3$. I can find $u=1$ so that the second case $-q+ku=-5+8(1)=3$ and then $3^2=1+8\cdot1$ now $1$ is a square. Notice that if original $p$ is a square then we are done or $k=\pm 1$.

I try to prove this is true. But I somehow fail. **Here is my attempt:** My process follows like this, suppose now $p$ is not square and I want to solve $(q+ku)^2=1+p_1k.$ Now I can $q^2+2kuq+k^2u^2=1+pk+2kuq+k^2u^2=1+p_1 k.$ I get the following Diophantine equation:

$p+2uq+ku^2=p_1=\theta^2.$ Now I want to solve $u$ in order to let $u$ be an integer, I must have the discriminant of a quadratic equation $u$ to be a perfect square. So I must have

$4q^2-4k(p-\theta^2)=4\phi^2$ for some integer $\phi.$ So know I can plug $q^2=1+pk$ then I can get the following Pell's equation.

$1+k\theta^2=\phi^2.$ Due to the theory of Pell's equation, if $k$ is not a perfect square, then there will be infinite solutions. But in order for $u$ to be an integer. I have $u=\frac{-q \pm \phi}{k}.$ I will need to further require that $\phi-q$ or $\phi+q$ must be divisible by $k$ which I am not sure how to proceed. I guess since there are infinite solutions, so it would be ok or due to some quadratic residue issue. I can not find the answer. Bu t I believe if (1) can not satisfied and then we can do for $-q$ then one can always make another true.

Due to some reason, I only need either (1) or (2) is true if one of them can not be satisfied. Any comments are very welcome. Thanks a lot.