[潘承洞、潘承彪《初等数论》]

整数

自然数又叫正整数, 即熟知的 `1, 2, 3, cdots, n, cdots`. 用 `NN` 表示全体自然数的集合.
整数是指正整数, 负整数及零, 即 `0, +-1, +-2, +-3, cdots, +-n, cdots`. 用 `ZZ` 表示全体整数的集合.

整数的运算

    整数集合 `ZZ` 关于其上的加法 "`+`" 与乘法 "`*`" 成一整环, 即
  1. 关于加法与乘法成一环.
      关于加法成一 Abel 群.
    1. 封闭性. `(AA a, b in ZZ)` `a + b in ZZ`;
    2. 结合律. `(AA a, b, c in ZZ)` `(a+b)+c = a+(b+c)`;
    3. 存在零元. `(EE 0 in ZZ)`, `(AA a in ZZ)` `a + 0 = a`;
    4. 存在负元. `(AA a in ZZ)`, `(EE -a in ZZ)` `a + (-a) = 0`;
    5. 交换律. `(AA a, b in ZZ)`, `a+b = b+a`;
      6. 关于乘法成一半群.
    6. 封闭性. `(AA a, b in ZZ)` `a * b in ZZ`;
    7. 结合律. `(AA a, b, c in ZZ)` `(a*b)*c = a*(b*c)`;
      8. 满足乘法对加法的分配律:
    8. `(AA a, b, c in ZZ)` `a * (b + c) = a*b + a*c`.
  2. 无零因子. `(AA a, b in ZZ)` `a * b = 0 rArr a = 0 or b = 0`;
  3. 乘法交换律. `(AA a, b in ZZ)` `a*b = b*a`;
  4. 有乘法幺元. `(EE 1 in ZZ)` `(AA a in ZZ)` `a * 1 = a`; 但是, 不一定有乘法逆元.
    5. 因此, 也称 `ZZ` 为整数环. 简单起见, 字母间的乘法 `a*b` 简记为 `ab`, 减法 `a + (-b)` 简记为 `a-b`.

从整数乘法的无零因子可以推出它满足的消去律: `(AA a in ZZ\\{0}, b, c in ZZ)` `a*b = a*c rArr b = c`.

整数的序

    整数环 `ZZ` 上有一全序 `le`, 即满足
  1. `le` 为一偏序.
    1. 自反性. `(AA a in ZZ)` `a le a`;
    2. 反对称性. `(AA a, b in ZZ)` `a le b and b le a rArr a = b`;
    3. 传递性. `(AA a, b, c in ZZ)` `a le b and b le c rArr a le c`.
    据此可以定义 `ge, lt, gt` 如下: 对 `a, b in ZZ`, `a ge b iff b le a`;
    `a lt b iff a le b and a != b`;
    `a gt b iff a ge b and a != b`.
  2. 任意两个整数之间可以比较大小. `AA a, b in ZZ`, `a=b, a lt b, a gt b` 有且仅有一个成立.
    全序 `le` 与 `ZZ` 上的运算相容, 即
  1. `(AA a, b, c in ZZ)` `a + c le b + c iff a le b`;
  2. `(AA a, b in ZZ, c in NN)` `a c le b c iff a le b`;
  3. `(AA a, b in ZZ)` `a le b iff -a ge -b`;
    一些额外的性质
  1. `(AA a, b, c in NN)` `c = ab rArr a le c`, 等号成立当且仅当 `b = 1`.
  2. `(AA a, b in NN)` `a lt b iff a + 1 le b iff a le b-1`.

整数的绝对值

对任意 `a in ZZ`, 定义它的绝对值为 `|a| = { a, if a in NN; 0, if a = 0; -a, if -a in NN; :}`

    借助绝对值容易建立等价关系 `~: a ~ b iff |a| = |b|`, 满足
  1. 自反性. `(AA a in ZZ)` `a ~ a`;
  2. 对称性. `a ~ b rArr b ~ a`;
  3. 传递性. `a ~ b and b ~ c rArr a ~ c`.

绝对值具有性质 `|ab| = |a| * |b|`, `AA a, b in ZZ`;
`|a + b| le |a| + |b|`. `AA a, b in ZZ`.

归纳原理与数学归纳法

    归纳原理 设 `S sube NN` 满足条件
  1. `1 in S`;
  2. `n in S rArr n+1 in S`, `AA n ge 1`,
    3. 则 `S = NN`.

归纳原理是自然数最重要, 最本质的性质.

    (第一) 数学归纳法 设 `P(n)` 是关于自然数 `n` 的一种性质或命题. 如果
  1. `P(1)` 成立;
  2. 由 `P(n)` 成立可以推出 `P(n+1)` 成立, `AA n ge 1`,
    3. 那么 `P(n)` 对任意的自然数 `n` 成立.

对集合 `S = {n in NN: P(n)}` 应用归纳原理即得.

  1. 最小自然数原理 `NN` 的任意非空子集中存在最小元;
  2. 最大自然数原理 `NN` 的任意非空且在 `NN` 中有上界的子集中存在最大元.
  1. 设 `O/ != S sube NN`, 要证 `(EE m in S)` `(AA s in S)` `m le s`. 令 `L` 是 `S` 的全体下界, 即 `L = {l in NN: (AA s in S) l le s}`. 易知 `1 in L`, 故 `L` 非空.
    由于 `S` 非空, 取 `s in S`, 有 `s+1 gt s`. 所以 `s+1 !in L`, 这说明 `L != NN`. 由归纳原理, 存在 `m in L`, `m+1 !in L`.
    下证 `m in S`. 若不然, 则对任意 `s in S`, `m lt s`, 即 `m+1 le s`, 故 `m+1 in L`, 矛盾. `m` 即为 `S` 中的最小自然数.
  2. 设 `O/ != S sube NN` 且在 `NN` 中有上界, 要证 `(EE M in S)` `(AA s in S)` `s le M`. 令 `U = {u in NN: (AA s in S) s le u}` 是 `S` 的全体上界, 则 `U` 非空. 由最小自然数原理知, `U` 中有最小自然数 `M`. 下证 `M in S`, 若不然, 则对任意 `s in S`, `s lt M`, 即 `s le M-1`. 从而 `M-1 in U`, 与 `M` 是 `S` 的最小上界矛盾. `M` 即为 `S` 中的最大自然数.

从证明过程可以看出, 整数集合中的最小自然数与最大自然数分别等于其下确界与上确界.

    第二数学归纳法 设 `P(n)` 是关于自然数 `n` 的一种性质或命题. 如果
  1. `P(1)` 成立;
  2. 由 `P(m)` 对任意自然数 `m lt n` 成立可以推出 `P(n)` 成立, `n gt 1`,
    3. 那么 `P(n)` 对任意的自然数 `n` 成立.

反设集合 `T = {t in NN: not P(t)}` 非空, 则它有最小元 `t_0`, 由 `P(1)` 成立知 `t_0 gt 1`, 于是对任意自然数 `m lt t_0`, `P(m)` 成立, 由2, 这蕴含 `P(t_0)` 成立, 矛盾.

有理数与无理数

取整函数

阿基米德 (Archimedes) 原理 对任意实数 `a` 和 `epsi gt 0`, 存在正整数 `n` 使得 `n epsi gt a`.

考虑集合 `S = { n epsi | n in ZZ^+ }`. 若不存在正整数 `n` 使得 `n epsi gt a`, 那么 `a` 是 `S` 的上界; 由确界原理, 可设 `S` 的上确界为 `A`. 则存在 `n_0 epsi in S` 使得 `n_0 epsi gt A - epsi`, 即 `(n_0+1) epsi gt A`. 但 `(n_0+1) epsi in S`, 这与 `A` 是 `S` 的上确界矛盾.

任意给定实数 `x`, 都存在整数 `m, n` 满足 `m lt x lt n`.

