The context for this is the following coding problem on Hackerrank. I'm trying to understand why one of their sample inputs (Sample Input 4) has no solution.
After a bit of math, it comes down to showing that for any natural number $D>100$, the following expression cannot be a natural number.
$$\frac{1 + \sqrt{D^2 -D +1}}{2}$$
I have no idea why that is true. I now just want to check if $\sqrt{D^2 -D +1}$ can be an odd integer for some $D$ or prove that it can never be the case. How does one approach this type of problem for a general quadratic expression under the square root?
Since $D$ is a natural number, so is $D^2-D+1$. But $(D-1)^2 = D^2-2D+1$, so $D^2-D+1$ is almost exactly halfway between $(D-1)^2$ and $D^2$. Because square roots of natural numbers other than perfect squares are irrational, the fraction cannot be a natural number.
The foregoing argument only fails for $D = 0$ or $1$, where $D^2-D+1 = 1$ is a perfect square. But it works for all other natural numbers $D > 1$. Can you complete this argument? Hint. Show that for $D > 1$, $D^2-D+1$ is strictly between $(D-1)^2$ and $D^2$.