每日科技文摘Daily Tech Digest

每日科技文摘 · 2026-10-04Daily Tech Digest · 2026-10-04

发布于 2026-10-04Published 2026-10-04

今日深读Today's Deep Read

今日深读:一个程序员去搜黎曼猜想的反例 / Today's Deep Read: A Programmer Goes Hunting for a Riemann Hypothesis CounterexampleToday's Deep Read: A Programmer Goes Hunting for a Riemann Hypothesis Counterexample

黎曼猜想是数学里最有名的未解问题之一:1900 年希尔伯特把它列进 problems 清单,2000 年克雷数学研究所为它悬出一百万美元赏金。它说的是素数分布的精细规律——ζ 函数所有「非平凡零点」的实部都恰好等于 1/2。一百六十多年来没人证明它,也没人推翻它。程序员出身的数学博主 Jeremy Kun(Math ∩ Programming 站主)做了一件很程序员的事:他写了一个程序,亲自去找反例。这组文章是 2021 年写的,本篇是最后一章——拿到数据之后怎么读。The Riemann Hypothesis is the most famous unsolved problem in mathematics: flagged by Hilbert in 1900, prize of one million dollars from the Clay Institute since 2000. It says something precise about the distribution of primes — all nontrivial zeros of the zeta function have real part exactly 1/2. For over 160 years nobody has proved it, and nobody has broken it. Jeremy Kun, a programmer-running math blogger (Math ∩ Programming), did something very programmer-ish: he wrote software and went looking for a counterexample himself. This series dates from 2021; the final post is what to do with the data once you have it.

第一步,把解析问题变成算术问题。直接去算 ζ 函数的零点太难了。Kun 用的是数论家 Lagarias 在 2002 年给出的等价表述:黎曼猜想成立,当且仅当对每个不小于 2 的整数 n,约数之和 σ(n) 都满足 σ(n) ≤ H_n + ln(H_n)·e^{H_n},其中 H_n 是调和级数的前 n 项和。换句话说,只要对越来越大的 n 挨个检查这条不等式,一旦哪天左边超过了右边,黎曼猜想就完蛋了。一个关于复平面的猜测,就这样变成了「枚举整数、算两个数、比大小」——程序员的主场。Step one, turn analysis into arithmetic. Computing zeta zeros directly is brutal. Kun uses Lagarias's 2002 equivalent statement: the Riemann Hypothesis holds if and only if for every integer n ≥ 2, the divisor sum σ(n) satisfies σ(n) ≤ H_n + ln(H_n)·e^{H_n}, where H_n is the n-th harmonic number. So you can just keep checking the inequality on larger and larger n — the first n that flips it kills the hypothesis. A conjecture about the complex plane becomes: enumerate integers, compute two quantities, compare.

第二步,别傻搜,找结构。对全体整数逐个检查是行不通的,因为真反例(如果存在)几乎必然长着特殊的样子。Kun 关注「超丰数」:σ(n)/n 这个比值比所有比它小的数都大的数。直觉上,一个数要把约数之和「堆」得特别高,就得把前 k 个小素数按指数递减打包进自己的质因数分解——2 的指数最大,3 的次之,越大的素数指数越小。于是搜索空间从「所有整数」坍缩成「一小族候选数的指数组合」,可以系统地枚举。每个数算出一个「见证值」,衡量它离打破不等式还有多远。Step two, don't brute force — find structure. Checking every integer is hopeless, and a real counterexample (if one exists) must have a special shape. Kun focuses on superabundant numbers: n where σ(n)/n exceeds the ratio for every smaller number. Intuitively, to stack up divisor sums you pack the first k small primes into n with decreasing exponents — the largest power of 2, then of 3, and so on. The search space collapses from 'all integers' to a narrow family of exponent combinations. Each candidate gets a witness value measuring how close it comes to violating the inequality.

第三步,用真正的软件工程做科研。这个搜索程序有测试、持续集成、报警和部署脚本,跑在 AWS 上,结果存进 Postgres 数据库——这样跑一半机器挂了,pg_dump 导出来就能接着搜。Kun 讲了一个好笑又真实的插曲:他把程序丢在云上就忙着买房,几周没管,再想起来时先看到的是账单。程序本身倒是没出过一次报警。Step three, do science with real software engineering. The search program has tests, continuous integration, alerting and deployment automation, runs on AWS, and logs results into Postgres — so if the machine dies mid-run, a pg_dump lets the search resume. Kun shares a funny, true detail: he left it running in the cloud, got busy buying a house, forgot about it for weeks, and the first thing he saw on return was the AWS bill. The software itself never fired an alert.