在 Archimedes 原理中特别取 `epsi = 1` 知, 任意给定一个实数 `x`, 总能找到一个正整数 `n` 大于它. 另一方面, 对于实数 `-x`, 存在正整数 `-m` 使得 `-m gt -x`. 综上 `m lt x lt n`.

    取整函数 对任意实数 `x`, 集合 `{n in ZZ| n ge x}` 和 `{m in ZZ| m le x}` 都非空, 且前者在 `ZZ` 中有下界, 后者在 `ZZ` 中有上界. 由此定义
  1. `x` 的向上取整 `|~ x ~|` 为不小于 `x` 的最小整数;
  2. `x` 的向下取整 `|__x__|` 为不大于 `x` 的最大整数, 又叫 `x` 的整数部分;
  3. `x` 的小数部分 `x mod 1 := x - |__x__|`.
  4. 有时我们也采用 Gauss 记号, 将 `x` 的整数部分与小数部分记作 `[x]` 和 `{x}`. 总之 `x = [x] + {x}`.

已知正整数 `c`, 求正整数 `n` 满足 `(n(n-1))/2 le c lt (n(n+1))/2`.

解二次不等式得 `(-1+sqrt(1+8c))/2 lt n le (1+sqrt(1+8c))/2`, 即 `n = |__(1+sqrt(1+8c))/2__|`. 注意分母为 2, 因此分子每变化 2, 才引起 `n` 的一次跳跃, 我们可以用取整平方根代替平方根, 即 `n = |__(1+|__sqrt(1+8c)__|)/2__|`.

抽屉原理

抽屉原理是初等数论常用的工具. 这可以由反证法得到.

抽屉原理 (鸽巢原理) 设 `n in NN`. 集合 `X` 有 `n+1` 个元素, 集合 `Y` 有 `n` 个元素, 则 `X` 到 `Y` 的映射一定不是单射. 换言之, 将 `n+1` 个物体放入 `n` 个盒子, 一定有一个盒子放入了两个或两个以上的物体.

有理数与循环小数 无限循环小数是有理数; 反之, 有理数 `m//n` 可以写成无限循环小数, 且循环节的长度小于分母 `n`. 因此, 一个数是无理数当且仅当它是无限不循环小数.

  1. 不妨设这个 `B` 进制小数 (`B gt 1`) 在区间 `[0, 1]` 中. 则它可以写成 `0.a_1 a_2 cdots a_k {:dot a:}_(k+1) cdots {:dot a:}_(k+p)`. 记 `m_1 = a_(k+1) cdots a_(k+p)` `= sum_(i=1)^p a_(k+i) B^(p-i)`. 原来的小数等于 `sum_(i=1)^k a_i B^-i + B^-k sum_(j=1)^oo B^(-p j) m_1` `= sum_(i=1)^k a_i B^-i + B^-k/(B^p-1) m_1`, 故是一个有理数.
  2. (证明参考初等数论的例题) 不妨设 `n gt 1`. 如果存在正整数 `k` 使得 `n | B^k`, 设 `B^k = n_1 n`, 则 `m//n = m n_1 // B^k` 是一个有限小数. 否则有 `n !| B^k`, `k = 0, 1, cdots, n-1`. 设 `B^k` 除以 `n` 的余数是 `r_k`, 则 `n` 个数 `r_0, r_1, cdots, r_(n-1)` 只能取 `1, 2, cdots, n-1` 这 `n-1` 个值. 由鸽巢原理, 必有两个余数相等, 设为 `r_i = r_j`, `0 le j lt i lt n`. 则 `n | B^i - B^j = B^j(B^(i-j)-1)`. 设 `d = i-j`, `B^j(B^d-1) = n n_2`, 则 `m/n = (m n_2)/(B^j(B^d-1))`. 记 `m_2 = m n_2`. 下面只需证 `m_2/(B^d-1)` 是循环小数. 我们只看小数部分, 不妨设 `0 le m_2/(B^d-1) le 1`, 于是 `0 le m_2 le B^d-1`. 将 `m_2` 表为 `B` 进制数 (在前面添加 0 直到有 `d` 位数) `m_2 = sum_(j=1)^d a_j B^(d-j) = a_1 a_2 cdots a_d`, 得到 `m_2/(B^d-1) = sum_(i=1)^oo B^(-d i) m_2` `= 0.a_1 a_2 cdots a_d a_1 a_2 cdots a_d cdots`. 这是循环节长度为 `d` 的循环小数, 其中 `d = i-j lt n`.

设整数 `n gt 1`. 证明: `H_n = sum_(j=1)^n 1/j` 不是整数.

    利用如下事实: 每个正整数 `j` 都可以唯一地写为 `j = 2^(m_j) a_j`, 其中 `m_j ge 0`, `a_j` 为奇数.
  1. 下证 `m_j` 在 `1 le j le n` 中有唯一的最大值 `m`. 设 `m_j = m_k = m`, `j le k`, 则 `k - j = 2^(m_k) a_k - 2^(m_j) a_j` `= 2^m (a_k - a_j)`, 其中 `a_k, a_j` 为奇数, 因此 `k - j` 为偶数. 若 `k - j gt 0`, 则它所含的 2 的次数大于 `m`, 矛盾; 因此 `k = j`.
  2. 设 `m = m_k = max_(1 le j le n) m_j`, `M = 2^(m-1) prod a_j`. 由 1. 知, `j = 2^(m_j) a_j | M` 当且仅当 `j != k`. 于是 `M H_n = sum M/j -= M/k (mod 1)` 上式右边不是整数, 因此左边也不能是整数, 证毕.

根式无理数

`sqrt 2` 是无理数.

(Euclid 的证明) 反设 `sqrt 2 = a//b`, `a, b` 是互素的整数. 两边平方得 `2b^2 = a^2`. `a^2 = 2b^2` 是偶数, 所以 `a` 也是偶数, 设 `a = 2n`, 于是 `2b^2 = (2n)^2`, `quad b^2 = 2n^2`. 应用同样的推理知 `b` 是偶数, 从而 `a`, `b` 有公因子 `2`. 矛盾.

记整系数多项式的有理根 (如果存在) 的最简分数为 `c//d`, 则 `d` 是首项系数的因子, `c` 是常数项的因子. 特别首项系数为一的整系数多项式, 其有理根 (如果存在) 必为整数, 且这个整数是常数项的因子.
例如 `d x - c` 的根为 `c//d`, 其中分母是首项的因子, 分子是常数项的因子.

设 `f(x) = a_n x^n + cdots + a_1 x_1 + a_0`. 将 `x = c//d` 代入, 两边同乘 `d^n` 得 `a_n c^n + cdots + a_1 c d^(n-1) + a_0 d^n = 0`, 从而 `d | a_n c^n`. 但 `(c, d) = 1`, 所以 `d | a_n`. 同理 `c | a_0 d^n rArr c | a_0`.

设 `n, k` 是正整数. 则 `root k n` 是整数或无理数. 因此, `sqrt 2, sqrt 5, sqrt 12, root 3 2` 都是无理数.

注意 `root k n` 是多项式 `x^k - n` 的根. 若它为有理数, 则必为整数.

显然 `n gt 1`, 设 `p` 是 `n` 的一个素因子, 且 `p^k !| n` (如果 `n` 的所有素因子的次数都至少是 `k`, 我们可以将它们同时从根号下提出, 比如 `sqrt 72 = 6 sqrt 2`, 这样就转化为证明 `sqrt 2` 是无理数了). 我们反设 `root k n = a//b`, `a, b` 互素. 下面证明 `a,b` 至少有公因子 `p`, 从而引出矛盾.
两边 `k` 次方得 `n b^k = a^k`, 于是 `p | a^k`, 这推出 `p | a`, 进而 `p^k | a^k = n b^k`. 因为 `n` 中含因子 `p` 的次数小于 `k`, 我们推出 `p | b^k`, 于是 `p | b`, 即 `p` 是 `a, b` 的公因子.

`a^n | b^n rArr a | b`.

设 `b^n = a^n d`, 则 `b/a = root n d` 是整数.

`a, b, k` 为正整数, `k` 无平方因子, 且 `a^2 | k b^2`. 证明: `a | b`.

因为我们可以从 `a^2 | k b^2` 两边同时约去 `a, b` 的最大公因数, 所以不妨设 `(a, b) = 1`. 于是 `a^2 | k`, 但 `k` 无平方因子, 得到 `a^2 = 1`, 从而 `a = 1`, `a | b`.

设 `a, b` 是两个不同的正整数, 若 `sqrt a, sqrt b` 有一个是无理数, 则 `sqrt a +- sqrt b` 都是无理数. 因此 `sqrt 2 + 1`, `sqrt 2 + sqrt 3`, `(sqrt 5-1)/2` 都是无理数.

