To show that there are $3$ numbers between $n^2$ and $(n+1) ^2$ such that they satisfy a certain property. Here is the problem

Show that for any natural number $n$, one can find three distinct
natural numbers $a, b, c$ between $n^2$ and $(n + 1)^2$ such that $a^2 + b^2$ is divisible
by $c$.

It seems like here are several ways to express $a^2 + b^2$.
\begin{array}
 aa^2 + b^2 &= (a - b) ^2 +  2ab \\
 &= (a + b) ^2 - 2ab \\
 &= \frac { (a + b) ^2 + (a - b)^2 }{2} \\
 &= 2b^2 + (a + b)(a - b)
\end{array}
What the problem is literally saying: Find algebraic expressions $X,Y$ and $Z$ such that $n^2 \lt X,Y,Z \lt(n + 1)^2$ and $Y^2 + Z^2 = AX$, for some expression $A$. (Hence, $X|Y^2 + Z^2$)
In the original problem, $X$ is $c$, $Y$ and $Z$ are $b$ and $a$.
People with enough experience might know the answer at once, but is it possible to actually find the expressions from identities/relations? For example the relations that I have found above?
From my trying it is very difficult because one needs to search for expression that are restricted between $n^2$ and $(n + 1)^2$, and then the factoring. What I tried was just plugging random expressions to $Y$ and $Z$ and trying to find a suitable $X$ that suffices the factoring, but to no avail.
Please help, and thanks for that!
 A: (Note: In the fixed olympiad question, $n\geq 2$, and $ n^2 < a , b, c < (n+1)^2$.)
There's a bunch of wishful thinking in solving this problem, which is a good healthy approach to take esp when solving Olympiad problems which typically have a "nice solution" but we have no idea what it is (IE "My problem is that how to find them" from the comments).
I've indicated this via "reasonable to assume". Of course, if things don't work out, then we have to revisit these "assumptions".
For $n=2$, the only solutions are $(6,7,5)$ and $(6,8,5)$.
For $n=3$, the only solutions are $(11,13,10)$, $(12,14,10)$, $(10, 11, 13)$, $(10, 15, 13)$.
At the point, it is reasonable to assume that we must have $c = n^2 + 1$. I like this assumption because it focuses what I'm investigating. We can reconsider what happens if this doesn't turn out to be true.
For $n=4, c = 17$, the only solutions are $(18, 21, 17)$ and $(20, 22, 17)$.
It is reasonable to assume that we have (a/several) family of solutions, and so let's see how we can split them.

*

*It is reasonable to assume that the "smaller solution" $(6,7,5) \sim (11,13,10) \sim (18, 21, 17)$ is a family, which we can observe is $ (n^2 + 2, n^2+n+1, n^2 + 1)$.

*It is likewise reasonable to assume that the "larger solution"  $(6,8,5) \sim (12, 14, 10) \sim (20, 22, 17)$ is a family, which we can observe is $(n^2 + n, n^2 + n + 2, n^2 + 1)$.

Finally, we verify that these families actually work.

Notes

*

*Looking at the other solutions for $n=3$, it might be reasonable to assume that we have solutions for $c = n^2 + n + 1$ when $n \geq 3$. However, checking $n =4, 5 $ doesn't yield such a solution. This is a good example of where wishful thinking doesn't work out, and so we have to change something else.

*In fact, for $n = 4$, the only solutions are those that we found. So if we didn't initially jump to the reasonable assumption that $c = n^2 +1$ after $n=3$, then we almost certainly should have after checking $n=4$
A: There is in fact another way to do this:

Thm 1: Let $N$ be a sufficiently large integer. Then between $N$ and
$N +\lceil 2\sqrt{N} \rceil$ there are 3 integers $A$, $B$, $C$ such that
$C|(A^2+B^2)$.

To prove Thm 1, we make the following claim:

Claim 2: For each $M$ and $k$, the equation $(M-k)^2 \equiv_k (M+k)^2 \equiv_M k^2$.

We now finish the proof of Thm 1: So let $k_1,k_2$ be distinct positive integers both no larger than $\sqrt{N}$ such that $N+\sqrt{N} > k_1^2+k^2_2 > N$, picking
$k_1=\lfloor \sqrt{N} \rfloor$ and $k_2 = O(N^{1/4})$ should work.
Then let $C=k^2_1+k^2_2$, and then let $A=C+k_1$ and $B=C+k_2$. Then $A,B,C$ satisfy the conditions of Thm 1. $\surd$