第四步,数据说了什么。搜索停在拥有 136 个不同质因数的那一族数上,处理过的最大数字有几百位。找到的最佳见证值是 1.7708——而真正推翻黎曼猜想需要见证值超过约 1.782。也就是说,差一点,但没到。更有趣的是数据的形状:随着质因数一个个加进去、指数被调整,见证值几乎单调地往上爬。这个规律本身成了启发式——它告诉你下一步该往哪个方向搜索。数据没有推翻猜想,却让你「看见」了它:在搜索所及的范围内,黎曼猜想是「勉强」成立的,余量以一种高度有序的方式一点点收窄。Step four, what the data says. The search stopped at the family of numbers with 136 distinct prime factors; the largest number processed has hundreds of digits. The best witness value found was 1.7708 — disproving RH requires roughly 1.782. Close, but no. More interesting is the shape of the data: as prime factors get added and exponents tuned, witness values climb almost monotonically. That pattern itself becomes the heuristic telling you where to search next. The data didn't disprove the hypothesis, but it let you see it: within reach, RH is 'barely' true, and the margin narrows in a highly orderly way.

带得走的想法是这个姿势:解不开一个大猜想,也可以把它「压」近一点——先找等价的可计算表述,再找候选数的结构,然后把随机搜索变成被数据引导的探索。哪怕最终反例不存在(大概率如此),沿途得到的分布规律和搜索策略,本身就是理解这个猜想的素材。这是一个程序员参与数学的正确方式:不冒充定理,只提供证据和直觉。The transferable idea is the posture: even if you can't solve a great conjecture, you can push it closer — find a computable equivalent statement, find the structure of candidates, turn random search into data-guided exploration. If no counterexample exists (likely), the distributional patterns and search strategies you build along the way are themselves material for understanding. A programmer's honest way into mathematics: not fake theorems, but evidence and intuition.

AI 思考AI Thoughts

数学之美Beauty of Math

每日 Lean 谜题 · 周日Daily Lean Puzzle · Sunday ★★★★★★★

IMO 1988 第六题:韦达跳跃法与整除之美IMO 1988 Problem 6: Vieta Jumping and the Beauty of Divisibility

设 $a$ 和 $b$ 为自然数,满足 $(a \cdot b + 1) \mid (a^2 + b^2)$。证明:$\frac{a^2 + b^2}{ab + 1}$ 是一个完全平方数。Let $a$ and $b$ be natural numbers such that $ab + 1$ divides $a^2 + b^2$. Show that $\frac{a^2 + b^2}{ab + 1}$ is a perfect square.

Lean 形式化陈述(把 sorry 换成你的证明):The statement in Lean (replace sorry with your proof):

/-
Copyright (c) 2019 Johan Commelin. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Johan Commelin
-/

import Mathlib.Data.Nat.Prime.Basic
import Mathlib.Data.Rat.Defs
import Mathlib.Order.WellFounded
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.Ring
import Mathlib.Tactic.WLOG

/-!
# International Mathematical Olympiad 1988, Problem 6

If a and b are two natural numbers such that a*b+1 divides a^2 + b^2,
show that their quotient is a perfect square.
-/

namespace Imo1988P6

theorem imo1988_p6 {a b : ℕ} (h : a * b + 1 ∣ a ^ 2 + b ^ 2) :
    ∃ d, d ^ 2 = (a ^ 2 + b ^ 2) / (a * b + 1) := by
  sorry

end Imo1988P6

在浏览器中挑战 ▶Try it in your browser ▶ 下载题目 .leanDownload puzzle .lean

提示Hint

令 $k = \frac{a^2 + b^2}{ab + 1}$,把条件重写为关于 $a$ 的二次方程 $a^2 - kba + b^2 - k = 0$。韦达定理给出另一个根 $a' = kb - a$,它也是整数,且 $aa' = b^2 - k$。在所有解中取 $a + b$ 最小的一对:如果 $a'$ 还是正整数,你就得到一个更小的解,矛盾;所以唯一的出路是 $a' \le 0$——而 $a' = 0$ 恰好给出 $k = b^2$,即结论本身。Set $k = \frac{a^2 + b^2}{ab + 1}$ and rewrite the condition as the quadratic $a^2 - kba + b^2 - k = 0$ in $a$. Vieta's formulas give the other root $a' = kb - a$, which is also an integer, with $aa' = b^2 - k$. Pick the solution with minimal $a + b$: if $a'$ is still a positive integer you get a smaller solution, a contradiction; so the only escape is $a' \le 0$ — and $a' = 0$ hands you $k = b^2$, which is exactly the conclusion.

