1997 AIME Problem 1

Question

How many of the integers between

1

and

1000,

inclusive, can be expressed as the difference of the squares of two nonnegative integers?

Answer

Factor

a^2 - b^2 = (a - b)(a + b)

and note the two factors always have the same parity

Odd numbers and multiples of

4

are all achievable; numbers that are

2

more than a multiple of

4

are not

Write

n = a^2 - b^2 = (a - b)(a + b).

The factors

a - b

and

a + b

differ by the even number

2b,

so they have the same parity. If both are odd,

n

is odd; if both are even,

n

is divisible by

4.

Hence no integer

n \equiv 2 \pmod 4

is a difference of two squares.

Conversely, every odd number

2k + 1

equals

(k+1)^2 - k^2,

and every multiple of

4,

say

4k,

equals

(k+1)^2 - (k-1)^2

(with

k - 1 \ge 0

since

k \ge 1

).

Between

1

and

1000

there are

500

odd numbers and

250

multiples of

4,

for a total of

500 + 250 = 750.

Problem 1 in other years