跳到主要内容

Lean 数论库

Lean 是一个功能强大的交互式定理证明器，广泛用于形式化数学和编程验证。Lean 的数论库（mathlib 中的数论部分）为研究数论提供了丰富的工具和定义。本文将带你了解 Lean 数论库的基础知识，并通过示例展示如何在实际中使用它。

什么是数论？​

数论是数学的一个分支，研究整数的性质及其相互关系。它涉及素数、整除性、模运算、同余等概念。Lean 的数论库提供了这些概念的严格定义和证明工具，使我们能够在计算机中形式化数论问题。

Lean 数论库的核心概念​

1. 整数的定义与基本操作​

在 Lean 中，整数类型为 ℤ（Unicode 符号表示）。我们可以使用 Lean 的标准库对整数进行基本操作，例如加法、乘法和取模运算。

-- 定义两个整数
def a : ℤ := 5
def b : ℤ := 3

-- 加法
#eval a + b  -- 输出: 8

-- 乘法
#eval a * b  -- 输出: 15

-- 取模运算
#eval a % b  -- 输出: 2

2. 素数与整除性​

素数是数论的核心概念之一。Lean 提供了 nat.prime 谓词来判断一个自然数是否为素数。

import data.nat.prime

-- 判断一个数是否为素数
#eval nat.prime 7  -- 输出: true
#eval nat.prime 10 -- 输出: false

整除性可以通过 ∣ 符号表示。例如，a ∣ b 表示 a 整除 b。

-- 判断整除性
#eval 3 ∣ 9  -- 输出: true
#eval 4 ∣ 10 -- 输出: false

3. 同余与模运算​

同余是数论中另一个重要概念。在 Lean 中，可以使用 ≡ 符号表示同余关系。

-- 定义同余关系
example : 7 ≡ 1 [MOD 3] :=
begin
  rw int.modeq_iff_dvd,  -- 将同余转换为整除关系
  use 2,                 -- 7 - 1 = 6，6 是 3 的倍数
  norm_num,
end

实际案例：验证费马小定理​

费马小定理是数论中的一个经典定理，它指出：如果 p 是一个素数，且 a 不是 p 的倍数，则 a^(p-1) ≡ 1 [MOD p]。

我们可以使用 Lean 来验证这个定理。

import data.nat.prime
import tactic

-- 费马小定理的验证
theorem fermat_little_theorem (p : ℕ) (hp : nat.prime p) (a : ℤ) (ha : ¬(p ∣ a)) :
  a^(p-1) ≡ 1 [MOD p] :=
begin
  -- 使用数论库中的费马小定理证明
  exact int.modeq_fermat_little hp ha,
end
提示

提示：Lean 的数论库已经内置了许多经典定理的证明，例如费马小定理。你可以直接调用这些定理，而不需要从头开始证明。

总结​

Lean 的数论库为研究数论提供了强大的工具。通过本文，你已经学习了如何在 Lean 中定义整数、判断素数、验证整除性和同余关系，并实际应用了费马小定理。

附加资源与练习​

资源​

练习​

  1. 使用 Lean 验证 17 是一个素数。
  2. 编写一个 Lean 函数，判断一个整数是否为偶数。
  3. 尝试证明：如果 a ≡ b [MOD m] 且 c ≡ d [MOD m]，则 a + c ≡ b + d [MOD m]。

通过不断练习和探索，你将能够更深入地理解 Lean 数论库的强大功能，并将其应用于更复杂的数学问题中！