<s>[INST] Can $pk+1$ divide $(p-k)^2$? Let $p>3$ be a prime, $0<k<p$. Then is it possible that $pk+1\mid(p-k)^2$?
For $k=1$, since $(p-1)^2\equiv(-2)^2\equiv4\pmod{p+1}$, and $p>3$, this is not possible.
And if $pk+1\mid(p-k)^2$ then $k^2-3pk+p^2-1\geq0$, so $k\leq\frac{3p-\sqrt{5p^2+4}}2$.

This arises from another question. I am running out of ideas, so any help is sincerely appreciated, thanks in advance.
 [/INST] Suppose that $p$ and $k$ are integers such that $p>k>0$ and $$n=\frac{(p-k)^2}{pk+1}$$
for some integer $n>0$.  Note that $(x,y)=(p,k)$ is a solution to the quadratic equation
$$x^2+y^2-(n+2)xy=n.\tag{1}$$
Let $(x,y)=(a,b)$ be a solution to (1) such that $a>b>0$ and $a+b$ takes the smallest possible value.  We claim that $n=b^2$.
Observe that $$(x,y)=\big(b,(n+2)b-a\big)=\left(b,\frac{b^2-n}{a}\right)\tag{2}$$
is an integer solution to (1), but not necessarily positive.  If $b^2>n$, then we see that (2) gives an integer solution in which
$$b>\frac{b^2-n}{a}>0\text{ and }b+\frac{b^2-n}{a}<a+b.$$
This contradicts the assumption that $a+b$ is minimum.  Hence, $b^2\leq n$.
If $b^2<n$, then observe that 
$$(x,y)=\left(\frac{b^2-n}{a},\frac{b^2-n}{a}(n+2)-b\right)=\left(\frac{b^2-n}{a},\frac{\left(\frac{b^2-n}{a}\right)^2-n}{b}\right)$$
is another integer solution to (1), with both numbers being negative.  Since (1) is invariant under the assignment $(x,y)\mapsto (-y,-x)$, we see that
$$(x,y)=\left(\frac{n-b^2}{a}(n+2)+b,\frac{n-b^2}{a}\right)$$
is a positive integer solution with
$$\frac{n-b^2}{a}(n+2)+b>\frac{n-b^2}{a}>0.$$
By minimality of $a+b$, we must have
$$\left(\frac{n-b^2}{a}(n+2)+b\right)+\frac{n-b^2}{a}\geq a+b.$$
Hence,
$$n(n+3)\geq a^2+(n+3)b^2.$$
Recall from (2) that
$$(n+2)b-a=\frac{b^2-a}{n}<0.$$
That is, $a>(n+2)b$ and we get
$$\begin{align}n(n+3)&\geq a^2+(n+3)b^2>(n+2)^2b^2+(n+3)b^2\\&\geq (n+2)^2+(n+3)=n(n+3)+(2n+7)>n(n+3).\end{align}$$
This is a contradiction, so $n=b^2$ is the only possibility.
With $n=b^2$, (2) becomes $(x,y)=\big(b,(b^2+2)b-a\big)=(b,0)$, so
$$a=b(b^2+2).$$
Note also that
$$(x,y)=\big((b^2+2)p-k,p\big)=\left(\frac{p^2-n}{k},p\right)$$
is also an integer solution to (1) satisfying $x>y>0$, provided that $(x,y)=(p,k)$ is a solution to (1) with $p>k>0$.  Indeed, we can see that all integer solutions $(x,y)=(p,k)$ with $n=b^2$  satisfying $p>k>0$ are given by
$$(p,k)=(t_{j+1},t_j)$$
for some positive integer $t_j$.  Here, we define $t_0=0$, $t_1=b$, and
$$t_j=(b^2+2)t_{j-1}-t_{j-2}$$
for $j\geq 2$.  Note that $t_j$ is divisible by $b$ at all $j$.  Since $t_j>b$ for $j>1$, we conclude that $p$ is not prime when $b>1$.  
For $b=1$, however, $t_j=F_{2j}$ (where $\left(F_m\right)$ is the Fibonacci sequence).  Since $F_j$ divides $F_{2j}$ for all $j$ and $F_j>1$ for $j>2$, we conclude that $p$ is prime only when $p=F_4=3$.
</s>