Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this 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
up vote 0 down vote accepted

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!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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