POLYA002: Integer pairs (x,y) for which (x^2+y^2)/(1+pxy) is an integer (proposed by Jean-Pierre Ehrmann, 11/7/01).
Given positive integers p, q satisfying pq > 1, find the set of integer pairs {x,y} such that x^2+y^2 = q(pxy+1).

Discussion. [PY, 11/9/01]: After typing this up, by coincidence, I ran into this story on p.127 of A.Engel's ``Problem-Solving Strategies'':
The problem [IMO,1988: If a,b, q = (a^2+b^2)/(ab+1) are integers, then q is a perfect square] was submitted in 1988 by the FRG. Nobody of the six members of the Australian problem committee could solve it. Two of the members were Georges [sic]  Szekeres and his wife, both famous problem solvers and problem creators. Since it was a number theoretic problem it was sent to the four most renowned Australian number theorists. They were asked to work on it for six hours. None of them could solve it in this time. The problem committee submitted it to the jury of the XXIX IMO marked with a double asterisk, which meant a superhard problem, possibly too hard to pose. After a long discussion, the jury finally had the courage to choose it as the last problem of the competition. Eleven students gave perfect solutions.

Now I recall having heard the same story from Hans-Dietrich Gronau 2 years ago.

[JPE, 11/9/01]:  I don't understand why this exercice seems so difficult. May be because a number theorist knows too much things to do it. The only thing to know is the sum and the product of the roots of a quadratic equation. If (a,b) is a solution with a>= b > 0, then the roots of x^2 - qbx + b^2-q = 0 are a and c=qb-a=(b^2-q)/a. Hence (b,c) is another solution and b>c>=0. Hence, if we choose b minimal, we get c=0 and q=b^2.

[PY, 11/9/01]: Let me try to understand you. For a positive integer q, let write B_q for the set of positive integers b for which there exist a (>= b) such that a^2 - qba + b^2-q = 0. If B_q is nonempty, let c the smallest integer in be smallest element. Necessarily, c^2 = q. This settles the IMO question.
But one can go further. With q = c^2, the equation becomes  a^2 - c^3a = 0, and a = c^3.  [Check: a^2+c^2/(ac+1) = c^2(c^4+1)/(c^4+1) = c^2 = q].
Your method of descent actually leads to a description of the set of integers (a,b) satisfying (a^2+b^2)/(1+ab) = integer c^2. These pairs are the consecutive terms of  the sequence (u_n) defined recursively by
u_(n+2) = c^2.u_(n+1) - u_n,  u_0 = c, u_1 = c^3.
Explicitly, the beginning terms of the sequence are c, c^3, c^5-c, c^7-2c^3, c^9-3c^5+c, c^11-4c^7+3c^3, ...
For c = 2, this is the sequence 2, 8, 30, 112, 418, 1560, 5822, 21728, 81090, ...
For c = 3, this is 3, 27, 240, 2133, 18957, 168480, 1497363, ...
Now I understand why you asked the question. Given p and q with pq>1, there are integers (x,y) satisfying the quadratic equation (x^2+y^2)/(1+pxy) = q if and only if q = c^2 for an integer c. The pairs of (x,y) satisfying this condition are the consecutive terms of the sequence
U_(n+2) = pc^2.U_{n+1} - U_n,  U_0 = c, U_1 = pc^3.
The beginning terms are c, pc^3, p^2c^5-c, p^3c^7-2pc^3, p^4c^9-3p^2c^5+c, p^5c^11-4p^3c^7+3pc^3, ...
For p = 3, q = 2, this is the sequence 2, 24, 286, 40610, 483912, 5766334, ...
For p=2, q=3, this is 3, 54, 969, 17388, 312015, 5598882, ...
Very interesting. Thank you for a good problem.

[JPE, 11/9/01]:  That was exactly my conclusion and my way to get the result. Note that u[n] = sum((-1)^k C(n-k,k) p^(n-2k) c^(2n-4k+1), 0<=k<=n/2) and that u[n] is closely related to the Chebychev polynomial P[n] such as sin(n+1)x = P[n](2 cos x) sin x or sinh(n+1)x = P[n](2 cosh x) sinh x.  In fact, u[n] = cP[n](pc^2). Another interesting conclusion is that c is the gcd of x,y for any pair of solutions.

[FvL: 11/28/01]: Perhaps it is interesting to extend this problem to triangular numbers t(n)=n(n+1)/2.
In a way very similar to the IMO problem, we can prove that if, a, b and q =( t(a) + t(b) )/( 1 + ab ) are integers, then N is a triangular number.
We get ( a(a+1) + b(b+1) ) / ( 2 + 2ab ) = q rewritten to a^2 + (1-2bq)a + b^2 + b - 2q = 0.
The roots of x^2 + (1-2bq)x + b^2 + b - 2q = 0 are x=a and x=2bq-a-1=(b^2+b-2q)/a=:c. When a>b and thus a>=b+1 we can show that c<b.
Etc. The sequence yielding pairs u_n and u_{n+1} such that q=t(m) are given by u_n = 2t(m)u_{n-1}-u_{n-2}-1, u_0 = m, u_1 = m^3 + m^2 - 1.
So q=3 gives 2, 11, 63, 366, 2132, 12425, 72417, ...
q=6 gives 3, 35, 416, 4956, 59055, 703703, ...
I have not gone into denominators (1+pab). All does not work for n-gonal numbers with n>4 in stead of the triangular or square numbers, this does not work. Then the second root of the quadratic equation is not necessarily an integer. For n=5 I made a small table indicating that indeed "q" is not pentagonal.

[FvL: 11/29/01]: Perhaps it is interesting to generalize JPE's original question in another way (than the triangular numbers of yesterday): In stead of putting p in the denominator we could also put p into the numerator as follows: (x^2 + pxy + y^2)/(1+xy) = q.
An interesting example is when we take p=2 and q=9, then we find as solution sequence: 3, 21, 144, 987, 6765, 46368, 317811, ...  which are Fibonacci(4n).
Since 1+xy must be a square as good as the numerator and q are, we know that sqrt(u(n)u(n+1)+1) gives an integersequence, which is indeed  1, 8, 55, 377, 2584, 17711, 121393, ... which are Fibonacci(4n+2).
Taking q = c^2 the recurrence relation is u_n = (c^2-p)u_{n-1) - u_{n-2}, u_0 = c, u_1 = c^3 - pc.

[FvL: 12/3/01]:  In my last contribution to this discussion I have been imprecise.
We can only apply the IMO-method to (x^2 + pxy + y^2)/(1+xy) = q when the numerator is pos.def. This is only the case for -2 < p < 2, so the example, (x+y)^2/(1+xy)=9, I gave was not solved completely. In fact there is a second sequence with solutions, being Fibonacci(4n+2).
 

Bibliography. [1] A.Engel, Problem -Solving Strategies, Springer, 1998.
 
 

Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]