{"history":[],"article":{"id":"95e77ca5-cec2-4946-873e-8687ba854251","title":"Vieta jumping","slug":"vieta-jumping","content":":::summary\n:::\n\n# \nIn [number theory](https://bliptext.com/articles/number-theory), **Vieta jumping**, also known as **root flipping**, is a [proof technique](https://bliptext.com/articles/mathematical-proof).\nIt is most often used for problems in which a relation between two integers is given, along with a statement to prove about its solutions.\nIn particular, it can be used to produce new solutions of a [quadratic](https://bliptext.com/articles/quadratic-equation) [Diophantine equation](https://bliptext.com/articles/diophantine-equation) from known ones.\nThere exist multiple variations of Vieta jumping, all of which involve the common theme of [infinite descent](https://bliptext.com/articles/infinite-descent) by finding new solutions to an equation using [Vieta's formulas](https://bliptext.com/articles/vieta-s-formulas).\n\n# History\nVieta jumping is a classical method in the theory of quadratic [Diophantine equations](https://bliptext.com/articles/diophantine-equations) and [binary quadratic forms](https://bliptext.com/articles/binary-quadratic-form).\nFor example, it was used in the analysis of the [Markov equation](https://bliptext.com/articles/markov-equation) back in 1879 and in the 1953 paper of Mills.\nIn 1988, the method came to the attention to [mathematical olympiad](https://bliptext.com/articles/mathematical-olympiad) problems in the light of the first olympiad problem to use it in a solution that was proposed for the [International Mathematics Olympiad](https://bliptext.com/articles/international-mathematics-olympiad) and assumed to be the most difficult problem on the contest:\na\nand\nb\nbe positive integers such that\nab + 1\ndivides\na2 + b2\n. Show that is the square of an integer.\n[Arthur Engel](https://bliptext.com/articles/arthur-engel-mathematician) wrote the following about the problem's difficulty:\n\"Nobody of the six members of the Australian problem committee could solve it. Two of the members were husband and wife George and Esther Szekeres, 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.\"\nAmong the eleven students receiving the maximum score for solving this problem were [Ngô Bảo Châu](https://bliptext.com/articles/ng-b-o-ch-u), [Ravi Vakil](https://bliptext.com/articles/ravi-vakil), [Zvezdelina Stankova](https://bliptext.com/articles/zvezdelina-stankova), and [Nicușor Dan](https://bliptext.com/articles/nicu-or-dan).\nEmanouil Atanassov (from Bulgaria) solved the problem in a paragraph and received a special prize.\n\n# Standard Vieta jumping\nThe concept of **standard Vieta jumping** is a [proof by contradiction](https://bliptext.com/articles/proof-by-contradiction), and consists of the following four steps:\na1, a2, ...\n) exists that violates the given requirements.\nai\nby a variable x in the formulas, and obtain an equation for which\nai\nis a solution.\n**Problem #6 at IMO 1988**: Let\na\nand\nb\nbe positive integers such that\nab + 1\ndivides\na2 + b2\n. Prove that\na2 + b2⁄ab + 1\nis a [perfect square](https://bliptext.com/articles/square-number).\nk\nthat is a non-square positive integer.\nAssume there exist positive integers\n(a, b)\nfor which\nk = a2 + b2⁄ab + 1\n.\n(A, B)\nbe positive integers for which\nk = A2 + B2⁄AB + 1\nand such that\nA + B\nis minimized, and [without loss of generality](https://bliptext.com/articles/without-loss-of-generality) assume\nA ≥ B\n.\nB\n, replace\nA\nwith the variable\nx\nto yield\nx2 – (kB)x + (B2 – k) = 0\n. We know that one root of this equation is\nx1 = A\n. By standard properties of quadratic equations, we know that the other root satisfies\nx2 = kB – A\nand\nx2 = B2 – k⁄A\n.\nx2\nshows that\nx2\nis an integer, while the second expression implies that\nx2 ≠ 0\nsince\nk\nis not a perfect square.\nFrom\nx22 + B2⁄x2B + 1 = k > 0\nit further follows that\nx2B > −1\n, and hence\nx2\nis a positive integer.\nFinally,\nA ≥ B\nimplies that\nx2 = B2 − k⁄A < B2⁄A ≤ A\n, hence\nx2 < A\n, and thus\nx2 + B < A + B\n, which contradicts the minimality of\nA + B\n.\n\n# Constant descent Vieta jumping\nThe method of **constant descent Vieta jumping** is used when we wish to prove a statement regarding a constant\nk\nhaving something to do with the relation between\na\nand\nb\n. Unlike standard Vieta jumping, constant descent is not a proof by contradiction, and it consists of the following four steps:\na > b\n.\nb\nand\nk\nare fixed and the expression relating\na, b\n, and\nk\nis rearranged to form a quadratic with coefficients in terms of\nb\nand\nk\n, one of whose roots is\na\n. The other root,\nx2\nis determined using Vieta's formulas.\n(a, b)\nabove a certain base case, show that\n0 < x2 < b < a\nand that\nx2\nis an integer.\nThus, while maintaining the same\nk\n, we may replace\n(a, b)\nwith\n(b, x2)\nand repeat this process until we arrive at the base case.\nk\nhas remained constant through this process, this is sufficient to prove the statement for all ordered pairs.\nLet\na\nand\nb\nbe positive integers such that\nab\ndivides\na2 + b2 + 1\n. Prove that\n3ab = a2 + b2 + 1\n.\na = b, a2\ndividing\n2a2 + 1\nimplies that\na2\ndivides 1, and hence the positive integers\na = b = 1\n, and\n3(1)(1) = 12 + 12 + 1\n. So, without loss of generality, assume that\na > b\n.\n(a, b)\nsatisfying the given condition, let\nk = a2 + b2 + 1⁄ab\nand rearrange and substitute to get\nx2 − (kb) x + (b2 + 1) = 0\n. One root to this quadratic is\na\n, so by Vieta's formulas the other root may be written as follows:\nx2 = kb − a = b2 + 1⁄a\n.\nx2\nis an integer and the second that it is positive.\nBecause\na > b\nand they are both integers,\na ≥ b + 1\n, and hence\nab ≥ b2 + b\nb > 1\n, we always have\nab > b2 + 1\n, and therefore\nx2 = b2 + 1⁄a < b\n. Thus, while maintaining the same\nk\n, we may replace\n(a, b)\nwith\n(b, x2)\nand repeat this process until we arrive at the base case.\nb = 1\n. For\n(a, 1)\nto satisfy the given condition,\na\nmust divide\na2 + 2\n, which implies that\na\ndivides 2, making\na\neither 1 or 2.\nThe first case is eliminated because\na = b\n. In the second case,\nk = a2 + b2 + 1⁄ab = 6⁄2 = 3\n. As\nk\nhas remained constant throughout this process of Vieta jumping, this is sufficient to show that for any\n(a, b)\nsatisfying the given condition,\nk\nwill always equal 3.\n\n# Geometric interpretation\nVieta jumping can be described in terms of lattice points on [hyperbolas](https://bliptext.com/articles/hyperbolas) in the first quadrant.\nThe same process of finding smaller roots is used instead to find lower lattice points on a hyperbola while remaining in the first quadrant.\nThe procedure is as follows:\nx\nand\ny\nso that they are symmetric about the line\ny = x\n.\ny = x\n.\n(x, y)\non some hyperbola and without loss of generality\nx < y\n. Then by Vieta's formulas, there is a corresponding lattice point with the same\nx\n-coordinate on the other branch of the hyperbola, and by reflection through\ny = x\na new point on the original branch of the hyperbola is obtained.\nx = 0\n) is achieved. Then by substitution of this condition into the equation of the hyperbola, the desired conclusion will be proven.\nThis method can be applied to **problem #6 at IMO 1988**: Let\na\nand\nb\nbe positive integers such that\nab + 1\ndivides\na2 + b2\n. Prove that\na2 + b2⁄ab + 1\nis a perfect square.\na2 + b2⁄ab + 1 = q\nand fix the value of\nq\n. If\nq = 1\n,\nq\nis a perfect square as desired.\nIf\nq = 2\n, then\n(a-b)2 = 2\nand there is no integral solution\na, b\n. When\nq > 2\n, the equation\nx2 + y2 − qxy − q = 0\ndefines a hyperbola\nH\nand\n(a,b)\nrepresents an integral lattice point on\nH\n.\n(x,x)\nis an integral lattice point on\nH\nwith\nx > 0\n, then (since\nq\nis integral) one can see that\nx = 1\n. This proposition's statement is then true for the point\n(x,x)\n.\nP = (x, y)\nbe a lattice point on a branch\nH\nwith\nx, y > 0\nand\nx ≠ y\n(as the previous remark covers the case\nx = y\n). By symmetry, we can assume that\nx < y\nand that\nP\nis on the higher branch of\nH\n. By applying Vieta's Formulas,\n(x, qx − y)\nis a lattice point on the lower branch of\nH\n. Let\ny = qx − y\n. From the equation for\nH\n, one sees that\n1 + x y > 0\n. Since\nx > 0\n, it follows that\ny ≥ 0\n. Hence the point\n(x, y)\nis in the first quadrant.\nBy reflection, the point\n(y, x)\nis also a point in the first quadrant on\nH\n. Moreover from Vieta's formulas,\nyy = x2 - q\n, and\ny = x2 - q⁄y\n. Combining this equation with\nx < y\n, one can show that\ny < x\n. The new constructed point\nQ = (y, x)\nis then in the first quadrant, on the higher branch of\nH\n, and with smaller\nx\n,\ny\n-coordinates than the point\nP\nwe started with.\nQ\nhas a positive\nx\n-coordinate.\nHowever, since the\nx\n-coordinates of these points will form a decreasing sequence of non-negative integers, the process can only be repeated finitely many times before it produces a point\nQ = (0, y)\non the upper branch of\nH\nq = y2\nis a square as required.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T11:52:00.803Z","updated_at":"2025-01-26T11:52:00.803Z","search_vector":"'jump':2 'vieta':1","search_content":" \n \n\n# \nIn [number theory](https://bliptext.com/articles/number-theory), **Vieta jumping**, also known as **root flipping**, is a [proof technique](https://bliptext.com/articles/mathematical-proof).\nIt is most often used for problems in which a relation between two integers is given, along with a statement to prove about its solutions.\nIn particular, it can be used to produce new solutions of a [quadratic](https://bliptext.com/articles/quadratic-equation) [Diophantine equation](https://bliptext.com/articles/diophantine-equation) from known ones.\nThere exist multiple variations of Vieta jumping, all of which involve the common theme of [infinite descent](https://bliptext.com/articles/infinite-descent) by finding new solutions to an equation using [Vieta's formulas](https://bliptext.com/articles/vieta-s-formulas).\n\n# History\nVieta jumping is a classical method in the theory of quadratic [Diophantine equations](https://bliptext.com/articles/diophantine-equations) and [binary quadratic forms](https://bliptext.com/articles/binary-quadratic-form).\nFor example, it was used in the analysis of the [Markov equation](https://bliptext.com/articles/markov-equation) back in 1879 and in the 1953 paper of Mills.\nIn 1988, the method came to the attention to [mathematical olympiad](https://bliptext.com/articles/mathematical-olympiad) problems in the light of the first olympiad problem to use it in a solution that was proposed for the [International Mathematics Olympiad](https://bliptext.com/articles/international-mathematics-olympiad) and assumed to be the most difficult problem on the contest:\na\nand\nb\nbe positive integers such that\nab + 1\ndivides\na2 + b2\n. Show that is the square of an integer.\n[Arthur Engel](https://bliptext.com/articles/arthur-engel-mathematician) wrote the following about the problem's difficulty:\n\"Nobody of the six members of the Australian problem committee could solve it. Two of the members were husband and wife George and Esther Szekeres, 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.\"\nAmong the eleven students receiving the maximum score for solving this problem were [Ngô Bảo Châu](https://bliptext.com/articles/ng-b-o-ch-u), [Ravi Vakil](https://bliptext.com/articles/ravi-vakil), [Zvezdelina Stankova](https://bliptext.com/articles/zvezdelina-stankova), and [Nicușor Dan](https://bliptext.com/articles/nicu-or-dan).\nEmanouil Atanassov (from Bulgaria) solved the problem in a paragraph and received a special prize.\n\n# Standard Vieta jumping\nThe concept of **standard Vieta jumping** is a [proof by contradiction](https://bliptext.com/articles/proof-by-contradiction), and consists of the following four steps:\na1, a2, ...\n) exists that violates the given requirements.\nai\nby a variable x in the formulas, and obtain an equation for which\nai\nis a solution.\n**Problem #6 at IMO 1988**: Let\na\nand\nb\nbe positive integers such that\nab + 1\ndivides\na2 + b2\n. Prove that\na2 + b2⁄ab + 1\nis a [perfect square](https://bliptext.com/articles/square-number).\nk\nthat is a non-square positive integer.\nAssume there exist positive integers\n(a, b)\nfor which\nk = a2 + b2⁄ab + 1\n.\n(A, B)\nbe positive integers for which\nk = A2 + B2⁄AB + 1\nand such that\nA + B\nis minimized, and [without loss of generality](https://bliptext.com/articles/without-loss-of-generality) assume\nA ≥ B\n.\nB\n, replace\nA\nwith the variable\nx\nto yield\nx2 – (kB)x + (B2 – k) = 0\n. We know that one root of this equation is\nx1 = A\n. By standard properties of quadratic equations, we know that the other root satisfies\nx2 = kB – A\nand\nx2 = B2 – k⁄A\n.\nx2\nshows that\nx2\nis an integer, while the second expression implies that\nx2 ≠ 0\nsince\nk\nis not a perfect square.\nFrom\nx22 + B2⁄x2B + 1 = k > 0\nit further follows that\nx2B > −1\n, and hence\nx2\nis a positive integer.\nFinally,\nA ≥ B\nimplies that\nx2 = B2 − k⁄A b\n.\nb\nand\nk\nare fixed and the expression relating\na, b\n, and\nk\nis rearranged to form a quadratic with coefficients in terms of\nb\nand\nk\n, one of whose roots is\na\n. The other root,\nx2\nis determined using Vieta's formulas.\n(a, b)\nabove a certain base case, show that\n0 b\n.\n(a, b)\nsatisfying the given condition, let\nk = a2 + b2 + 1⁄ab\nand rearrange and substitute to get\nx2 − (kb) x + (b2 + 1) = 0\n. One root to this quadratic is\na\n, so by Vieta's formulas the other root may be written as follows:\nx2 = kb − a = b2 + 1⁄a\n.\nx2\nis an integer and the second that it is positive.\nBecause\na > b\nand they are both integers,\na ≥ b + 1\n, and hence\nab ≥ b2 + b\nb > 1\n, we always have\nab > b2 + 1\n, and therefore\nx2 = b2 + 1⁄a 2\n, the equation\nx2 + y2 − qxy − q = 0\ndefines a hyperbola\nH\nand\n(a,b)\nrepresents an integral lattice point on\nH\n.\n(x,x)\nis an integral lattice point on\nH\nwith\nx > 0\n, then (since\nq\nis integral) one can see that\nx = 1\n. This proposition's statement is then true for the point\n(x,x)\n.\nP = (x, y)\nbe a lattice point on a branch\nH\nwith\nx, y > 0\nand\nx ≠ y\n(as the previous remark covers the case\nx = y\n). By symmetry, we can assume that\nx 0\n. Since\nx > 0\n, it follows that\ny ≥ 0\n. Hence the point\n(x, y)\nis in the first quadrant.\nBy reflection, the point\n(y, x)\nis also a point in the first quadrant on\nH\n. Moreover from Vieta's formulas,\nyy = x2 - q\n, and\ny = x2 - q⁄y\n. Combining this equation with\nx < y\n, one can show that\ny < x\n. The new constructed point\nQ = (y, x)\nis then in the first quadrant, on the higher branch of\nH\n, and with smaller\nx\n,\ny\n-coordinates than the point\nP\nwe started with.\nQ\nhas a positive\nx\n-coordinate.\nHowever, since the\nx\n-coordinates of these points will form a decreasing sequence of non-negative integers, the process can only be repeated finitely many times before it produces a point\nQ = (0, y)\non the upper branch of\nH\nq = y2\nis a square as required.","revisionCount":0},"hasMore":false,"nextCursor":null}