记 `u, v = sqrt a +- sqrt b`, 则 `u v` 是有理数. 假设 `u, v` 中有一个有理数, 则 `u, v` 都是有理数, 从而 `sqrt a, sqrt b = (u+-v)//2` 都是有理数. 矛盾.

若 `a, b` 是大于 1 的正整数, `a, b` 互素, 则 `log_a b` 是无理数.

反设 `log_a b = m//n`, 则 `a^m = b^n`, 由 `a, b` 互素得 `a = b = 1`, 矛盾.

  1. 存在两个无理数 `a, b`, 使得 `a^b` 是有理数;
  2. 存在两个无理数 `a, b`, 使得 `(a b)/a^b` 是有理数.
    设 `s = sqrt 2`.
  1. 若 `s^s` 是有理数, 取 `a = b = s` 即得证. 否则 `s^s` 是无理数, 取 `a = s^s`, `b = s`, 有 `a^b = (s^s)^s = s^(s^2) = s^2 = 2`.
  2. 若 `s^(s+1)` 是有理数, 则 `s^s` 是无理数. 取 `a = s^s`, `b = s` 即得证. 否则 `s^(s+1)` 是无理数, 取 `a = s^(s+1)`, `b = s` 即得证.

第一小题的更具体的例子: `sqrt 2` 的 `log_2 9` 次方等于 `3`.

无理数 `e` 与 `pi`

[知乎] 利用 `"e" = sum_(n ge 0) 1/n!` 直接证明 `"e"` 是无理数.

反设 `"e" = a//b`, `a, b` 为正整数. 取正整数 `n gt b`, 则 `n! a` `= n! b "e"` `= b sum_(k=0)^n n!/k!` `+ b sum_(k ge n+1) n!/k!` `:= A + B`. 显然等式左端的 `n! a` 和右端第一项的 `A` 为整数, 所以第二项 `B` 也应该是整数. 然而 `0 lt B` `lt b sum_(k ge 1) 1/(n+1)^k` `= b/n lt 1`. 因此 `B` 不可能是整数, 矛盾.

    设 `n` 为正整数. 考虑多项式函数 `f(x) = x^n (1-x)^n // n!`:
  1. `f(x) = sum_(i=n)^(2n) c_i x^i//n!`, 其中 `c_i` 是整数.
  2. `0 lt f(x) lt 1//n!`, `AA x in (0, 1)`;
  3. `f^((m))(0)`, `f^((m))(1)` 都是整数, `m = 0, 1, 2, cdots`.

只证性质 3. 利用对称性 `f(x) = f(1-x)` 有 `f^((m))(1) = (-1)^m f^((m))(0)`, 因此只需证 `f^((m))(0)` 是整数. 事实上, `f^((m))(0) // m!` 等于 `f(x)` 的 `m` 次项系数 `c_m // n!`, 于是 `f^((m))(0) = c_m m! // n!`. 注意 `m lt n` 时 `c_m = 0`, 而 `m ge n` 时 `m! // n!` 为整数, 所以 `f^((m))(0)` 总是整数.

`AA k in ZZ^+`, `"e"^k` 是无理数.

假设存在正整数 `k`, 使 `"e"^k = a//b`, `a, b` 为正整数. 取正整数 `n` 使得 `n! gt a k^(2n+1)`, 构造微分方程 `F'(x) + k F(x) = k^(2n+1) f(x)`, 其中 `f` 是引理中定义的 `2n` 次多项式函数. 容易验证方程的一个解是 `F(x) = sum_(i ge 0) (-k)^(2n-i) f^((i))(x)`. 由于 `f` 是多项式, `F(x)` 实际只有有限项. 代入原方程得到 `"d"/dx["e"^(k x) F(x)]` `= "e"^(k x) (F'(x) + k F(x))` `= "e"^(k x) k^(2n+1) f(x)`. 两边乘以 `b` 再积分, `I = b int_0^1 "e"^(k x) k^(2n+1) f(x) dx` `= b "e"^k F(1) - b F(0)` `= a F(1) - b F(0)`. 根据引理的 3, `F(0)`, `F(1)` 均为整数, 因此 `I` 为整数. 又根据引理的 2, `0 lt I lt b "e"^k k^(2n+1) // n!` `= a k^(2n+1) // n!` `lt 1`, 所以 `I` 不可能为整数, 矛盾.

`AA q in QQ\\{0}`, `"e"^q` 是无理数.

先设 `q` 是正有理数, `q = a//b`, `a, b` 为正整数. 假如 `"e"^q` 为有理数, 则 `"e"^a = ("e"^q)^b` 也是有理数, 矛盾. 所以 `"e"^q` 为无理数, `"e"^-q = ("e"^q)^-1` 也是无理数.

`pi^2` 是无理数; 从而 `pi` 是无理数.

(Ivan M. Niven) 假设 `pi^2 = a//b`, `a, b` 是正整数. 取正整数 `n` 使得 `n! gt pi a^n`, 同样利用引理的函数 `f` 构造微分方程 `P''(x) + pi^2 P(x) = pi^(2n+2) f(x)`. 容易验证方程的一个解是 `P(x) = sum_(i ge 0) (-1)^i pi^(2n-2i) f^((2i))(x)`. 同样 `P(x)` 只有有限项. 于是 `"d"/dx[P'(x) sin pi x - pi P(x) cos pi x]` `= (P''(x) + pi^2 P(x)) sin pi x` `= pi^(2n+2) f(x) sin pi x`. 两边乘以 `b^n//pi` 再积分, 一方面 `I = int_0^1 b^n pi^(2n+1) f(x) sin pi x dx` `= b^n (P(1) + P(0))`. 由于 `b^n pi^(2n) = a^n` 是整数, 根据引理的 3. 得到 `I` 是整数. 另一方面 `0 lt I lt b^n pi^(2n+1) // n!` `= pi a^n // n! lt 1`, 所以 `I` 不可能是整数, 矛盾.

连分数、丢番图逼近与等分布定理

连分数

连分数 (continued fraction) 设 `a_0, a_1, cdots` 为一列实数, 从 `a_1` 开始每项都为正. 我们称下式为有限连分数: `a^((n)) := [a_0";" a_1, cdots, a_n]` `:= a_0 + 1/(a_1+) 1/(a_2+) cdots 1/a_n` `:= a_0 + 1/(a_1+ 1/({: a_2+; , ddots 1/a_n :}))`. 称 `a^((k)) := [a_0";" a_1, cdots, a_k]` 为上式的第 `k` 个截断. `n to oo` 时, 上式称为无限连分数, 若极限存在则称该连分数收敛: `[a_0";" a_1, cdots] := lim_(n to oo) a^((n))`. 如果每项 `a_i` 都是整数, 则称该连分数是简单的. 简单连分数的值是有理数.

  1. 有理数的简单连分数展开是有限的: 试着展开 `62/23`.
  2. 二次无理数的简单连分数展开是循环的: 试着展开 `(3+sqrt7)/2`.
  3. 将有限连分数 `[3";"1,1,1,1]` 写为最简分数.
  1. 辗转相除, 将 `x` 写为 `[x] + {x}`: `62/23 = 2 + 16/23`,
    `23/16 = 1 + 7/16`,
    `16/7 = 2 + 2/7`,
    `7/2 = 3 + 1/2`,     此时分子为 1, 终止迭代. 我们得到 `62/23 = 2 + 1/(1 + 1/(2 + 1/(3 + 1/2)))` `:= [2";"1,2,3,2]`.
  2. 仍然是辗转相除: `(3+√7)/2 = 2 + (√7-1)/2`,
    `2/(√7-1) = (1+√7)/3 = 1 + (√7-2)/3`,
    `3/(√7-2) = 2+√7 = 4 + √7 - 2`,
    `1/(√7-2) = (2+√7)/3 = 1 + (√7-1)/3`,
    `3/(√7-1) = (1+√7)/2 = 1 + (√7-1)/2`,
     余数 `(√7-1)/2` 出现重复, 终止迭代. 我们得到 `(3+√7)/2 = 2 + 1/(1 + 1/(4 + 1/(1 + 1/(1 + cdots))))` `:= [2";"bar(1,4,1,1)]`.
  3. `[3";" 1, 1, 1, 1]` `= [3";" 1, 1, 2]` `= [3";" 1, 3/2]` `= [3";" 5/3]` `= 18/5`.

