# Positive integers which cannot be expressed as a difference of squares.

This question comes from Saylor course MA111 which took the question from the 2011 Mathcounts national competition.

How many positive integers less than $2011$ cannot be expressed as the difference of the squares of two positive integers?

Solution given: The answer is $505$. If $n=a^{2}-b^{2}=(a+b)(a-b)$, then $a-b$ and $a+b$ have the same parity, so $n$ is either odd or a multiple of $4$. So we want to count all the numbers of the form $4k+1$, $k=0;1;...;502$ together with two values $2$ and $4$, for a total of $505$.

I understand the issue of parity, but I do not understand why $n$ must be a multiple of $4$ or how integers of the form $4k+1$ satisfy the question. For $k=2$, $4(2)+1=9$ which is equal to $5^{2}-4^{2}$ and therefore doesn't satisfy the question but is counted. How do the integers of the form $4k+1$ satisfy the question?

-
If I'm not mistaken, you write 'cannot be expressed' in the question. On the other hand, the solution counts the number which can be expressed... – mathlove Jan 3 '14 at 12:16

Because $a^{2} \equiv 0$ or $1 \pmod{4}$ for all integers $a$, it follows that $$a^{2} -b^{2} \equiv 0,1,3 \pmod{4}$$ So, if $n \equiv 2 \pmod{4}$, we cannot find $a$ and $b$ such that $n=a^{2} -b^{2}$.
Now, for $n \equiv 1$ or $3 \pmod{4}$, then we have the following identity, $$n=(\frac {n+1}{2})^{2} - (\frac {n-1}{2})^{2}$$ And if $n \equiv 0 \pmod{4}$, then we have $$n=(\frac {n}{4} +1)^{2} - (\frac {n}{4}-1)^{2}$$ So, the given solution is wrong somehow. They should have counted the integers of the form $4k+2$ along with the integers $1$ and $4$, as they want difference of squares of "positive" integers, which is not satisfied with $1$ and $4$ in the given identities and also no two perfect squares of positive integers differ by $1$ or $4$ which can be easily checked by the increasing sequence of squares ${1,4,9,...}$. But the answer is $505$ anyway!