From: John Robertson Subject: Re: help me find the solution please Date: Fri, 13 Oct 2000 01:56:34 GMT Newsgroups: sci.math To: jkhaug00@studNOSPAM.hia.no In article <39E5D299.9F0271BD@studNOSPAM.hia.no>, Jan Kristian Haugland wrote: > > Dave Rusin wrote: > > > In article <8rim95$lpa$1@nnrp1.deja.com>, wrote: > > >find pairs of integers a, b such that > > > > > >(a^2+b^2+1)/(ab+a+b) > > > > > >results in a integer. > > > > I don't have the answer but I do want to comment that this looks an > > awful lot like a problem from an old Putnam or IMO exam. Does > > anyone recognize it? > > > > (Here "looks like" probably means the other problem also considered > > factors of integer values of a^2+b^2+1 .) > > Well, when I saw this problem, it reminded me of a problem > from the IMO in Australia, 1988: Prove that if a,b >= 1 > are integers such that c=(a^2+b^2)/(ab+1) is an integer, > then c is a square. This has been known as "the hardest > IMO problem ever"! > IIRC, the story behind the (a^2+b^2)/(ab+1) problem is discussed, and the problem is solved, in Arthur Engel's Exploring Mathematics with Your Computer, published by the MAA in the New Mathematical Library series. Sometime in the mid-nineties (maybe) a similar problem (asking about the possible values of a ratio of quadratics in two variables) was in the problem section of the American Mathematical Monthly. The published solution included a list of a few similar problems. Perhaps someone else has a better memory. John Robertson Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Jpr2718@aol.com Date: Thu, 12 Oct 2000 22:01:11 EDT Subject: (a^2+b^2+1)/(ab+a+b) and related To: rusin@vesuvius.math.niu.edu Dave, I posted the following to sci.math: IIRC, the story behind the (a^2+b^2)/(ab+1) problem is discussed, and the problem is solved, in Arthur Engel's Exploring Mathematics with Your Computer, published by the MAA in the New Mathematical Library series. Sometime in the mid-nineties (maybe) a similar problem (asking about the possible values of a ratio of quadratics in two variables) was in the problem section of the American Mathematical Monthly. The published solution included a list of a few similar problems. John Robertson ============================================================================== From: Dave Rusin Date: Thu, 12 Oct 2000 23:18:56 -0500 (CDT) To: Jpr2718@aol.com Subject: Re: (a^2+b^2+1)/(ab+a+b) and related Thanks for the tip; I'll take a look. A colleague says the problem(s) surfaced at a conference here at our place when Selfridge was running the joint. Evidently one of these problems made the exercise lists in Niven and Zuckerman, with lots of asterisks indicating difficulty. One colleague offers a 1-letter-grade bonus to students who solve it. (There has only been one claimant to the prize, and he didn't need it.) I can't find my copy of N&Z to check. Again, thanks for your response. dave ============================================================================== From: Jpr2718@aol.com Date: Sat, 14 Oct 2000 00:08:00 EDT Subject: Ratios of binary quadratics To: rusin@math.niu.edu (Dave Rusin) Dave, The Monthly problem I was thinking of is number 10203, solved March, 1994, page 279. This problem reduces to x^2 + y^2 + 1 = 3xy. There is a list of related problems at the end. A related problem is 10263, solved December 1992, to show that if abs(m^2+1-n^2) divides n^2-1, then abs(m^2+1-n^2) is a square. Another is 10382 asking what integers are represented by (x+y+z)^2/xzy for x, y, z > 0 - asked May 1994, I haven't found the published solution yet. And most related is 10316 to find a, b so that ab divides a^2 + b^2 + 1, solved December 1996. NZM, 5th ed (which you knew because it would be NZ otherwise), page 20, problem 54 is to show that if ab + 1 divides a^2 + b^2, then the quotient is a square. It may be the only problem in the book with a double asterisk. I will try to turn this into a more coherent post in the next few days. John ============================================================================== From: Dave Rusin Date: Fri, 13 Oct 2000 23:44:51 -0500 (CDT) To: Jpr2718@aol.com Subject: Re: Ratios of binary quadratics Great! Thanks for doing the legwork. That really is the NZ(M) problem I remembered. (I don't know its exact origin.) Since I spend my day in pointless meetings nowadays I can't comment on how hard it _really_ is; a colleague remembers a nice descent proof. dave ============================================================================== From: John Robertson Subject: Re: help me find the solution please Date: Sat, 14 Oct 2000 20:34:59 GMT Newsgroups: sci.math Summary: [missing] Choogu asked about integers a, b so that n = (a^2 + b^2 + 1)/(ab + a + b) is an integer. In another post, I conjecture that the only possible values for n are 1, 2, 5, 10, 14, and (-1)*(k^2 + 2) for k any (might as well be nonnegative) integer. For a given n, if abs(n) >= 3 then the theory of Pell equations can be used to find all solutions. If abs(n) <= 2, then completing the square a time or two is sufficient to reduce the equation to one whose solution is apparent. Some of these solutions are given in a post by Robert Israel. The main purpose of this note is to give some references to related problems. Jan Kristian Haugland noted that a problem on the 1988 IMO, held at Canberra, Australia, was to show that if a and b are positive integers so that q = (a^2 + b^2)/(ab + 1) is an integer, then q is a square. This problem is given as an exercise in Niven, Zuckerman, and Montgomery's An Introduction to the Theory of Numbers, fifth edition, 1991, page 20, problem 54 [thanks to Dave Rusin for pointing this out]. The history of problem and a solution are given in Arthur Engel's Exploring Mathematics With Your Computer, Mathematical Association of America, New Mathematical Library, Number 35, 1993, Section 65, pages 229-231. The problem was proposed for the 1988 IMO by the German Federal Republic. According to Engel, the Australian Problem Committee could not solve it, and neither could the four most prominent Australian number theorists over some six-hour period. Despite this, the question was put on the IMO, and 11 contestants got perfect scores for the problem. Engel gives a proof by descent. In exercise, Engel gives the problem of showing that if (a^2 + ab + b^2)/ (ab + 1) is an integer, then it is a square [I don't know whether it is assumed that a and b are positive]. Another exercise in Engel is to consider q = (a^2 + rab + b^2)/(sab + t) with r = -1, 0, or 1, and s, t >0. The question is to find conditions on s, t so that q is a square, or qt is a square. Problem 10203 in the American Mathematical Monthly, solved in Volume 101, Number 3, March 1994, pages 279-280, is, "Suppose that a, b, c, and d are positive integers satisfying the two relations b^2 + 1 = ac and c^2 + 1 = bd. Prove that a = 3b - c and d = 3c - b." This is equivalent to characterizing k, b, and c so that b, c > 0, k = (b^2 + c^2 +1)/(bc) and k is and integer. The solution is that k = 3, and b and c are consecutive odd-indexed Fibonacci numbers. The published solution to 10203 includes a list of related problems given by Robert Weber: x^2 + y^2 = k(xy + 1) iff k = m^2; x^2 + y^2 + 1 = k(xy + 1) iff k = m^2 + 1; x^2 + y^2 = k(xy - 1) iff k = 5; x^2 + y^2 - 1 = kxy has infinitely many solutions for every k >= 2 [I think x, y >0 is assumed for all of these]. It is noted that 10203 is virtually the same as problem E3210 in the AMM, solved in V. 95, No. 9, November 1988, pages 879-880. This problem is, "Determine all pairs (m, n) of integers such that 1 <= m <= n, m^2 == -1 (mod n), n^2 == -1 (mod m)." Another method to solve the equation m^2 + n^2 + 1 = 3mn is given after the solution of E3210. And Gerry Meyerson referenced W. Sierpinski and A. Schinzel, Sur l'equation x^2 + y^2 + 1 = xyz, Matematiche, Catania 10(1955), 30-36; MR 17 711e. Problem 10316 in the AMM, solved V. 103, No. 10, December 1996, page 905, is equivalent to E3210 and 10203. This problem is, "For what pairs of integers a, b, does ab exactly divide a^2 + b^2 + 1?" In addition to the references to E3210 and 10203 above, reference is made to L. J. Mordell's Diophantine Equations, Academic Press, 1966, [Chapter 30], page 299, and to I. M. Yaglom's The USSR Olympiad Problem Book, W. H. Freeman, 1962, pp. 205-208. Mordell, Chapter 30, Section 4, pages 295-300, gives a general treatment of ratios of binary quadratics, and specifically treats x^2 + y^2 + 1 = xyz [x, y, z any integers]; x^2 + y^2 + x + y + 1 = xyz, x>0, y>0; and x^2 + y^2 - x - y + 1 = xyz, x>0, y>0. Yaglom presents an algorithm for solving x^2 + y^2 + z^2 = kxyz. Problem 10382 in the AMM, solved V. 104, No. 3, March 1997, page 278 is, "Which integers are represented by (x + y + z)^2/(xyz) where x, y, and z are positive integers?" The answer is {1, 2, 3, 4, 5, 6, 8, 9}. Problem 10263 in the AMM, solved V. 101, No. 10, December 1994, page 1018 is, "Let m and n be odd integers, and suppose n^2 - 1 is a multiple of abs(m^2 + 1 - n^2). Prove or disprove that this requires that abs(m^2 + 1 - n^2) be the square of an integer." The solution shows that the implication holds. I would like to hear of other references to these problems or to related problems. John Robertson Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Jpr2718@aol.com Date: Sat, 14 Oct 2000 16:41:36 EDT Subject: Ratios of binary quadratics To: choogu@yahoo.com, israel@math.ubc.ca, rusin@vesuvius.math.niu.edu, jkhaug00@stud.hia.no I posted the following to Sci.Math: Choogu asked about integers a, b so that n = (a^2 + b^2 + 1)/(ab + a + b) is an integer. In another post, I conjecture that the only possible values for n are 1, 2, 5, 10, 14, and (-1)*(k^2 + 2) for k any (might as well be nonnegative) integer. For a given n, if abs(n) >= 3 then the theory of Pell equations can be used to find all solutions. If abs(n) <= 2, then completing the square a time or two is sufficient to reduce the equation to one whose solution is apparent. Some of these solutions are given in a post by Robert Israel. The main purpose of this note is to give some references to related problems. Jan Kristian Haugland noted that a problem on the 1988 IMO, held at Canberra, Australia, was to show that if a and b are positive integers so that q = (a^2 + b^2)/(ab + 1) is an integer, then q is a square. This problem is given as an exercise in Niven, Zuckerman, and Montgomery's An Introduction to the Theory of Numbers, fifth edition, 1991, page 20, problem 54 [thanks to Dave Rusin for pointing this out]. The history of problem and a solution are given in Arthur Engel's Exploring Mathematics With Your Computer, Mathematical Association of America, New Mathematical Library, Number 35, 1993, Section 65, pages 229-231. The problem was proposed for the 1988 IMO by the German Federal Republic. According to Engel, the Australian Problem Committee could not solve it, and neither could the four most prominent Australian number theorists over some six-hour period. Despite this, the question was put on the IMO, and 11 contestants got perfect scores for the problem. Engel gives a proof by descent. In exercise, Engel gives the problem of showing that if (a^2 + ab + b^2)/(ab + 1) is an integer, then it is a square [I don't know whether it is assumed that a and b are positive]. Another exercise in Engel is to consider q = (a^2 + rab + b^2)/(sab + t) with r = -1, 0, or 1, and s, t >0. The question is to find conditions on s, t so that q is a square, or qt is a square. Problem 10203 in the American Mathematical Monthly, solved in Volume 101, Number 3, March 1994, pages 279-280, is, "Suppose that a, b, c, and d are positive integers satisfying the two relations b^2 + 1 = ac and c^2 + 1 = bd. Prove that a = 3b - c and d = 3c - b." This is equivalent to characterizing k, b, and c so that b, c > 0, k = (b^2 + c^2 +1)/(bc) and k is and integer. The solution is that k = 3, and b and c are consecutive odd-indexed Fibonacci numbers. The published solution to 10203 includes a list of related problems given by Robert Weber: x^2 + y^2 = k(xy + 1) iff k = m^2; x^2 + y^2 + 1 = k(xy + 1) iff k = m^2 + 1; x^2 + y^2 = k(xy - 1) iff k = 5; x^2 + y^2 - 1 = kxy has infinitely many solutions for every k >= 2 [I think x, y >0 is assumed for all of these]. It is noted that 10203 is virtually the same as problem E3210 in the AMM, solved in V. 95, No. 9, November 1988, pages 879-880. This problem is, "Determine all pairs (m, n) of integers such that 1 <= m <= n, m^2 == -1 (mod n), n^2 == -1 (mod m)." Another method to solve the equation m^2 + n^2 + 1 = 3mn is given after the solution of E3210. And Gerry Meyerson referenced W. Sierpinski and A. Schinzel, Sur l'equation x^2 + y^2 + 1 = xyz, Matematiche, Catania 10(1955), 30-36; MR 17 711e. Problem 10316 in the AMM, solved V. 103, No. 10, December 1996, page 905, is equivalent to E3210 and 10203. This problem is, "For what pairs of integers a, b, does ab exactly divide a^2 + b^2 + 1?" In addition to the references to E3210 and 10203 above, reference is made to L. J. Mordell's Diophantine Equations, Academic Press, 1966, [Chapter 30], page 299, and to I. M. Yaglom's The USSR Olympiad Problem Book, W. H. Freeman, 1962, pp. 205-208. Mordell, Chapter 30, Section 4, pages 295-300, gives a general treatment of ratios of binary quadratics, and specifically treats x^2 + y^2 + 1 = xyz [x, y, z any integers]; x^2 + y^2 + x + y + 1 = xyz, x>0, y>0; and x^2 + y^2 - x - y + 1 = xyz, x>0, y>0. Yaglom presents an algorithm for solving x^2 + y^2 + z^2 = kxyz. Problem 10382 in the AMM, solved V. 104, No. 3, March 1997, page 278 is, "Which integers are represented by (x + y + z)^2/(xyz) where x, y, and z are positive integers?" The answer is {1, 2, 3, 4, 5, 6, 8, 9}. Problem 10263 in the AMM, solved V. 101, No. 10, December 1994, page 1018 is, "Let m and n be odd integers, and suppose n^2 - 1 is a multiple of abs(m^2 + 1 - n^2). Prove or disprove that this requires that abs(m^2 + 1 - n^2) be the square of an integer." The solution shows that the implication holds. I would like to hear of other references to these problems or to related problems. John Robertson ============================================================================== From: "Weyl" Newsgroups: sci.math Subject: Re: Number theory homework problem Date: Tue, 27 Nov 2001 10:08:41 +0100 "Pertzborn" schreef in bericht news:2d65ee79.0111262150.3b2fc908@posting.google.com... > Greetings, > > Suppose that a and b are positive integers with the property > that (1+ab) divides (a^2 + b^2). Show that the ratio > (a^2 + b^2)/(1+ab) must be a perfect square. > > This is problem 54 in section 1.2 of "An Introduction to the > Theory of Numbers", 5th ed., by Niven, Zuckerman, and Montgomery. > The problem was assigned (and due) in 1994 so I'm not trying > to cheat but it's been driving me nuts for years. Unfortunately > the prof didn't know a solution either. > > The only specific examples of solutions I've found are of the > form b = a^3, in which case the ratio is just a^2. Are these > the only solutions? > > Pertzborn I haven't read the book by Niven, but i know this is a problem from the international math olympiad. 1988 problem 6 you can find a solution at: http://www.kalva.demon.co.uk/imo/imo88.html (By the way, it's one of the hardest problems ever posed at IMO) Jan Tuitman ============================================================================== From: "Robin Chapman" Newsgroups: sci.math Subject: Re: Number theory homework problem Date: Tue, 27 Nov 2001 09:21:45 +0000 (UTC) "Pertzborn" wrote in message news:2d65ee79.0111262150.3b2fc908@posting.google.com... > Greetings, > > Suppose that a and b are positive integers with the property > that (1+ab) divides (a^2 + b^2). Show that the ratio > (a^2 + b^2)/(1+ab) must be a perfect square. The way I attacked this was to try to find a and b with (a^2 + b^2)/(1+ab) = 1, 4, 9 etc. Finding several examples gave me enough insight about the structure of the solution set for me to construct a proof. Robin Chapman -- Posted from jalapeno.ulcc.wwwcache.ja.net [194.82.103.40] via Mailgate.ORG Server - http://www.Mailgate.ORG ============================================================================== From: jr@redmink.demon.co.uk (John R Ramsden) Newsgroups: sci.math Subject: Re: Number theory homework problem Date: Wed, 28 Nov 2001 19:50:51 GMT "Weyl" wrote: > > "Pertzborn" schreef: > > > > Suppose that a and b are positive integers with the property > > that (1+ab) divides (a^2 + b^2). Show that the ratio > > (a^2 + b^2)/(1+ab) must be a perfect square. > > > > The only specific examples of solutions I've found are of the > > form b = a^3, in which case the ratio is just a^2. Are these > > the only solutions? > > [...] > > you can find a solution at: > http://www.kalva.demon.co.uk/imo/imo88.html Get thee behind me Satan !-) > (By the way, it's one of the hardest problems ever posed at IMO) You're kidding - Once one sees the idea, the solution only takes a few lines (although admittedly the "aha" moment might be a bit elusive for people not accustomed to various Diophantine tricks). Actually the IMO examiners could have been even more sadistic, by expressing the problem as follows: Let a, b be non-negative integers such that one of a.b + 1, a^2 + b^2 divides the other. Show that the quotient must be a perfect square. Reading this, there'd be a 50% chance of the unsuspecting examinee starting by solving the first "half" (a^2 + b^2 divides a.b + 1) as follows: Firstly, we can assume 0 <= a <= b. If a = 0 then a^2 + b^2 divides a.b + 1 if and only if b = 1, whereupon the quotient is 1^2. If 0 < a, b then 0 < 1 + a.b <= 1 + b^2 <= a^2 + b^2, with equality in both (required) if and only if a = b = 1, for which again the quotient is 1^2. Encouraged by this easy success, they might well expect to crack the other case in a minute or so by similar kinds of arguments ;-) SPOILER ... Suppose that for some integer c we have a^2 + b^2 = (a.b + 1).c, where again we assume a <= b. If a = 0 then c = b^2, which is a perfect square as required. If a = b, then b^2 + 1, being prime relative to b^2, divides 2. This forces b = 0 or 1, which are each consistent with a = b and give c = 0^2, 1^2 resp. Otherwise we have 0 < a < b, and in this case viewing the above equation defining c as a quadratic in b we see that it is monic (leading coefficient 1) and with integer coefficients. Thus, since it has one integer root, b, the other root, say b', must also be an integer (This is the key idea of the solution.) Furthermore, since the product of these two roots is a^2 - c (< a^2), it follows that if this product is non-zero, and thus positive, then a < b implies 0 < b' < a. Thus we can leapfrog from the solution a, b (with 0 < a < b) to a new solution b', a (with 0 < b' < a), and this descent can be continued, with the value of c unchanged, until we reach, as we must, a solution with a^2 - c = 0, i.e. c = a^2 so that b = a^3. Reversing this process, it can be seen that the complete set of non-trivial (0 < a < b) solutions comprises a chain of solutions for each a, starting with b = a^3, with c = a^2 for every solution in the chain. Cheers --------------------------------------------------------------------------- John R Ramsden (jr@redmink.demon.co.uk) --------------------------------------------------------------------------- The new is in the old concealed, the old is in the new revealed. St Augustine. --------------------------------------------------------------------------- ============================================================================== From: Erick Wong Newsgroups: sci.math Subject: Re: Reprise: Integer [a^2+b^2]/[1+a*b] not a square! Date: Fri, 30 Nov 2001 12:00:08 GMT Virgil wrote: > A problem was posted recently which asked for a proof that, for a > and b integers, the ratio r = [a^2+b^2]/[1+a*b] could be an integer > only if it were the square of an integer. > > If this was, in fact, how the problem was put, then it is wrong. > > While it may be true for natural numbers, it is not true for > integers. There are infinitely many solutions for which the ratio r > equals -5, which is clearly not a square. > > a=-1,b=2 is such a solution. This raises the obvious question: What is the range of integer values of [a^2+b^2]/[1+ab] where a and b are integers? I think I have a similar descent argument that -5 is the only such value, but I might have messed up some inequalities. Computational evidence does seem to bear out this hypothesis. It seems a curious collection, such a natural formulation resulting in "all squares, together with -5". -- Erick ============================================================================== From: slash_sad@yahoo.com (Andrei Ismail) Newsgroups: sci.math Subject: Re: Reprise: Integer [a^2+b^2]/[1+a*b] not a square! Date: 1 Dec 2001 01:39:41 -0800 Hello If I'm not mistaken , this was proposed at some International Mathematical Olimpyad in the past . Maybe it wouldn't be such a bad idea to look it up in John Schole's archive , or better , find the sollution yourself . I can remember that there are two proofs , one with induction over ab and one with a sollution-transformation function . That's about it , gotta run now :) Bye ============================================================================== From: "James Van Buskirk" Newsgroups: sci.math.num-analysis Subject: Re: I HAVE A QUESTION!!! WHO CAN HELP ME?? PLEASE!! IT IS IMPORTANT!! Date: Thu, 16 May 2002 00:21:41 GMT "Franz" wrote in message news:abum4e$3ud$1@lacerta.tiscalinet.it... > f = (a^2+b^2)/(ab+1) , where a and b are integer numbers. > f is a function of two integer variables. > I SHOULD DEMONSTRATE that when f is an integer, the square root of f is an > integer. > Please, help me as soon!! If the problem is not clear, tell me about!! > I would be very grateful if someone sent me a demonstration !!! > Thank you!! Kind of typical of number theory problems submitted to sci.math.num-analysis: ill-posed and obviously homework. The problem is ill-posed because a = -3 and b = 1 satisfies the hypothesis of the theorem, but ((-3)**2+1**2)/((-3)*1+1) = -5 is not the square of a rational integer. Either we have to assume 'integer' means 'algebraic integer' or 'nonnegative integer'. Since the first definition makes the theorem trivial, we will concentrate on the second. We will assume that b >= a >= 0. If a = 0, then our theorem reads (0**2+b**2)/(0*b+1) = b**2 and is clearly true. If a = 1, then (1**2+b**2)/(1*b+1) = b-1+2/(b+1) and it follows that b = 1, and we have 1-1+2/(1+1) = 1 = 1**2 so the theorem is again true. If a > 1, we have a**2+b**2 = 0 mod(a*b+1) so a**2 = -b**2 mod(a*b+1) a**3 = -a*b**2 = b mod(a*b+1) so it follows that b = a**3-k*(a*b+1) We know that k >= 0 since if it weren't, we would have b > a*b+1. If k = 0, then (a**2+b**2)/(a*b+1) = a**2, and the theorem is again true. Assume, therefore, that k > 0. Let's solve for b. We get: b = (a**3-k)/(k*a+1) It follows that (a**2+b**2)/(a*b+1) = (k**2+a**2)/(a*k+1) So we have a similar expression, and since k = (a**3-b)/(a*b+1) and a**3-b < a**3 and a*b+1 >= a*a+1 > a**2 it follows that k < a**3/a**2 = a So in our new expression, we have replaced b >= a > 1 by a > k > 1. We can repeat this process until at some point our new number is zero, at which point we will have (x**2+y**2)/(x*y+1) = (x**2+x**6)/(x*x**3+1) = x**2 which is the square of a rational integer. You're welcome. ============================================================================== From: Bill Dubuque Newsgroups: sci.math Subject: Re: I HAVE A QUESTION !!!!!! WHO CAN HELP ME?? PLEASE!!! IT IS IMPORTANT!! Date: 16 May 2002 06:26:38 -0400 Franz wrote: > > Show: If 0 <= k = (x^2+y^2)/(xy+1) then k is a square (x,y,k integers) Such diophantine problems are discussed frequently here, see e.g. [1]. Perhaps the most famous is the Markoff equation x^2 + y^2 + z^2 = 3xyz. The trick is to notice that the integral solutions on such conics admit nontrivial symmetries (reflections) which may be used to generate new solutions from old. The underlying structure is evident if you study the arithmetic gemometry of quadratic fields (or, equivalently, binary quadratic forms), but I don't have time to elaborate - perhaps someone else will be so kind. In any case, below is a quick sketch of the basic geometrical viewpoint -- for a slight generalization. CLAIM x^2 - k y x + y^2 = j, 0 <= j <= k => j square (x,y,j,k integers) Proof: (sketch) The equation is a hyperbola which enjoys besides the trivial symmetry (x,y) -> (y,x) another non-trivial symmetry on its integer points. Considered as a quadratic in x, given a solution (x,y) there is another (x',y) where x' is obtained by noting the sum of the roots is x + x' = 4y. Geometrically if we draw a horizontal line through (x,y) it will intersect the hyperbola in another point (x',y) and x' is an integer since x' = 4y - x (see the graph below). Symmetrically, drawing a vertical line through (x,y) yields another point (x,y') where y' = 4 x - y. Suppose (x,y) is a solution. If x = y, or x or y = 0 it's easy to see that j is a square. Otherwise, suppose w.l.o.g by symmetry, that x > y > 0. Show y > x' >= 0. Iterating this way (x,y) -> (y,x') must reach a minimal solution where x' = 0, then j = y^2 is a square. Below is the graph for k = 4, j = 1. Note if (c,0) is the minimal solution, so j = c^2, then iterating backwards shows that c divides all values of x, y since reflections x = 4y - x' are linear in x, y. So we may as well assume c = 1 -> j = 1. Then y' y x -> kx - y ... x,y = c [0 1 k k^2-1 k^3-2k k^4-3k^2+1 ...] and j = c^2 e.g. k = 4: 0 1 4 15 56 209 ... see below graph ... ky-x <- y x x' 30 _| / | p(y,x) = y^2 - 4 x y + x^2-1 = 0 => p(y',x)=0, y' = 4x-y | / p(y,x')=0, x' = 4y-x | y = 2 x +- sqrt(3 x^2 + 1) | / | ~= ( 2 +- sqrt(3)) x ~= {3.73, 0.27} x 20 _| / | | / 4,15 <== 4 + 56 = 4(15) <== 56,15 | #. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .# | /. || x' + x = 4 y _ - | . \/ _ - 10 _| / . _ - | . _ - | / . _ - 0 <- 1 <- 4 <- 15 <- 56 | . 15,4 _ - 1,4 |# . _ # 1,0 <== 4,1 <== 4,15 <== 56,15 |/ . _ - |#---#------------------------------------------------------------- 1,0 <= 4,1 | | | | | . 10 20 30 40 50 . ... y' + y = 4 x 1 + 15 = 4(4) -Bill Dubuque [1] John Robertson, sci.math 2000-10-14: Re: help me find the solution please http://groups.google.com/groups?threadm=8sag1j%244i0%241%40nnrp1.deja.com Bill Dubuque, sci.math 2001-07-24: Re: Pairs of integers and divisibility http://groups.google.com/groups?threadm=y8zofq9plou.fsf%40nestle.ai.mit.edu Kevin Brown: N = (x^2 + y^2)/(1+xy) is a Square http://www.mathpages.com/home/kmath334.htm John Scholes, IMO 1998 Problem 6 http://www.kalva.demon.co.uk/imo/isoln/isoln886.html ============================================================================== [The question arose again in 2005; a URL for the whole thread is http://groups.google.com/group/sci.math/browse_frm/thread/ac9e8c2d03ba6ec4/55f53ca725847f03 Following are some highlights from that thread. --djr] ============================================================================== From: mareg@mimosa.csv.warwick.ac.uk () Newsgroups: sci.math Subject: Re: Diophantine equation Date: Tue, 1 Feb 2005 11:56:45 +0000 (UTC) >Arne Smeets wrote: >> >> How to prove that if (a^2 + b^2)/(ab - 1) is a positive integer for >positive integers a and b, then it is equal to 5? Has anyone sent a correct solution to this yet? Here is my attempt! Let a^2 + b^2 = n(ab - 1) with a,b,n positive integers We first prove n >= 4. a^2 + b^2 >= 2ab, so certainly n > 2. For n=3, since a^2 = 0 or 1 mod 3, we would have 3|a and 3|b, but then 9 divides a^2 + b^2 but not 3(ab - 1), contradiction. Hence n >= 4, as claimed. Note that if a=1, then b-1 divides b^2 + 1, so b-1 divides 2, and we get the solutions b=2 or 3, n=5. So we may assume that a > 1 and b > 1. We want to prove that n=5 so, for a contradiction, choose a solution with n not equal to 5 and a+b minimal. Assume that a >= b. Let a = nb - c. Then b^2 + c^2 = n(bc - 1), so b,c is another solution for the same n. If n >= ab, then a^2 + b^2 >= a^2 b^2 - ab, which is not possible for a, b > 1. So n < ab. We have a/b + b/a = n - n/(ab), and since b/a <= 1, this gives 0 < n - a/b < 2 and hence, since n >= 4, a/b > 2. But n - a/b = c/b < 2, so c/b < a/b, and b+c < b+a, contradicting the minimality of the solution. Derek Holt. ============================================================================== From: sttscitrans@tesco.net Newsgroups: sci.math Subject: Re: Diophantine equation Date: 1 Feb 2005 18:30:35 -0800 Dave Rusin wrote: > In article <200501300818.j0U8IwK29711@proapp.mathforum.org>, > Arne Smeets wrote: > > > How to prove that if (a^2 + b^2)/(ab - 1) is a positive integer for > > positive integers a and b, then it is equal to 5? > > How to prove that if (a^2 + b^2)/(ab + 1) is a positive integer for > positive integers a and b, then it is equal to a perfect square? A cubic variant that goes "one better" is given a,b,c are positive integers and a < 2b, b < 2c then prove that if (a^3 + 2b^3 +4c^3)/(abc + 1) is a positive integer it equals 6 or give a counterexample. ============================================================================== From: anonymous@mathforum.org Newsgroups: sci.math Subject: Re: Diophantine equation Date: Tue, 1 Feb 2005 12:42:49 +0000 (UTC) On 31 Jan 2005, Dave Rusin wrote: >How to prove that if (a^2 + b^2)/(ab + 1) is a positive integer for >positive integers a and b, then it is equal to a perfect square? Haha :) >(It's a classic stumper so if you want a challenge, don't look at >the posted solutions!) > >dave That is a classic problem indeed, given in the international mathematical olympiad in 1988. However it is easier than the problem about (a^2 + b^2)/(ab - 1) in my opinion because the descent works immediately (it is much more obvious that we are going down) and finally we have to reach a solution (a, b) where b = 0, giving (a^2 + b^2)/(ab + 1) = a^2. (Put (a^2 + b^2) = k(ab + 1). We create new solutions going from (a, b) to ((b^2 - k)/a, b). However we can assume WLOG that a >= b and then (b^2 - k)/a < (a^2 - k)/a < a.) ============================================================================== From: "Ignacio Larrosa Cañestro" Newsgroups: sci.math Subject: Re: Diophantine equation Date: Fri, 4 Feb 2005 09:50:26 +0100 escribió en el mensaje news:1107480142.669379.116850@l41g2000cwc.googlegroups.com... Ignacio Larrosa Cañestro wrote: >En el mensaje:1107401578.587737.66490@f14g2000cwb.googlegroups.com, >sttscitrans@tesco.net escribió: >> Ignacio Larrosa Cañestro wrote: >>> "Arne Smeets" escribió en el mensaje >>> news:200501300818.j0U8IwK29711@proapp.mathforum.org... >>>> How to prove that if (a^2 + b^2)/(ab - 1) is a positive integer for >>> positive integers a and b, then it is equal to 5? >>>> I'm stuck - I have been trying several "descent algorithms" but they >>> didn't work so far. >>> >>> 1. No solutions with a = b >>> >>> 2. For a = 1, the only two solutions are b = 2 and b = 3, both with >>> k = 5 >>> >>> 3. Suppose then that there is a solution (a, b) with 1 < a < b and >>> certain k. Show that (A, B) = (ka - b, a) is also a solution, with >>> the same k, and 0 < A < a = B >>> >>> 4. As the step 3 can't be iterated infinitely, you must reach a >>> solution with A = 1. But then, for step 2, k mus be 5. Done. >> >> You can produce an infinite number >> of solutions with increasing a, b from the >> primitive solutions (2,1) and (3,1) by the >> transformation (a,b) =(5a-b, a) > > Of course. Actually, all of them cen be reached going to left (a',b') = > (5a - b, a), or to the right (a', b') = (b, 5b - a), in > > > > where a solution is a pair of consecutive numbers. > > So you go along a branch of the hyperbola a^2 + b^2 - 5ab + 5 = 0 > > >> However the equation (a^2 +b^2)/(ab-1) =N >> can be written as a^2 -Nab + b^2 = -N. >> If N = 17 >> a^ -17ab +b^2 = -89 has solutions >> such as (3,2) > > But that is other equation! If N = 17, it must be > > a^2 - 17ab + b^2 = -17 > > and it hasn't integer solutions. ======================= [sttscitrans]: Yes, proving that a^2 - Nab + b^2 = -N has no integer solutions, except when N =5, is the difficulty. How do you do that ? 1) and 2) are true. If you can reduce any (a,b) to (a',1) no matter what k you choose then all (a,b) would be on the N=5 hyperbola. But you are assuming that a point on a N<>5 hyperbola must equal (a',1) ======================== [ILC]: (Note: My OE it isn`t quote properly by unknown reasons) At point 3), form a hipotetical solution (a, b; k) with 1 < a < b, I get other solution (A, B; k) with 0 < A < a. Then, point 4), we must reach neccessarily a solution of the form (1, B; k) that halts the 'descense'. By 2), then B = 2 or 3 and K = 5. Best regards, Ignacio Larrosa Cañestro A Coruña (España) ilarrosaQUITARMAYUSCULAS@mundo-r.com ============================================================================== From ilarrosaQUITARMAYUSCULAS@mundo-r.com Mon Feb 14 11:27:53 CST 2005 Article: 361488 of sci.math Path: news!news.niu.edu!canoe.uoregon.edu!elk.ncren.net!solaris.cc.vt.edu!news.vt.edu!newsfeed-00.mathworks.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "Ignacio Larrosa Cañestro" Newsgroups: sci.math Subject: Re: Diophantine equation Date: Fri, 4 Feb 2005 20:29:33 +0100 Lines: 219 Message-ID: <36i0otF537g35U1@individual.net> References: <200501300818.j0U8IwK29711@proapp.mathforum.org> <36ckbkF4vk52bU1@individual.net> <1107401578.587737.66490@f14g2000cwb.googlegroups.com> <36f7c9F4vok6kU1@individual.net> <1107480142.669379.116850@l41g2000cwc.googlegroups.com> <36grdcF51m9p1U1@individual.net> <1107518652.840225.83330@l41g2000cwc.googlegroups.com> Reply-To: "Ignacio Larrosa Cañestro" X-Trace: individual.net HTayfw1gVjBpqpTsGuYW8Q2pjzj832HllsmoGUFSfLHSwMXQdq X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.2180 X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 X-RFC2646: Format=Flowed; Original Xref: news sci.math:361488 Status: RO Content-Length: 6227 En el mensaje:1107518652.840225.83330@l41g2000cwc.googlegroups.com, sttscitrans@tesco.net escribió: > Ignacio Larrosa Cañestro wrote: >> escribió en el mensaje >> news:1107480142.669379.116850@l41g2000cwc.googlegroups.com... >> Ignacio Larrosa Cañestro wrote: >>> En el mensaje:1107401578.587737.66490@f14g2000cwb.googlegroups.com, >>> sttscitrans@tesco.net escribió: >>>> Ignacio Larrosa Cañestro wrote: >>>>> "Arne Smeets" escribió en el mensaje >>>>> news:200501300818.j0U8IwK29711@proapp.mathforum.org... >>>>>> How to prove that if (a^2 + b^2)/(ab - 1) is a positive integer >>>>>> for positive integers a and b, then it is equal to 5? I'm stuck >>>>>> - I have been trying several "descent algorithms" but >>>> they >>>>> didn't work so far. >>>>> >>>>> 1. No solutions with a = b >>>>> >>>>> 2. For a = 1, the only two solutions are b = 2 and b = 3, both >>>>> with k = 5 >>>>> >>>>> 3. Suppose then that there is a solution (a, b) with 1 < a < b and >>>>> certain k. Show that (A, B) = (ka - b, a) is also a solution, with >>>>> the same k, and 0 < A < a = B >>>>> >>>>> 4. As the step 3 can't be iterated infinitely, you must reach a >>>>> solution with A = 1. But then, for step 2, k mus be 5. Done. >>>> >>>> You can produce an infinite number >>>> of solutions with increasing a, b from the >>>> primitive solutions (2,1) and (3,1) by the >>>> transformation (a,b) =(5a-b, a) >>> >>> Of course. Actually, all of them cen be reached going to left (a', >>> b') = (5a - b, a), or to the right (a', b') = (b, 5b - a), in >>> >>> >>> >>> where a solution is a pair of consecutive numbers. >>> >>> So you go along a branch of the hyperbola a^2 + b^2 - 5ab + 5 = 0 >>> >>> >>>> However the equation (a^2 +b^2)/(ab-1) =N >>>> can be written as a^2 -Nab + b^2 = -N. >>>> If N = 17 >>>> a^ -17ab +b^2 = -89 has solutions >>>> such as (3,2) >>> >>> But that is other equation! If N = 17, it must be >>> >>> a^2 - 17ab + b^2 = -17 >>> >>> and it hasn't integer solutions. >> >> ======================= >> [sttscitrans]: >> >> Yes, proving that a^2 - Nab + b^2 = -N >> has no integer solutions, except when N =5, >> is the difficulty. >> >> How do you do that ? >> >> 1) and 2) are true. If you can reduce >> any (a,b) to (a',1) no matter what k you >> choose then all (a,b) would be on >> the N=5 hyperbola. >> But you are assuming that a point on a >> N<>5 hyperbola must equal (a',1) >> ======================== >> [ILC]: >> >> (Note: My OE it isn`t quote properly by unknown reasons) >> >> At point 3), form a hipotetical solution (a, b; k) with 1 < a < b, I >> get other solution (A, B; k) with 0 < A < a. Then, point 4), we must >> reach neccessarily a solution of the form (1, B; k) that halts the >> 'descense'. By 2), then B = 2 or 3 and K = 5. > > How are you showing that with any K, that > eventually (a,1) is reached ? That is the complete develop of the solution. It is in spanish, I'm sorry, but I don't very good in english and I am hurry now. 1) No hay soluciones con m = n: 2m^2/(m^2 - 1) = k Para m = 1 no hay solución y si m >= 2, tenemos que 2 < k < 8/3 2) Para m = 1, solo hay dos soluciones, con n = 2 ó 3 y k = 5 (1 + n^2)/(n - 1) = k ==> n^2 - kn + k + 1 = 0 n = (k +/- rq(k^2 - 4k - 4))/2 Para que la raíz sea entera, k^2 - 4k - 4 = (k - 2)^2 - 8 = h^2 ===> (k - 2)^2 - h^2 = 8 ===> (k - 2 - h)(k - 2 + h) = 8 cuya única solución en enteros positivos es k = 5, h = 1. Esto nos da n = 2 ó 3. 3) Supongamos entonces que tenemos una solución con 1 < m < n y cierto k positivo (suponer m < n no es ninguna restricción, dada la simetría del problema). Entonces, (M, N) = (km - n, m) es otra solución, ya que M^2 + N^2 = (km - n)^2 + m^2 = k^2m^2 - 2kmn + n^2 + m^2 = k^2m^2 - 2kmn + k(mn - 1) = k(km^2 - mn - 1) = k(MN - 1) Por otra parte, es M > 0 ya que M = km - n = m(m^2 + n^2)/(mn - 1) - n > m(m^2 + n^2)/(mn) - n = m^2/n + n - n = m^2/n > 0 De otro lado, esta es la clave, M < N = m, ya que las siguientes desigualdades son equivalentes, km - n < m km < n + m (m^2 + n^2)m < (n + m)(mn - 1) (pues mn > 1) m^3 + n^2m < n^2m + m^2n - n - m m^3 + m < n(m^2 - 1) m^3 - m + 2m < n(m^2 - 1) 2m < n(m^2 - 1) - m(m^2 - 1) 2m < (n - m)(m^2 - 1) Pero esto último es cierto siempre que m > 2 ó n - m > 1, pues n > m ===> n - m >= 1 ===> (n - m)(m^2 - 1) >= m^2 - 1 > 2m Para m = 2 y n - m = 1, vemos directamente que no hay soluciones: (2^2 + 3^2)/(2*3 - 1) = 13/5 no es entero. Tenemos ya todos los ingredientes para el "descenso": dada una solución (m,n) con 1 < m < n, hemos encontrado encontramos otra solución (M, N) MAS PEQUEÑA, M < m, con 0 < M < N (y con el mismo k). Dado que no podemos repetir este proceso indefinidamente, habrá algún momento en que llegaremos a una solución (A,B) con A = 1 y el mismo k. Pero por el paso 2, tenemos entonces que NECESARIAMENTE k=5. Para B tenemos solo los valores 2 ó 3 y todas las soluciones se obtienen como en el mensaje anterior. -- Best regards, Ignacio Larrosa Cañestro A Coruña (España) ilarrosaQUITARMAYUSCULAS@mundo-r.com > All the transformation shows is that > > (a(n)^2 +b(n)^2)/(a(n)b(n) -1) = K => > (a(n-1)^2 +b(n-1)^2)/(a(n-1)b(n-1) -1) = K > > and that > (a(n-1)^2 +b(n-1)^2)/(a(n-1)b(n-1) -1) = K => > (a(n)^2 +b(n)^2)/(a(n)b(n) -1) = K > > In my last post I show by long division that > the transformation with K, any integer, gives > (a(0)^2 +b(0)^2)/(a(0)b(0) -1) = 5 => > (a(1)^2 +b(1)^2)/(a(1)b(1) -1) = 5 > > Reprsent the statement > (a(n)^2 +b(n)^2)/(a(n)b(n) -1) = K > by F(n,K) > > As F(n,K) => F(n-1,K) > and F(n-1,K) => F(n,K) > > F(0,5) => F(1,5) > F(1,5) => F(2,K) = F(2,5) > and so on > > The transformation > T = [(K, 1)( 1, 0)] has det= -1 > > So T(a,b) -> (a',b') does not > miss out any solutions on the same > hyperbola. I don't see why > T(3,1), T(2,1) would necessarily take > you to a different hyperbola though. > The transformation takes you along > a hyperbola, not from one hyperbola to > another. The minima of a <>5 hyperbola > might be greater than those of the 5 hyperbola. > Perhaps another kind of descent is required ? ==============================================================================