贵金属数 (Metallic ratio) 定义为二次方程 `x^2 = n x + 1` 的正根 `x_n = (n + sqrt(n^2+4))/2`, `n` 为正整数. 原方程变形为 `x = n + 1/x`, 迭代得到连分数表示: `x_n = [n";" n, n, ...]`. 黄金数 `x_1 = (1+sqrt 5)/2 = 1.618...`, 白银数 `x_2 = 1 + sqrt 2`, 青铜数 `x_3 = (3+sqrt(13))/2` 等等.

[参见这里] 常见常数的连分数 `"e" = [2";" 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...]`;
`pi = [3";" 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, ...]`. `"e"` 的展开有规律, 而 `pi` 似乎无规律可循. 取 `pi` 的连分数前两项就得到约率 `[3";"7] = 22//7`, 取前四项就得到著名的密率 `[3";"7,16] = 355//113`. 第 5 项 292 是较大的数字, 这意味着密率的精度较高.

说明: 分数、连分数、浮点数互转.

    单调性 考虑连分数 `a^((n)) = [a_0";" a_1, cdots, a_n]`.
  1. `a^((n))` 关于每个 `a_k` 是单调的, 且 `k` 为奇数时单调减, `k` 为偶数时单调增.
  2. `a^((0)) lt a^((2)) lt cdots lt a^((2k))` `lt a^((2l+1)) lt cdots lt a^((3)) lt a^((1))`.
  3. `a_n to oo` 时, `a^((n)) to a^((n-1))`; `a_n to 0` 时 `a^((n)) to a^((n-2))`.
    递推公式 考虑连分数 `a^((n)) = [a_0";" a_1, cdots, a_n]`. 记 `p_(-2) = q_(-1) = 0`, `p_(-1) = q_(-2) = 1`, 且 `p_n, q_n` 遵循同一递推公式: `{ p_n = a_n p_(n-1) + p_(n-2); q_n = a_n q_(n-1) + q_(n-2) :}` 则成立
  1. 递推: `a^((n)) = p_n // q_n` `(n ge 0)`.
  2. 互素: `p_(n-1) q_n - p_n q_(n-1) = (-1)^n` `(n ge -1)`, 因此当 `a^((n))` 为简单连分数时, `p_n, q_n` 互素.
  3. 误差: `a^((n-1)) - a^((n)) = (-1)^n (q_n q_(n-1))^-1` `(n ge 1)`.
  4. 当 `a^((n))` 为简单连分数时, 分母 `q_n` 从 `n ge 2` 起严格递增趋于无穷.
  1. `n = 0` 时, `a^((0)) = a_0`; 另一方面 `p_0 = a_0`, `q_0 = 1`, 结论成立. 设结论对 `n` 成立, 则 `n+1` 时 `a^((n+1)) = [a_0";" a_1, a_2, cdots, a_n + 1//a_(n+1)]`
    `= ((a_n + 1//a_(n+1)) p_(n-1) + p_(n-2))/ ((a_n + 1//a_(n+1)) q_(n-1) + q_(n-2))`
    `= (a_(n+1)(a_n p_(n-1) + p_(n-2)) + p_(n-1))/ (a_(n+1)(a_n q_(n-1) + q_(n-2)) + q_(n-1))`
    `= (a_(n+1) p_n + p_(n-1))/(a_(n+1) q_n + q_(n-1))` `= p_(n+1)/q_(n+1)`.
  2. `n = -1` 时结论成立. 设结论对 `n` 成立, 则 `n+1` 时 `p_n q_(n+1) - p_(n+1) q_n` `= p_n (a_(n+1) q_n + q_(n-1)) - q_n (a_(n+1) p_n + p_(n-1))` `= p_n q_(n-1) - q_n p_(n-1)` `= (-1)^(n+1)`.
  3. 由 1. 2. 直接推出.
  4. 这是因为 `q_0 = 1`, `q_1 = a_1 ge 1`, 从 `n ge 2` 起, 递推式系数均为正, 因此 `q_n` 严格递增趋于无穷.

无限简单连分数的收敛性 `[a_0";" a_1, cdots]` 必定收敛, 且极限 `a` 为无理数, 满足 `a^((0)) lt a^((2)) lt cdots lt a lt cdots lt a^((3)) lt a^((1))`.

  1. 我们已经知道, `a^((2n))` 严格递增有上界, `a^((2n-1))` 严格递减有下界, 设两个数列的极限分别为 `a, a'`, 显然 `a le a'`. 另一方面, 记 `a^((n)) = p_n//q_n`, 则由误差公式和 `q_n to oo` 知道 `a' - a lt a^((2n-1)) - a^((2n))` `= (q_(2n) q_(2n-1))^-1 to 0`. 因此 `a' = a`.
  2. 反设 `a = u//v` 是有理数, 则对任意正整数 `n` 有 `0 lt |a - a^((n))| lt |a^((n+1)) - a^((n))| = (q_n q_(n+1))^-1`, 即 `0 lt |u/v - p_n/q_n| lt 1/(q_n q_(n+1))`. 由左半不等式知道 `|u q_n - p_n v| ge 1`, 再由右半不等式知道 `1/(|v| q_n) lt 1/(q_n q_(n+1))`, 即 `q_(n+1) lt |v|`, 这与 `q_n to oo` 矛盾.
    简单连分数展开的唯一性定理
  1. 设 `[a_0";" a_1, cdots, a_n] = [b_0";" b_1, cdots, b_s]` 是两个相等的有限简单连分数, 且 `a_n, b_s gt 1`, 则有 `n = s` 且 `a_i = b_i`, `i = 0, cdots, n`.
  2. 设 `[a_0";" a_1, cdots] = [b_0";" b_1, cdots]` 是两个相等的无限简单连分数, 则 `a_i = b_i`, `i = 0, 1, cdots`.
  1. 不妨设 `s ge n`, 对 `n` 归纳. `n = 0` 时, 若 `s ge 1`, 则 `a_0 = b_0 + 1//[b_1";" cdots, b_s]`. 已知 `b_s gt 1`, 则上式分母 `[b_1";" cdots, b_s] gt 1`, 从而上式的 `a_0, b_0` 不能同时为整数, 矛盾.
    现在设结论对 `n-1 ge 0` 成立, 考虑 `n` 的情形, `s ge n ge 1`, 于是以下两式相等: `[a_0";"a_1, cdots, a_n] = a_0 + 1//[a_1";" cdots a_n]`
    `[b_0";"b_1, cdots, b_s] = b_0 + 1//[b_1";" cdots b_s]`
     已知 `a_n, b_s gt 1`, 则以上两式的分母 `gt 1`. 从而它们的整数部分相等: `a_0 = b_0`, 这又推出两式的分母相等. 由归纳假设 `n = s`, 并且 `a_i = b_i`, `i = 0, cdots, n`.
  2. 用 `r^((n))` 表示连分数的尾部 `r^((n)) = [a_n";" a_(n+1), cdots]`, 它一定收敛. 事实上 `r^((0)) = lim_(n to oo) [a_0";"a_1, cdots, a_n]` `= lim_(n to oo) a_0 + 1//[a_1";" cdots, a_n]` `= a_0 + 1//r^((1))`. 其中 `r^((1)) gt a_1 ge 1`, 因此 `a_0 = |__r^((0))__|`. 同理有 `a_n = |__r^((n))__|`, `quad AA n ge 0`. `a_n` 由 `r^((n))` 的值完全决定, 因此 `a_i = b_i`, `i = 0, 1, cdots`.

简单连分数展开的存在性定理 每个正实数 `a` 都能展开为简单连分数 `[a_0";" a_1, cdots]`, 并且 `a` 是有理数当且仅当该连分数有限. 事实上 `a_0 := [a]`, `quad r_0 := {a}`,
`a_(n+1) := [1//r_n]`, `quad r_(n+1) := {1//r_n}`. 如果规定有限简单连分数的最后一项大于 1, 则该连分数还是唯一的.

  1. 若 `a` 是有理数, 根据辗转相除法, 上述过程必定在有限步终止, 于是得到一个有限简单连分数. 并且, 在规定最后一项大于 1 时, 该结果是唯一的.
  2. 若 `a` 是无理数, 则每个 `r_i` 都是 `(0, 1)` 中的无理数. 由构造 `a = a_0 + r_0` `= a_0 + 1//(a_1 + r_1)` `= [a_0";"a_1, cdots, a_n + r_n]`, `quad AA a ge 0`, 可以看出 `a` 满足不等式 `a^((2n)) lt a lt a^((2n+1))`, 其中 `a^((n))` 表示第 `n` 个截断. 再由两边夹法则得到 `a = lim_(n to oo) a^((n)) = [a_0";"a_1, cdots]`.

