Maths Olympiad Prep

Library / /30 of 43

, 2007

Number theory Difficulty 5.7 AIME, harder Prove it Italy

Problem:

If aa is a positive integer less than 100100, for how many values of aa does the system
{x2=y+ay2=x+a \begin{cases} x^{2} = y + a \\ y^{2} = x + a \end{cases}
have integer solutions?

Solution

Solution:

The answer is 1919. Subtracting the two equations term by term we get x2y2=yxx^{2} - y^{2} = y - x, that is (xy)(x+y+1)=0(x - y)(x + y + 1) = 0.

Suppose that the first factor vanishes, that is y=xy = x: substituting, xx must satisfy the equation x2xa=0x^{2} - x - a = 0. Hence aa must be such that
x=1±1+4a2 is an integer.  x = \frac{1 \pm \sqrt{1 + 4a}}{2} \text{ is an integer. }
This happens if and only if aa is such that 1+4a1 + 4a is the square of an odd number. In other words, aa must be such that there exists an nNn \in \mathbb{N} such that 1+4a=(2n+1)21 + 4a = (2n + 1)^{2}, that is such that a=n(n+1)a = n(n + 1). Since 0<a<1000 < a < 100, the acceptable values of nn are those from 11 to 99 inclusive.

Now suppose that the second factor vanishes. Proceeding analogously to the previous case, y=x1y = -x - 1; substituting, xx must satisfy the equation x2+x+(1a)=0x^{2} + x + (1 - a) = 0. aa must be such that
x=1±1+4(a1)2 is an integer.  x = \frac{-1 \pm \sqrt{1 + 4(a - 1)}}{2} \text{ is an integer. }
Once again 1+4(a1)1 + 4(a - 1) must be the square of an odd integer, that is 1+4(a1)=(2n+1)21 + 4(a - 1) = (2n + 1)^{2}, that is a=n(n+1)+1a = n(n + 1) + 1. The acceptable values of nn are those from 00 to 99 inclusive and give all values of aa distinct from those of the previous case.

Summing up we have 99 values of aa from the first case and 1010 from the second for a total of 1919 integer values of aa for which the system has integer solutions.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.