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?

  • $\begingroup$ 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... $\endgroup$ – 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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.