丢番图逼近 (有理逼近)

(Dirichlet, 1842) `alpha in RR` 是无理数当且仅当存在无穷多对互素整数 `(p, q)` 使得 `|alpha - p/q| lt 1/q^2`.

  1. 定理的 "`lArr`" 部分是容易的. 设 `alpha = c/d` 是有理数. 考查 `|c/d - p/q|` `= |(c q - d p)/(d q)| lt 1/q^2`, 上式等价于 `|c q - d p| lt |d/q|`, 当 `|d| lt |q|` 时, 要使上式成立, 必须 `c q - d p = 0`, 即 `c/d = p/q`; 显然满足条件的互素 `(p, q)` 数量有限. 另一方面, 若 `|d| ge |q|`, 分母 `q` 有界, 于是位于 `alpha = c/d` 附近的分数 `p/q` 只有有限个.
  2. 现在设 `alpha` 是无理数, `p_n//q_n` 是 `alpha` 的连分数展开的第 `n` 个截断, 则 `p_n//q_n` 是既约分数, 并且根据连分数的截断误差, `0 lt |alpha - p_n/q_n| lt 1/(q_n q_(n+1)) lt 1/q_n^2`. 由于 `q_n` 从 `n ge 2` 起严格递增, 满足上式的 `p, q` 有无穷多对.
    Dirichlet 的原始证明.
  1. 设 `alpha` 是无理数. `AA n in ZZ^+`, 考虑 `[0, 1]` 区间的 `n+2` 个数 `1, {j alpha}`, `quad j = 0, cdots, n`. 由抽屉原理, 必有两个数距离 `le 1/(n+1)`.
    (i) 当这两个数为 `{i alpha}`, `{j alpha}` `(i gt j)` 时, 令 `c = [i alpha] - [j alpha]`, `quad d = i - j`; (ii) 当这两个数为 `1, {i alpha}` `(i gt 0)` 时, 令 `c = [i alpha]+1`, `quad d = i`. 两种情况下, 我们都令 `p = c//gcd(c, d)`, `q = d//gcd(c, d)`. 从而 `p, q` 互素, `1 le q le d le n`, 且 (i) `|alpha - p/q|` `= |alpha - ([i alpha] - [j alpha])/(i - j)|` `= |({i alpha} - {j alpha})/(i-j)|` `le 1/(d(n+1))` `lt 1/q^2`;
    (ii) `|alpha - p/q|` `= |alpha - ([i alpha] + 1)/i|` `= |({i alpha} - 1)/i|` `le 1/(d(n+1))` `lt 1/q^2`.     因此我们得到满足不等式要求的一对互素整数 `(p, q)`, 且 `1 le q le n`.
  2. 下证这样的 `(p, q)` 有无穷多对. 取 `n_0 = 1`, 由 2. 知存在 `p_0, q_0` 满足 `1 le q_0 le n_0` (因此 `q_0 = 1`), 且 `0 lt r_0 := |alpha - p_0/q_0| le 1/(q_0 (n_0+1)) lt 1/q_0^2 = 1`. 这里 `r_0 gt 0` 是因为 `alpha` 为无理数. 归纳假设已得到 `p_k, q_k, n_k` 满足 `1 le q_k le n_k`, 且 `0 lt r_k := |alpha - p_k/q_k| le 1/(q_k (n_k+1)) lt 1/q_k^2`, 那么取 `n_(k+1) = [r_k^-1]`, 由 2. 知存在 `p_(k+1), q_(k+1)` 满足 `1 le q_(k+1) le n_(k+1)`, 且 `0 lt r_(k+1) := |alpha - p_(k+1)/q_(k+1)| le 1/(q_(k+1) (n_(k+1)+1)) lt 1/q_(k+1)^2`, 这样便得到无穷多个满足条件的分数 `p_k//q_k`, 它们是两两不同的, 因为 `r_(k+1) le 1/(q_(k+1) (n_(k+1)+1))` `lt r_k/q_(k+1)`, 这说明每个分数都比上一个更加逼近 `alpha`.
    [Deepseek] 我们可以证明分母 `q_k to oo`. 事实上, 假设 `q_k` 不趋于无穷, 则存在正数 `M` 使得有无穷多项 `q_k le M`. `q_k` 是正整数, 这意味它只有有限种取值, 必存在正整数 `q`, 使得有无穷多项 `q_k = q`. 由构造 `|alpha - p_k/q| lt 1/q^2`, 满足上式的 `p_k` 只有有限个, 与结论 “`p_k//q_k` 两两不同”矛盾.

`alpha` 为无理数时, 上述结果可以改进为 `|alpha - p/q| lt 1/(2 q^2)`. 反之, 若 `p/q` 满足此不等式, 则它一定来自 `alpha` 的连分数的截断.

  1. 将 `alpha` 展开为连分数 `[a_0";"a_1, cdots]`, 取连续两个截断分数 `p_i//q_i`, `i = n, n+1`. 下面证明, 两个不等式 `|alpha - p_i/q_i| lt 1/(2 q_i^2)`, `quad i = n, n+1` 至少有一个成立. 假设两个不等式都不成立, 则 `1/(q_n q_(n+1)` `= |p_n/q_n - p_(n+1)/q_(n+1)|` (误差公式)
    `= |p_n/q_n - alpha| + |alpha - p_(n+1)/q_(n+1)|` (`alpha` 位于两个截断分数之间)
    `ge 1/2 (1/q_n^2 + 1/q_(n+1)^2)`.     化简得 `2 q_n q_(n+1) ge q_n^2 + q_(n+1)^2`, 这推出 `q_n = q_(n+1)`, 于是有 `n = 0` 及 `q_0 = q_1 = a_1 = 1`,
    `p_0 = a_0`, `p_1 = a_1 a_0 + 1 = a_0 + 1`,
    `a_0 + 1//2 lt alpha lt a_0 + 1`.     从而 `i = n+1 = 1` 时有 `|alpha - p_1//q_1|` `= |alpha - (a_0 + 1)|` `lt 1//2`, 与假设矛盾.
  2. 不妨设 `q gt 0`, 由 `q_0 = 1` 和 `q_n` 严格递增趋于无穷知道, 存在唯一的 `n` 使得 `q_n le q lt q_(n+1)`. 利用引理 🚧 得到 `|alpha q_n - p_n| le |alpha q - p|`, 故 `|alpha - p_n/q_n|` `le |alpha - p/q| q / q_n` `lt 1/(2 q q_n)`. 进而 `|p_n/q_n - p/q|` `le |p_n/q_n - alpha| + |alpha - p/q|` `lt 1/(2 q q_n) + 1/(2 q^2)`. `(ast)` 下证 `q_n = q`. 假设不成立, 则 `q_n lt q lt q_(n+1)`, `p//q` 不可能来自连分数截断. 特别 `p//q != p_n//q_n`, 因此 `1/(q q_n)` `le |p_n/q_n - p/q|` `lt 1/(2 q q_n) + 1/(2 q^2)`. 这推出 `q lt q_n`, 矛盾. 所以必有 `q_n = q`. 代入 `(ast)` 式得到 `|p_n - p| lt 1//q`, 故 `p_n = p`.

定理表明, `alpha` 的一个“好的”逼近必然来自连分数.