答案与讲解Solution & walkthrough
  1. 第一步,设定常数 $k$ 并建立二次方程。令 $k = \frac{a^2 + b^2}{ab + 1}$,它是正整数。把整除条件改写为 $a^2 - k \cdot b \cdot a + (b^2 - k) = 0$。这是一个以 $a$ 为变量的二次方程,其系数只依赖 $b$ 和 $k$。Step 1, set up the constant $k$ and the quadratic. Let $k = \frac{a^2 + b^2}{ab + 1}$, a positive integer. Rewrite the divisibility as $a^2 - kba + (b^2 - k) = 0$. This is a quadratic in $a$ whose coefficients depend only on $b$ and $k$.
  2. 第二步,用韦达定理找出另一个根。设方程的两个根为 $a$ 和 $a'$,则 $a + a' = kb$ 且 $a \cdot a' = b^2 - k$。由第一个等式得 $a' = kb - a$,这是整数(因为 $a, k, b$ 都是整数);它同时是二次方程的根,所以 $(a', b)$ 也满足 $a'^2 + b^2 = k(a'b + 1)$——只要 $a'$ 是非负整数,它就是一组新解。Step 2, use Vieta's formulas to find the other root. Let the two roots be $a$ and $a'$. Then $a + a' = kb$ and $a \cdot a' = b^2 - k$. From the first, $a' = kb - a$ is an integer; since it solves the same quadratic, $(a', b)$ also satisfies $a'^2 + b^2 = k(a'b + 1)$ — so whenever $a'$ is a nonnegative integer it is a fresh solution.
  3. 第三步,最小性产生矛盾。固定 $k$,在所有满足条件的解 $(a, b)$ 中取 $a + b$ 最小的一对,不妨设 $a \ge b$。可以推出 $a' < a$(由 $a' = kb - a$ 结合 $a$ 是方程的较大根),所以如果 $a' > 0$,$(a', b)$ 就是和更小的一组解,与最小性矛盾。因此必有 $a' \le 0$;再结合 $aa' = b^2 - k$ 与 $a > 0$,得 $b^2 - k \le 0$。而 $a' < 0$ 会导致 $a'b + 1 < 0$ 或等式 $a'^2 + b^2 = k(a'b+1)$ 两边符号冲突,排除掉。Step 3, minimality produces the contradiction. Fix $k$ and pick the solution $(a, b)$ minimizing $a + b$, say $a \ge b$. One can show $a' < a$ (from $a' = kb - a$ and $a$ being the larger root), so if $a' > 0$ then $(a', b)$ is a smaller solution — contradiction. Hence $a' \le 0$; combined with $aa' = b^2 - k$ and $a > 0$ this forces $b^2 - k \le 0$, and the case $a' < 0$ breaks the sign balance of $a'^2 + b^2 = k(a'b + 1)$.
  4. 第四步,边界即结论。剩下唯一可能是 $a' = 0$,代入 $aa' = b^2 - k$ 得 $k = b^2$——完全平方数,正是要证的东西。另外两个平凡入口直接验证即可:若 $b = 0$,商为 $\frac{a^2}{1} = a^2$,本身就是平方数;若 $a = b$,则 $k = \frac{2a^2}{a^2 + 1}$,只有 $a^2 + 1$ 整除 $2a^2$(即 $a = 1$,$k = 1 = 1^2$)时才成立。于是对任意满足条件的 $(a, b)$,$k$ 必为完全平方数。Step 4, the boundary is the conclusion. The only survivor is $a' = 0$, and $aa' = b^2 - k$ then gives $k = b^2$ — a perfect square, exactly what we wanted. The trivial entrances check directly: if $b = 0$ the quotient is $\frac{a^2}{1} = a^2$; if $a = b$ then $k = \frac{2a^2}{a^2 + 1}$, an integer only when $a = 1$ (giving $k = 1 = 1^2$). So $k$ is a perfect square for every valid $(a, b)$.
/-
Copyright (c) 2019 Johan Commelin. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Johan Commelin
-/

import Mathlib.Data.Nat.Prime.Basic
import Mathlib.Data.Rat.Defs
import Mathlib.Order.WellFounded
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.Ring
import Mathlib.Tactic.WLOG

/-!
# International Mathematical Olympiad 1988, Problem 6

If a and b are two natural numbers such that a*b+1 divides a^2 + b^2,
show that their quotient is a perfect square.
-/

namespace Imo1988P6

/-
Question 6 of IMO1988 is somewhat (in)famous. Several expert problem solvers
could not tackle the question within the given time limit.
The problem lead to the introduction of a new proof technique,
so called “Vieta jumping”.

In this file we formalise constant descent Vieta jumping,
and apply this to prove P6 of IMO1988.
To illustrate the technique, we also prove a similar result.
-/

/-- Constant descent Vieta jumping.

This proof technique allows one to prove an arbitrary proposition `claim`,
by running a descent argument on a hyperbola `H` in the first quadrant of the plane,
under the following conditions:

* `h₀`     : There exists an integral point `(x,y)` on the hyperbola `H`.
* `H_symm` : The hyperbola has a symmetry along the diagonal in the plane.
* `H_zero` : If an integral point `(x,0)` lies on the hyperbola `H`, then `claim` is true.
* `H_diag` : If an integral point `(x,x)` lies on the hyperbola `H`, then `claim` is true.
* `H_desc` : If `(x,y)` is an integral point on the hyperbola `H`,
with `x < y` then there exists a “smaller” point on `H`: a point `(x',y')` with `x' < y' ≤ x`.

For reasons of usability, the hyperbola `H` is implemented as an arbitrary predicate.
(In question 6 of IMO1988, where this proof technique was first developped,
the predicate `claim` would be `∃ (d : ℕ), d ^ 2 = k` for some natural number `k`,
and the predicate `H` would be `fun a b ↦ a * a + b * b = (a * b + 1) * k`.)

To ensure that the predicate `H` actually describes a hyperbola,
the user must provide arguments `B` and `C` that are used as coefficients for a quadratic equation.
Finally, `H_quad` is the proof obligation that the quadratic equation
  `(y:ℤ) * y - B x * y + C x = 0`
describes the same hyperbola as the predicate `H`.

For extra flexibility, one must provide a predicate `base` on the integral points in the plane.
In the descent step `H_desc` this will give the user the additional assumption that
the point `(x,y)` does not lie in this base locus.
The user must provide a proof that the proposition `claim` is true
if there exists an integral point `(x,y)` on the hyperbola `H` that lies in the base locus.
If such a base locus is not necessary, once can simply let it be `fun x y ↦ False`.
-/
theorem constant_descent_vieta_jumping (x y : ℕ) {claim : Prop} {H : ℕ → ℕ → Prop} (h₀ : H x y)
    (B : ℕ → ℤ) (C : ℕ → ℤ) (base : ℕ → ℕ → Prop)
    (H_quad : ∀ {x y}, H x y ↔ (y : ℤ) * y - B x * y + C x = 0) (H_symm : ∀ {x y}, H x y ↔ H y x)
    (H_zero : ∀ {x}, H x 0 → claim) (H_diag : ∀ {x}, H x x → claim)
    (H_desc : ∀ {x y}, 0 < x → x < y → ¬base x y → H x y →
      ∀ y', y' * y' - B x * y' + C x = 0 → y' = B x - y → y' * y = C x → 0 ≤ y' ∧ y' ≤ x)
    (H_base : ∀ {x y}, H x y → base x y → claim) : claim := by
  -- First of all, we may assume that x ≤ y.
  -- We justify this using H_symm.
  wlog hxy : x ≤ y
  · rw [H_symm] at h₀; apply this y x h₀ B C base _ _ _ _ _ _ (le_of_not_ge hxy); assumption'
  -- In fact, we can easily deal with the case x = y.
  by_cases x_eq_y : x = y
  · subst x_eq_y; exact H_diag h₀
  -- Hence we may assume that x < y.
  replace hxy : x < y := lt_of_le_of_ne hxy x_eq_y
  clear x_eq_y
  -- Consider the upper branch of the hyperbola defined by H.
  let upper_branch : Set (ℕ × ℕ) := {p | H p.1 p.2 ∧ p.1 < p.2}
  -- Note that the point p = (x,y) lies on the upper branch.
  let p : ℕ × ℕ := ⟨x, y⟩
  have hp : p ∈ upper_branch := ⟨h₀, hxy⟩
  -- We also consider the exceptional set of solutions (a,b) that satisfy
  -- a = 0 or a = b or B a = b or B a = b + a or that lie in the base locus.
  let exceptional : Set (ℕ × ℕ) :=
    {p | H p.1 p.2 ∧ (base p.1 p.2 ∨ p.1 = 0 ∨ p.1 = p.2 ∨ B p.1 = p.2 ∨ B p.1 = p.2 + p.1)}
  -- Let S be the projection of the upper branch on to the y-axis
  -- after removing the exceptional locus.
  let S : Set ℕ := Prod.snd '' (upper_branch \ exceptional)
  -- The strategy is to show that the exceptional locus in nonempty
  -- by running a descent argument that starts with the given point p = (x,y).
  -- Our assumptions ensure that we can then prove the claim.
  suffices exc : exceptional.Nonempty by
    -- Suppose that there exists an element in the exceptional locus.
    simp only [Set.Nonempty, Prod.exists, Set.mem_ofPred_eq, exceptional] at exc
    -- Let (a,b) be such an element, and consider all the possible cases.
    rcases exc with ⟨a, b, hH, hb⟩
    rcases hb with (_ | rfl | rfl | hB | hB)
    -- The first three cases are rather easy to solve.
    · solve_by_elim
    · rw [H_symm] at hH; solve_by_elim
    · solve_by_elim
    -- The final two cases are very similar.
    all_goals
      -- Consider the quadratic equation that (a,b) satisfies.
      rw [H_quad] at hH
      -- We find the other root of the equation, and Vieta's formulas.
      rcases vieta_formula_quadratic hH with ⟨c, h_root, hV₁, hV₂⟩
      -- By substitutions we find that b = 0 or b = a.
      simp only [hB, add_eq_left, add_right_inj] at hV₁
      subst hV₁
      rw [← Int.ofNat_zero] at *
      rw [← H_quad] at h_root
      -- And hence we are done by H_zero and H_diag.
      solve_by_elim
  -- To finish the main proof, we need to show that the exceptional locus is nonempty.
  -- So we assume that the exceptional locus is empty, and work towards deriving a contradiction.
  rw [Set.nonempty_iff_ne_empty]
  intro exceptional_empty
  -- Observe that S is nonempty.
  have S_nonempty : S.Nonempty := by
    -- It contains the image of p.
    use p.2
    apply Set.mem_image_of_mem
    -- After all, we assumed that the exceptional locus is empty.
    rwa [exceptional_empty, Set.sdiff_empty]
  -- We are now set for an infinite descent argument.
  -- Let m be the smallest element of the nonempty set S.
  let m : ℕ := WellFounded.min Nat.lt_wfRel.wf S S_nonempty
  have m_mem : m ∈ S := WellFounded.min_mem Nat.lt_wfRel.wf S S_nonempty
  have m_min : ∀ k ∈ S, ¬k < m := fun k hk => WellFounded.not_lt_min Nat.lt_wfRel.wf S hk
  -- It suffices to show that there is point (a,b) with b ∈ S and b < m.
  rsuffices ⟨p', p'_mem, p'_small⟩ : ∃ p' : ℕ × ℕ, p'.2 ∈ S ∧ p'.2 < m
  · solve_by_elim
  -- Let (m_x, m_y) be a point on the upper branch that projects to m ∈ S
  -- and that does not lie in the exceptional locus.
  rcases m_mem with ⟨⟨mx, my⟩, ⟨⟨hHm, mx_lt_my⟩, h_base⟩, m_eq⟩
  -- This means that m_y = m,
  -- and the conditions H(m_x, m_y) and m_x < m_y are satisfied.
  simp only at mx_lt_my hHm m_eq
  simp only [exceptional, hHm, Set.mem_ofPred_eq, true_and] at h_base
  push Not at h_base
  -- Finally, it also means that (m_x, m_y) does not lie in the base locus,
  -- that m_x ≠ 0, m_x ≠ m_y, B(m_x) ≠ m_y, and B(m_x) ≠ m_x + m_y.
  rcases h_base with ⟨h_base, hmx, hm_diag, hm_B₁, hm_B₂⟩
  replace hmx : 0 < mx := pos_iff_ne_zero.mpr hmx
  -- Consider the quadratic equation that (m_x, m_y) satisfies.
  have h_quad := hHm
  rw [H_quad] at h_quad
  -- We find the other root of the equation, and Vieta's formulas.
  rcases vieta_formula_quadratic h_quad with ⟨c, h_root, hV₁, hV₂⟩
  -- Now we rewrite Vietas formulas a bit, and apply the descent step.
  replace hV₁ : c = B mx - my := eq_sub_of_add_eq' hV₁
  rw [mul_comm] at hV₂
  have Hc := H_desc hmx mx_lt_my h_base hHm c h_root hV₁ hV₂
  -- This means that we may assume that c ≥ 0 and c ≤ m_x.
  obtain ⟨c_nonneg, c_lt⟩ := Hc
  -- In other words, c is a natural number.
  lift c to ℕ using c_nonneg
  -- Recall that we are trying find a point (a,b) such that b ∈ S and b < m.
  -- We claim that p' = (c, m_x) does the job.
  let p' : ℕ × ℕ := ⟨c, mx⟩
  use p'
  -- The second condition is rather easy to check, so we do that first.
  constructor; swap
  · rwa [m_eq] at mx_lt_my
  -- Now we need to show that p' projects onto S. In other words, that c ∈ S.
  -- We do that, by showing that it lies in the upper branch
  -- (which is sufficient, because we assumed that the exceptional locus is empty).
  apply Set.mem_image_of_mem
  rw [exceptional_empty, Set.sdiff_empty]
  -- Now we are ready to prove that p' = (c, m_x) lies on the upper branch.
  -- We need to check two conditions: H(c, m_x) and c < m_x.
  constructor
  · -- The first condition is not so hard. After all, c is the other root of the quadratic equation.
    rw [H_symm, H_quad]
    simpa using h_root
  · -- For the second condition, we note that it suffices to check that c ≠ m_x.
    lia

theorem imo1988_p6 {a b : ℕ} (h : a * b + 1 ∣ a ^ 2 + b ^ 2) :
    ∃ d, d ^ 2 = (a ^ 2 + b ^ 2) / (a * b + 1) := by
  rcases h with ⟨k, hk⟩
  rw [hk, Nat.mul_div_cancel_left _ (Nat.succ_pos (a * b))]
  simp only [sq] at hk
  apply constant_descent_vieta_jumping a b (H := fun a b => a * a + b * b = (a * b + 1) * k)
      hk (fun x => k * x) (fun x => x * x - k) fun _ _ => False <;>
    clear hk a b
  · -- We will now show that the fibers of the solution set are described by a quadratic equation.
    lia
  · -- Show that the solution set is symmetric in a and b.
    intro x y
    simp [add_comm (x * x), mul_comm x]
  · -- Show that the claim is true if b = 0.
    suffices ∀ a, a * a = k → ∃ d, d * d = k by simpa [sq]
    rintro x rfl; use x
  · -- Show that the claim is true if a = b.
    intro x hx
    suffices k ≤ 1 by
      rw [Nat.le_add_one_iff, Nat.le_zero] at this
      rcases this with (rfl | rfl)
      · use 0; simp
      · use 1; simp
    contrapose! hx with k_lt_one
    apply ne_of_lt
    calc
      x * x + x * x = x * x * 2 := by rw [mul_two]
      _ ≤ x * x * k := (Nat.mul_le_mul_left (x * x) k_lt_one)
      _ < (x * x + 1) * k := by linarith
  · -- Show the descent step.
    intro x y hx x_lt_y _ _ z h_root _ hV₀
    constructor
    · have hpos : z * z + x * x > 0 := by
        apply add_pos_of_nonneg_of_pos
        · apply mul_self_nonneg
        · positivity
      have hzx : z * z + x * x = (z * x + 1) * k := by
        rw [← sub_eq_zero, ← h_root]
        ring
      rw [hzx] at hpos
      replace hpos : z * x + 1 > 0 := pos_of_mul_pos_left hpos (Int.natCast_nonneg k)
      replace hpos : z * x ≥ 0 := Int.le_of_lt_add_one hpos
      apply nonneg_of_mul_nonneg_left hpos (mod_cast hx)
    · contrapose! hV₀ with x_lt_z
      apply ne_of_gt
      calc
        z * y > x * x := by apply mul_lt_mul' <;> lia
        _ ≥ x * x - k := sub_le_self _ (Int.natCast_nonneg k)
  · -- There is no base case in this application of Vieta jumping.
    simp

/-
The following example illustrates the use of constant descent Vieta jumping
in the presence of a non-trivial base case.
-/
example {a b : ℕ} (h : a * b ∣ a ^ 2 + b ^ 2 + 1) : 3 * a * b = a ^ 2 + b ^ 2 + 1 := by
  rcases h with ⟨k, hk⟩
  suffices k = 3 by simp_all; ring
  simp only [sq] at hk
  apply constant_descent_vieta_jumping a b (H := fun a b => a * a + b * b + 1 = a * b * k)
      hk (fun x => k * x) (fun x => x * x + 1) fun x _ => x ≤ 1 <;>
    clear hk a b
  · lia
  · -- Show that the solution set is symmetric in a and b.
    intro x y; ring_nf -- Porting note: Originally, `cc` solved the entire goal
  · -- Show that the claim is true if b = 0.
    simp
  · -- Show that the claim is true if a = b.
    intro x hx
    have x_sq_dvd : x * x ∣ x * x * k := dvd_mul_right (x * x) k
    rw [← hx] at x_sq_dvd
    obtain ⟨y, hy⟩ : x * x ∣ 1 := by simpa only [Nat.dvd_add_self_left, add_assoc] using x_sq_dvd
    obtain ⟨rfl, rfl⟩ : x = 1 ∧ y = 1 := by simpa [mul_eq_one] using hy.symm
    simpa using hx.symm
  · -- Show the descent step.
    intro x y _ hx h_base _ z _ _ hV₀
    constructor
    · have zy_pos : z * y ≥ 0 := by rw [hV₀]; exact mod_cast Nat.zero_le _
      apply nonneg_of_mul_nonneg_left zy_pos
      lia
    · contrapose! hV₀ with x_lt_z
      apply ne_of_gt
      push Not at h_base
      calc
        z * y > x * y := by apply mul_lt_mul_of_pos_right <;> lia
        _ ≥ x * (x + 1) := by apply mul_le_mul <;> lia
        _ > x * x + 1 := by
          rw [mul_add, mul_one]
          apply add_lt_add_right
          assumption_mod_cast
  · -- Show the base case.
    intro x y h h_base
    obtain rfl | rfl : x = 0 ∨ x = 1 := by rwa [Nat.le_add_one_iff, Nat.le_zero] at h_base
    · simp at h
    · rw [mul_one, one_mul, add_right_comm] at h
      have y_dvd : y ∣ y * k := dvd_mul_right y k
      rw [← h, Nat.dvd_add_left (dvd_mul_left y y)] at y_dvd
      obtain rfl | rfl := (Nat.dvd_prime Nat.prime_two).mp y_dvd <;> apply mul_left_cancel₀
      exacts [one_ne_zero, h.symm, two_ne_zero, h.symm]

end Imo1988P6

运行答案 ▶Run the solution ▶ 下载答案 .leanDownload solution .lean

人的思考A human's take

AoPS Wiki: 1988 IMO Problems/Problem 6(韦达跳跃法的经典讨论页) — AoPS Wiki 社区(含 multiple solutions 与视频讲解)

这是 AoPS 维基上该题的页面,收录了多种成文解答和两段视频讲解。最标准的解法(页面 Solution 1)结构是:令商为 $k$,固定 $k$,在所有满足 $a^2 - kba + b^2 - k = 0$ 的自然数对 $(a, b)$ 中取 $a + b$ 最小的一组;由韦达定理,另一根 $a' = kb - a$ 也是整数且与 $b$ 组成新解。若 $0 < a' < a$,最小性被推翻;若 $a' < 0$,等式 $a'^2 + b^2 = k(a'b + 1)$ 的符号不成立;于是只剩 $a' = 0$,而 $aa' = b^2 - k$ 立即给出 $k = b^2$。This is the AoPS Wiki page for the problem, collecting several written solutions and two video walkthroughs. The standard one (Solution 1) runs: call the quotient $k$; fix $k$ and choose a pair $(a, b)$ of natural numbers with minimal $a + b$ solving $a^2 - kba + b^2 - k = 0$. By Vieta's formulas the other root $a' = kb - a$ is an integer that forms a new solution with $b$. If $0 < a' < a$, minimality is violated; if $a' < 0$, the identity $a'^2 + b^2 = k(a'b + 1)$ has the wrong sign; so only $a' = 0$ survives, and $aa' = b^2 - k$ then gives $k = b^2$.

页面的讨论清晰地展示了这道题为什么难:从题面到「把它看成二次方程」之间没有自然的桥梁,选手必须在考场上自己想到「固定商、最小化、跳根」这条三步路。韦达跳跃成为竞赛标准技巧,正是因为这道题把它的每个环节都逼到了极限。The page's discussion makes clear why the problem is so hard: nothing in the statement hints at 'read it as a quadratic' — the solver must find the three-step path (fix the quotient, minimize, jump the root) alone under exam conditions. Vieta jumping became standard olympiad equipment precisely because this problem pushes each of its steps to the limit.

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道题是 1988 年国际数学奥林匹克(IMO)的第 6 题,历史上公认最难的竞赛题之一:当年 518 名选手中只有 6 人拿到满分。它催生了一种此后成为竞赛标配的证明技巧——韦达跳跃(Vieta jumping),名字来自解题核心所依赖的韦达定理(二次方程根与系数的关系),并在 AoPS 等竞赛社区被系统整理和传播。This was Problem 6 of the 1988 International Mathematical Olympiad and is remembered as one of the hardest competition problems ever set: of the 518 contestants that year, only 6 achieved a perfect score. It gave birth to a technique — Vieta jumping — that has since become standard equipment in olympiad arsenals. The name comes from what the argument leans on, Vieta's formulas relating the roots of a quadratic to its coefficients; the technique was systematized and spread through the competition community, AoPS above all.

解题的关键洞察是「把整除条件重新解释为一个二次方程」。$a^2 + b^2 = k(ab + 1)$ 表面看是一条关于两个变量的对称关系,但一旦固定 $k$,它就变成了关于 $a$ 的二次曲线——而韦达定理恰好提供了从一组解跳到另一组解的梯子。这种「固定一个参数、把条件视为方程」的技巧在数论中屡见不鲜,但在这里它被推向了极致:梯子的每一步都带你向下,直到撞上边界($a' = 0$),而那个边界恰恰就是你想证明的结论。The key insight is to reinterpret the divisibility condition as a quadratic equation. $a^2 + b^2 = k(ab + 1)$ looks like a symmetric relation between two variables, but once $k$ is fixed it becomes a quadratic curve in $a$ — and Vieta's formulas provide exactly the ladder that lets you jump from one solution to another. This move (fix a parameter, read the condition as an equation) appears throughout number theory, but here it is pushed to its limit: every rung of the ladder takes you downward, until you hit a boundary ($a' = 0$), and that boundary is precisely where the desired conclusion lives.

韦达跳跃的精髓在于「在离散结构上递降」——在整数格点上,你不可能无限下降。这让人联想到良序原则:任何非空自然数集合都有最小元。在程序员的语境中,这像是一个循环不变量论证:每次迭代(跳跃)都让某个度量($a + b$)严格减小,而度量的下界保证了循环必然终止;终止时的状态,恰好给出了你想要证明的结论。The essence of Vieta jumping is descent on a discrete structure — you cannot descend forever on the integer lattice. This echoes the well-ordering principle: every nonempty set of natural numbers has a least element. In a programmer's idiom, it is a loop-invariant argument: each iteration (jump) strictly decreases some measure ($a + b$), and the lower bound guarantees termination. The state at termination is exactly the conclusion you wanted to prove.

这道题还有一层更深的审美:它展示了看似随机的整除条件背后隐藏的刚性结构。商 $k = \frac{a^2 + b^2}{ab + 1}$ 最初看起来像个自由参数——你可以任取 $a$ 和 $b$,$k$ 的值似乎没有约束。但证明告诉我们 $k$ 不自由:它必须是完全平方数。这种「约束的涌现」是数论最令人愉悦的现象之一:表面的随机性之下,藏着严格的算术律。There is a deeper aesthetic at play: the problem reveals rigid structure lurking beneath an apparently free divisibility condition. The quotient $k = \frac{a^2 + b^2}{ab + 1}$ initially looks unconstrained — pick $a$ and $b$ at will. But the proof shows $k$ is never free: it must be a perfect square. This emergence of constraint is one of number theory's most delightful phenomena — beneath surface randomness, strict arithmetic law waits to be found.

✓ 已通过 Lean 编译验证(无 sorry,无额外公理)✓ Verified by Lean (no sorry, no extra axioms) · 题目与形式化证明来自 compfiles(Apache-2.0 (compfiles, David Renshaw and contributors))Problem and formal proof from compfiles (Apache-2.0 (compfiles, David Renshaw and contributors)) · Lean v4.35.0-rc3 · Mathlib 3f6737d

程序员随想Programmer Reflections

哲学与生活Philosophy & Life

工具角Tools Corner