(Hurwitz, 1891) `alpha` 为无理数时, 上述结果可以改进为 `|alpha - p/q| lt 1/(sqrt 5 q^2)`. 且常数 `sqrt 5` 对于某些无理数是最佳估计, 不可再增加.

  1. 将 `alpha` 展开为连分数 `[a_0";"a_1, cdots]`, 取连续三个截断分数 `p_i//q_i`, `i = n-1, n, n+1`. 下面证明, 三个不等式 `|alpha - p_i/q_i| lt 1/(sqrt 5 q_i^2)`, `quad i = n-1, n, n+1` 至少有一个成立. 假设三个不等式都不成立, 则对 `i = n, n+1` 有 `1/(q_i q_(i-1))` `= |p_i/q_i - p_(i-1)/q_(i-1)|` (误差公式)
    `= |p_i/q_i - alpha| + |alpha - p_(i-1)/q_(i-1)|` (`alpha` 位于两个截断分数之间)
    `ge 1/sqrt 5 (1/q_i^2 + 1/q_(i-1)^2)`.     化简得 `q_i/q_(i-1) + q_(i-1)/q_i le sqrt 5`, `quad i = n, n+1`. 由 `sqrt 5` 是无理数知道不等号严格成立, 解一元二次不等式 `x + x^-1 lt sqrt 5` 得 `x in (phi^-1, phi)`, 其中 `phi = (sqrt5+1)//2`, 于是 `phi^-1 lt q_i//q_(i-1) lt phi`, `quad i = n, n+1`. 另一方面由递推公式, `q_(n+1)//q_n = (a_(n+1) q_n + q_(n-1))//q_n` `= a_(n+1) + q_(n-1)//q_n` `gt 1 + phi^-1` `= phi`, 矛盾.
  2. 我们估计误差 `alpha - p_n//q_n`. 将连分数的尾部记作 `r^((n)) = [a_n";"a_(n+1), cdots]`, 则 `alpha = [a_0";"cdots, a_n, r^((n+1))]`. 于是 `alpha - p_n//q_n`
    `= (p_n r^((n+1)) + p_(n-1))/(q_n r^((n+1)) + q_(n-1)) - p_n/q_n`
    `= (q_n p_(n-1) - p_n q_(n-1))/(q_n(q_n r^((n+1)) + q_(n-1)))`
    `= (-1)^n/(q_n^2(r^((n+1)) + q_(n-1)//q_n))`. `(ast)`     现在说明常数 `sqrt 5` 对于 `alpha = phi` 是最佳估计. 事实上 `phi = [1";"1, 1, cdots]`, 代入递推式得 `p_n = F_(n+1)`, `quad q_n = F_n`, `quad n ge 0`, `F_n` 为 Fibonacci 数列. 代入公式 `(ast)` 得 `|phi - p_n//q_n| q_n^2` `= 1/(phi + q_(n-1)//q_n)` `to 1/(phi + phi^-1)` `= 1/sqrt 5`, `quad n to oo`. 如果存在常数 `lambda gt sqrt 5` 和有理数 `p//q` 满足 `|phi - p//q| q^2 lt 1//lambda`, `(ast ast)` 由上个定理知 `p//q` 一定来自 `phi` 的连分数截断, 即存在 `n` 使得 `p//q = p_n//q_n`. 然而我们已经证明 `n to oo` 时极限是 `1//sqrt 5`, 因此满足 `(ast ast)` 式的互素 `(p, q)` 只有至多有限对.

Farey 分数

Farey 数列 第 1 步, 记 `F_1 = {0//1, 1//1}`. 第 `n` 步, 向 `F_(n-1)` 插入一些新的数, 得到新数列 `F_n`. 规则如下: 当 `a//b lt c//d` 是 `F_(n-1)` 中相邻的两个分数, 且分母之和 `b+d = n` 时, 就在这两个分数之间写上它们的 Farey 和 `(a+c)/(b+d)`. 由糖水不等式知道, Farey 和的大小介于两个分数之间. 我们将要证明, `F_n` 恰好将 `[0, 1]` 中所有分母不超过 `n` 的最简分数从小到大列出: `F_1 = {0/1, 1/1}`,
`F_2 = {0/1, 1/2, 1/1}`,
`F_3 = {0/1, 1/3, 1/2, 2/3, 1/1}`,
`F_4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}`,
`F_5 = {0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1}`.

    相邻性质 设 `a//b lt c//d` 是 `[0, 1]` 中的最简分数, 则以下各款等价:
  1. `a//b, c//d` 在某个 `F_n` 中相邻;
  2. `b c - a d = 1`; 这立即推出 `gcd(a, b) = gcd(c, d) = 1`, 因此 Farey 数表中的每个数都是最简分数.
  3. `a//b, c//d` 的 Ford 圆相切. 所谓 `a//b` 的 Ford 圆是指, 半径为 `1//2b^2`, 圆心在 `(a//b, 1//2b^2)` 的圆.
  1. `rArr` 2. 对 `n` 归纳, `n=1` 时等式成立. 设 `a//b lt c//d` 在 `F_n` 中相邻, 若两个分数都是从 `F_(n-1)` 继承下来的, 则它们在 `F_(n-1)` 中已经相邻, 由归纳假设等式成立. 否则, 根据 Farey 数的构造过程, `a//b, c//d` 中恰有一个数是第 `n` 步新增的, 不妨设为 `a/b`. 设 `x/y lt c/d` 是 `F_(n-1)` 中相邻的两数, 且 `a = x+c`, `b = y+d`. 由归纳假设 `y c - x d = 1`, 于是 `b c - a d = (y+d) c - (x+c) d = 1`.
  2. `rArr` 1. 根据, `a//b, c//d` 两个分数同时出现在 `F_n` 中, 其中 `n = max(b, d)`. 但根据分母下界性质, 若存在分数 `x//y` 介于 `a//b, c//d` 之间, 则必有 `y ge b + d ge n + 1`. 因此 `x//y !in F_n`. 这意味着 `a//b, c//d` 在 `F_n` 中相邻. 这一部分的推理不影响下文的证明, 因此不构成循环论证.
  3. `hArr` 2. 两 Ford 圆相切时, 连接圆心, 由勾股定理 `(1/(2b^2) - 1/(2d^2))^2 + (c/d - a/b)^2 = (1/(2b^2) + 1/(2d^2))^2`, 化简就得到 `b c - a d = 1`.

分母下界 设 `a//b lt x//y lt c//d` 是 `[0, 1]` 中的三个分数, 分母 `b, y, d` 均大于 0. 如果 `b c - a d = 1`, 则有 `y ge b + d`, 且等号成立时有 `x = a + c` 成立.

由已知 `c/d - a/b = (b c - a d)/(b d) = 1/(b d)`, 因此 `1/(b d) = c/d - x/y + x/y - a/b` `= (c y - d x)/(d y) + (b x - a y)/(b y)` `ge 1/(d y) + 1/(b y)`, 于是 `y ge b + d`. 如果等号成立, 则 `1 = c y - d x` `= c(b+d) - d x` `= a d + 1 + c d - d x`, 这推出 `d x = (a + c) d`, 于是 `x = a + c`.

Farey 数列 `F_n` 恰好将 `[0,1]` 中所有分母不超过 `n` 的最简分数从小到大列出.

“最简分数”与“从小到大”的性质已在前面证明. 下证 `F_n` 恰好包含 `[0, 1]` 中所有分母不超过 `n` 的最简分数. 对 `n` 归纳, `n = 1` 时命题成立. 假设命题对 `n-1` 成立, 那么 `F_n` 必须恰好新增这些元素: `S_n = {k//n | 0 lt k lt n, gcd(k, n) = 1}`. 根据相邻性质, `F_n` 新增的元素都是分母为 `n` 的最简分数, 因此包含在集合 `S_n` 中. 反之要证集合 `S_n` 的每个元素 `k//n` 都会出现在 `F_n` 中. 事实上, 先找到相邻两项 `a//b lt c//d in F_(n-1)` 满足 `a//b lt k//n lt c//d`, 由分母下界性质, `n ge b + d`. 这里等号必成立, 如若不然, 设 `n gt b + d`, 根据 Farey 数列构造规则与归纳假设, 分数 `(a+c)/(b+d)` 已经出现在 `F_(n-1)` 中, 从而 `a//b, c//d` 不可能是 `F_(n-1)` 的相邻两项. 于是 `n = b + d`, 这推出 `k = a + c`, 于是 `k//n in F_n`.

Farey 和性质 设 `a//b lt x//y lt c//d` 是某个 `F_n` 中的连续相邻三项, 则 `x/y = (a+c)/(b+d)`.

    对 `n` 归纳:
  1. 若 `a//b, c//d` 正好是 `F_(n-1)` 中的相邻两项, 则 `x//y` 是 `F_n` 中新增的项, 根据 Farey 数列的构造规则, 结论成立.
  2. 若 `a//b, c//d in F_(n-1)` 但不相邻, 则 `a//b, x//y, c//d` 正好是 `F_(n-1)` 中连续相邻三项, 根据归纳假设, 结论成立.
  3. 接下来 `a//b, c//d` 至少有一个是 `F_n` 中的新增项, 这意味着 `x//y in F_(n-1)`. 例如, 当 `a//b` 是 `F_n` 的新增项时, 设 `x//y` 在 `F_(n-1)` 中的左邻居是 `p//q`, 于是 `a = p+x`, `b = q+y`, `x(b+d) - y(a+c)` `= x(q+y+d)-y(p+x+c)` `= x(q+d) - y(p+c)`. 这推出 `x/y = (a+c)/(b+d)` `iff x/y = (p+c)/(q+d)`. 若 `c//d in F_(n-1)`, 则问题归结到 `F_(n-1)` 中的连续三项 `p//q, x//y, c//d`, 从而结论成立. 否则设 `x//y` 在 `F_(n-1)` 中的右邻居是 `u//v`, 于是 `c = x+u`, `d = y+v`, `x(q+d) - y(p+c)` `= x(q+y+v) - y(p+x+u)` `= x(q+v) - y(p+u)`, 这推出 `x/y = (p+c)/(q+d)` `iff x/y = (p+u)/(q+v)`. 从而问题归结到 `F_(n-1)` 中的连续三项 `p//q, x//y, u//v`.
    用 Farey 分数证明丢番图逼近结论 设 `a//b lt c//d` 是 `F_n` 中的相邻两项, 且无理数 `xi` 满足 `a//b lt xi lt c//d`, 则
  1. `|xi - a/b| lt 1/(2b^2)` 或 `|xi - c/d| lt 1/(2d^2)` 至少有一个成立;
  2. `|xi - a/b| lt 1/(sqrt 5 b^2)`, `|xi - c/d| lt 1/(sqrt 5 d^2)` 或 `|xi - (a+c)/(b+d)| lt 1/(sqrt 5(b+d)^2)` 至少有一个成立.

1. 是显然的, 因为 Farey 数列相邻两项的 Ford 圆相切. 下证 2. 记 `a/b = p_1/q_1`, `(a+c)/(b+d) = p_2/q_2`, `c/d = p_3/q_3`, 显然它们是 `F_(b+d)` 的连续相邻三项. 假设三个不等式都不成立, 则 `1/(q_i q_(i+1))` `= p_(i+1)/q_(i+1) - p_i/q_i` `= |xi - p_(i+1)/q_(i+1)| + |xi - p_i/q_i|` `ge 1/sqrt 5(1/q_i^2 + 1/q_(i+1)^2)`, `quad i = 1, 2`. 整理得 `q_i/q_(i+1)+q_(i+1)/q_i le sqrt 5`, `quad i = 1, 2`. 和 Hurwitz 定理的证明相同, 得到 `q_i//q_(i+1) in (phi^-1, phi)`, `i = 1, 2`, 即 `b/(b+d), (b+d)/d in (phi^-1, phi)`. 记 `x = b/(b+d)`, 则 `(b+d)/d = 1/(1-x)`, 但 `x in (phi^-1, phi)` 时不可能有 `1/(1-x) in (phi^-1, phi)`, 矛盾.

等分布定理

Dirichlet 逼近定理 设 `x in RR`, `n in ZZ^+`, 则在 `x, 2x, cdots, n x` 这 `n` 个数中, 存在一个数到最近整数的距离小于 `1//n`.

记 `{x} = x - [x]` 为实数 `x` 的小数部分. 考虑 `n+1` 个数 `0, {x}, {2x}, cdots, {n x}`, 它们落在区间 `[0, 1)` 中. 若将区间平均分为 `n` 份 (左闭右开), 则必有两个数落在同一区间. 设它们是 `{i x}, {j x}`, 其中 `i gt j`. 于是 `|(i-j) x - ([i x] - [j x])|` `= |{i x} - {j x}|` `lt 1//n`.

Kronecker 逼近定理 设 `a` 是无理数, 则数列 `a_n = {n a}` (`n a` 的小数部分) 在 `[0, 1]` 上稠密.

    [Deepseek] 只需证对任意 `x in [0, 1]` 和任意正整数 `m` 都存在一项 `a_n` 使得 `|a_n - x| lt 1/m`. 根据 Dirichlet 逼近定理, 存在 `1 le k le m` 使得 `a_k in [0, 1//m) uu (1 - 1//m, 1)`. 又由 `a` 是无理数知道 `a_k != 0`.
  1. 若 `a_k = delta in (0, 1//m)`, 则对任意正整数 `j` 有 `a_(j k) = {j a_k} = {j delta}`. 令 `N = |__ 1//delta __|`, 则集合 `(a_(j k))_(j=1)^N` `= (j delta)_(j=1)^N` 将 `[0, 1]` 区间分为 `N+1` 个小区间, 前 `N` 个长度为 `delta`, 最后一个长度为 `1 - N delta lt delta`. 点 `x` 总会落在一个小区间内, 故存在一个 `j_0` 使得 `|a_(j_0 k) - x| le delta lt 1//m`.
  2. 若 `a_k = 1 - delta in (1-1//m, 1)`, 则 `a_(j k) = {j a_k}` `= 1 - {j delta}`, 即 `1 - a_(j k) = {j delta}`. 令 `y = 1 - x`, 由 1. 的证明知存在一个 `j_0` 使得 `|(1 - a_(j_0 k)) - y| le delta lt 1//m`, 即 `|x - a_(j_0 k)| lt 1//m`.

[知乎@Fulcrum] 数列 `{tan n}` 无界.

由 `tan` 的周期性, 只需证 `n/pi mod 1` 与 `1/2` 可以任意地逼近. 根据 Kronecker 逼近定理和 `1/pi` 是无理数知, 数列 `{n/pi mod 1}` 在 `[0, 1]` 上稠密. 从而 `n/pi mod 1` 与 `[0, 1]` 中的任意实数都能任意地逼近, 包括 `1/2`.

Weyl 等分布定理 设 `a` 是无理数, 则数列 `a_n = n a mod 1` 在 `[0, 1]` 上等分布. 这就是说, 对任意子区间 `[a, b] sube [0, 1]`, `a_n` 落在 `[a, b]` 中的概率与区间长度成正比: `lim_(n to oo) {: \#{1 le k le n: a_k in [a, b]} :}/n = b-a`.

[吴昊《`{n^k alpha}` 稠密性的初等证明》]

(Van der Waerden) 对任意正整数 `N, k`, 存在正整数 `M`, 使得把数 `1, 2, cdots, M` 染成 `N` 种颜色时, 不论染色方案如何, 都至少存在一个长度为 `k` 的等差数列被染为同一颜色.

对任意正整数 `w, n, k` 有 `n^k = 1/k! sum_(i=0)^k (-1)^(k-i) (k;i) (w+i n)^k`.

对多项式 `f(x) = x^k` 在 `k+1` 个点 `w_i = w + i n` (`0 le i le k`) 处应用 Lagrange 插值: `x^k = sum_(i=0)^k prod_(j!=i) (x-w_j)/(w_i-w_j) w_i^k`, 比较上式 `x^k` 的系数 `1 = sum_(i=0)^k prod_(j!=i) w_i^k/(w_i-w_j)`
`= sum_(i=0)^k w_i^k/(prod_(j!=i) n(i-j))`
`= sum_(i=0)^k (w_i/n)^k 1/(i! * (-1)^(k-i) (k-i)!)`
`= 1/k! sum_(i=0)^k (-1)^(k-i) (k;i) (w_i/n)^k`.

对任意无理数 `alpha` 和正整数 `k`, 数列 `x_n = n^k alpha mod 1` 在区间 `[0, 1]` 上稠密.

  1. 任取 `epsi in (0, 1)`, 下证存在一项 `x_n in (0, epsi)`. 取正整数 `N` 满足 `N gt (2^k//epsi+1)^k`, 对每个正整数 `i`, 存在唯一的 `1 le j le N`, 使得 `i^k alpha mod 1 in [(j-1)/N, j/N)`. 换言之, 我们可以用 `N` 种颜色对全体正整数染色. 由 Van der Waerden 定理, 存在长度为 `k+1` 的同色等差数列, 记为 `w_i = w + i n`, quad `0 le i le k`, `w, n in ZZ^+`.
  2. 记 `y_i = w_i^k alpha mod 1`. 由引理, `n^k alpha` `= 1/k! sum_(i=0)^k (-1)^(k-i) (k;i) w_i^k alpha` `-= 1/k! sum_(i=0)^k (-1)^(k-i) (k;i) y_i` `(mod 1)`. 记上式右端为 `A`, 下面进行分部求和. 记 `(-1)^i (k;i) = (-1)^i (k-1;i) - (-1)^(i-1) (k-1;i-1)` `:= u_(i+1) - u_i`, 从而 `A = 1/k! (-1)^k [u_i y_i]_0^(k+1) - 1/k! sum_(i=0)^k (-1)^k u_(i+1) (y_(i+1) - y_i)` `= 1/k! sum_(i=0)^(k-1) (-1)^(k-i) (k-1;i) (y_i - y_(i+1))`. 由于每个 `w_i` 同色, 有 `|y_i - y_j| lt 1/N`. 从而 `|A| lt 2^(k-1)/(k! N) le 1/N`.
  3. 我们已经证明 `n^k alpha -= A (mod 1)`, 由于 `alpha` 是无理数易得 `A != 0`. 若 `A gt 0`, 则 `x_n := n^k alpha mod 1` 就等于 `A`, 且 `x_n = A in (0, 1/N) sube (0, epsi)`. 若 `A lt 0`, 此时 `x_n = A + 1 in (1 - 1/N, 1)`. 取最大的使得 `M^k (1-x_n) lt 1` 成立的正整数 `M`, 下证 `x_(M n) in (0, epsi)`. 事实上, `(M+1)^k (1-x_n) ge 1` `rArr (M+1)^k ge 1/(1-x_n)` `ge N gt (2^k/epsi+1)^k`. 于是 `M gt 2^k/epsi`. 另一方面, `x_(M n) = (M n)^k alpha mod 1` 与 `1 - M^k(1 - x_n)` 均属于 `(0, 1)` 且差为整数, 所以 `x_(M n) = 1 - M^k(1-x_n)` `le (M+1)^k (1-x_n) - M^k(1-x_n)` `overset(?)(le) 2^k M^(k-1) (1-x_n)` `lt 2^k/M lt epsi`. 其中问号处的不等式, 做法是将 `(M+1)^k` 展开, 第一项 `M^k` 抵消后, 剩下的最高次项是 `M^(k-1)`, 且每项系数不超过 `2^k`.
  4. 最后对任意区间 `(s, t) sube (0, 1)`, 证明存在一项 `x_n in (s, t)`. 取 `epsi gt 0` 使得 `t/epsi gt (2^k/(1-s//t) + 1)^k`. 先取正整数 `n` 使得 `x_n in (0, epsi) sube (0, t)`, 再取最大正整数 `M`, 使得 `M^k x_n lt t`, 于是 `(M+1)^k x_n ge t` `rArr (M+1)^k ge t/epsi` 这推出 `M gt 2^k/(1-s//t)`, 即 `t(1 - 2^k/M) gt s`. 故 `x_(M n)` `= M^k x_n` `ge (M+1)^k x_n - 2^k M^(k-1) x_n` `gt t - 2^k/M t` `= t(1 - 2^k/M)` `gt s`. 综上有 `x_(M n) in (s, t)`.

对任意无理数 `alpha`, 正整数 `k, m` 和整数 `0 le r lt m`, 存在无穷多个正整数 `n` 使得 `|__n^k alpha__| -= r (mod m)`.

记 `x_n := n^k alpha mod 1`, 由于 `n^k alpha` `= m |__n^k alpha__| + m x_n`, 取整并模 `m` 得到 `|__n^k alpha__| -= |__ m x_n __|` `(mod m)`. 而 `|__ m x_n __| = r` 等价于 `x_n in [r/m, (r+1)/m)`; 利用 `x_n` 在 `[0, 1]` 的稠密性即得证.

代数数与超越数

设 `x in CC`, 如果存在不为常数的多项式 `f in QQ[x]` 使得 `f(x) = 0`, 则称 `x` 是代数数, 记作 `x in cc A_QQ`; 否则称为超越数, 记作 `x in CC\\cc A_QQ`. 如果 `x` 是代数数, 上述使得 `f(x) = 0` 的 `f in QQ[x] \\ QQ` 当中, 总存在一个次数最小, 且首项系数为 1 的多项式, 称为 `x` 的最小多项式. 最小多项式的次数就称为 `x` 的次数. 例如有理数是 1 次代数数, `sqrt 2` 是 2 次代数数等.

由于可以将有理系数的 `n` 次多项式的各系数通分, 所以定义中的有理系数换成整系数也对.

全体代数数 `cc A_QQ` 是可数的; 从而由 `CC` 不可数知道, 超越数是存在的, 而且有不可数多个超越数.

由于一个 `n` 次多项式至多有 `n` 个不同的根, 我们只需指出全体整系数多项式的集合 `P` 是可数集. 以 `P_n` 记全体次数不超过 `n` 的整系数多项式, 则 `P_n` 可数, 于是 `P = uuu_(n=0)^oo P_n` 也可数.

[菲赫金哥尔茨《微积分学教程》中册第319目] `"e"` 是超越数.

    反设 `"e"` 是整系数多项式 `sum_(i=0)^m c_i x^i` 的根, 其中 `c_0 != 0`.
  1. 任取 `n` 次多项式 `f(x)`, 分部积分 `int_0^i "e"^-x f(x) dx` `= -["e"^-x f(x)]_0^i + int_0^i "e"^-x f'(x) dx` `= cdots` `= -["e"^-x (f(x) + f'(x) + cdots + f^((n))(x))]_0^i`. 简记 `F(x) := f(x) + f'(x) + cdots + f^((n))(x)`, 有 `int_0^i "e"^-x f(x) dx` `= -["e"^-x F(x)]_0^i` `= F(0) - "e"^-i F(i)`. 等式两边乘以 `c_i "e"^i` 并求和, `sum_(i=0)^m c_i "e"^i int_0^i "e"^-x f(x) dx` `= F(0) sum_(i=0)^m c_i "e"^i - sum_(i=0)^m c_i F(i)` `= - sum_(i=0)^m c_i F(i)`. `(ast)`
  2. 现在设 `p` 是大于 `m` 与 `|c_0|` 的素数. 这样的素数有无穷多个, 且可以取到比任意给定正数都大. 令 `f(x) = x^(p-1)/(p-1)! prod_(j=1)^m (x-j)^p` `= 1/(p-1)! sum_(j ge p-1) a_j x^j`. 求导得 `f^((k))(x) = 1/(p-1)! sum_(j ge k) j (j-1) cdots (j-k+1) a_j x^(j-k)` `= k!/(p-1)! sum_(j ge k) (j;k) a_j x^(j-k)`. 当阶数 `k ge p` 时, 分母的 `(p-1)!` 被消去, `f^((k))(x)` 成为整系数多项式, 且系数为 `p` 的倍数.
  3. 另一方面, 当 `k lt p` 且 `x = 1, 2, cdots, m` 时, 由于 `x` 是 `f` 的 `p` 阶零点, `f^((k))(x) = 0`, 因此 `F(x) = f(x) + f'(x) + cdots + f^((n))(x)` 是 `p` 的倍数. 然而当 `x = 0` 仅仅是 `f` 的 `p-1` 阶零点, 于是 `F(0) -= f^((p-1))(0)` `= (p-1)! xx f` 的 `p-1` 次项系数 `= ((-1)^m m!)^p !-= 0` `quad (mod p)`. 我们对 `(ast)` 式右边模 `p`, 得到 `-c_0 F(0) !-= 0 (mod p)`. 再来估计左边, 注意 `x in [0, m]`, 有 `|int_0^i "e"^-x f(x) dx|` `lt m^(m p + p-1)/(p-1)! int_0^i "e"^-x dx` `to 0`. `quad (p to oo)` 于是 `(ast)` 式右边的绝对值恒 `ge |c_0| ge 1`, 左边却趋于零, 从而矛盾.

(Gelfand) 设 `a in cc A_QQ\\{0, 1}`, `b in cc A_QQ\\QQ`, 则 `a^b` 是超越数.

Gelfand 常数 `"e"^pi = ("e"^(pi"i"))^(-"i")` 是超越数.