解关于 `x, y` 的不定方程 `a x y+b x+c y+d = 0`, `a, b, c, d` 为整数.

两边同乘 `a` 以后变形为 `(a x+c)(a y+b) = b c-a d`, 再讨论 `b c-a d` 的因子即可.

解关于 `a, b, c, d` 的不定方程 `1/a + 1/b + 1/c + 1/d = 1`, `a, b, c, d` 是两两不相等的正整数.

解关于 `x, y` 的不定方程 `x^2 + 615 = 2^y`.

  1. 模 2: 显然 `y` 只能是正整数, 于是 `2^y` 是偶数. 这推出方程左边是偶数, 于是 `x` 是奇数.
  2. 模 3: `2^y` 不是 3 的倍数, 但 615 是 3 的倍数, 于是 `x` 不是 3 的倍数.
  3. 模 6: 综上可知 `x = 6n+-1`, 于是 `x^2 -= 1 (mod 6)`. 而 `615 -= 3 (mod 6)`, 得到 `2^y -= 4(mod 6)`. 这推出 `y` 是偶数.
  4. 设 `y = 2n`, 原方程变形为 `(2^n - x)(2^n + x) = 615 = 3*5*41`, 我们只需寻找 `(a, b)` 满足 `a + b = 2^(n+1)`, 其中 `a, b in {3, 5, 41}`. 容易发现只有两组解 `(a, b) = (5, 123)` 或 `(123, 5)`. 于是 `2^n +- x = 5`, `quad 2^n ± x = 123`. 解得 `n = 6`, (于是 `y = 12`), `x = +-59`.

[来自 我是小学二年级的屑] 求 `{ x y = 4 n; x+y = n+2 :}` 的正整数解.

    [来自 CBY 博士] 由已知 `x, y = (n+2+-sqrt((n-6)^2-32))/2`. 令判别式 `(n-6)^2-32 ge 0` 得 `n ge 12`. 令 `m = n-6 ge 6`, 则 `x = 4 + (m-sqrt(m^2-32))/2` `= 4 + 16/(m+sqrt(m^2-32))`. 因此 `4 lt x` `le 4 + 16/(6+sqrt(6^2-32)) = 6`, 即 `x = 5, 6`.
  1. `x = 6` 对应 `m = 6`, `n = 12`, 这时 `y = 8`.
  2. `x = 5` 对应 `m - sqrt(m^2 - 32) = 2`, 即 `m = 9`, `n = 15`, 这时 `y = 12`.

求 `(x+y)^2 = x^3 + y^3` 的正整数解.

两边同时约去正因子 `x+y` 得 `x+y = x^2 - x y + y^2`, 这是椭圆的方程, 由图像我们推测正整数解只有 `(1,2)`, `(2,1)`, `(2,2)`. [来自 我是费马方程的正整数解] 上式视为 `x` 的方程, 令它的判别式 `ge 0`, 我们得到 `y = 1, 2`, 从而轻松得到结果.

求 `x^3 + y^3 = z^2` 的正整数解.

令 `(x, y, z) = (a c, b c, c^2)`, 问题化为 `a^3 c^3 + b^3 c^3 = c^4`, 显然 `c != 0`, 得 `a^3 + b^3 = c`. 任取 `a, b in ZZ^+`, `(x, y, z) = (a (a^3+b^3), b (a^3+b^3), (a^3+b^3)^2)` 都给出原方程的一组正整数解; 如 `a=1, b=1` 时得到 `(2, 2, 4)`, `a=1, b=2` 时得到 `(9, 18, 81)` 等. 其它形式的解??

[来自 马上开学的菜狗] 求 `x^3 + y^3 = x^2 y^2` 的正整数解.

[来自 小猿搜题] 取参数 `t = x // y`, 方程化为 `(t^3+1) y^3 = t^2 y^4`, 从而 `{ x = t^2 + 1//t; y = t + 1//t^2 :}` `t = 1` 时, 得到一组解 `x = y = 2`. `t gt 1` 时, ??

[来自 叉叉子] 证明不定方程 `2x^4 = y^4 - 17 z^4` 只有平凡解 `x = y = z = 0`.

由于方程齐次, 不妨令 `gcd(x, y, z) = 1`, 考虑 mod 17 的可能余数: `{: 2x^4, y^4, 17z^4; 0, 0, 0; +-2, +-1, ; +-8, +-4, ; :}` 等式不能成立, 一个矛盾.

勾股数

由熟知的勾股定理 (Pythagorean theorem), 直角三角形的三边长 `a, b, c` 满足 `a^2+b^2=c^2`. 我们称满足上述不定方程的正整数 `a, b, c` 为一组勾股数 (Pythagorean triple), 如 `3, 4, 5`; `5, 12, 13`; `7, 24, 25` 等. 以勾股数为边长的直角三角形叫勾股三角形. 注意到像 `3, 4, 5` 与 `6, 8, 10` 是本质相同的勾股数, 故定义勾股数 `a, b, c` 是本原的, 如果 `gcd(a, b, c) = 1`.

本原勾股数 `a, b, c` 两两互素, 且 `c` 为奇数, `a, b` 一奇一偶.

设 `d = (a, b)`, 则 `d^2 | a^2 + b^2 = c^2`, 这推出 `d | c`. 于是 `d | (a, b, c) = 1`, 即 `d = 1`. 同理 `(b, c) = (c, a) = 1`.
因为 `(a, b, c)` 两两互素, 它们中的偶数不超过一个, 假设 `c` 为偶数, 则 `a, b` 为奇数. 设 `a = 2m+1`, `quad b = 2n+1`, `quad c = 2k`, 则 `a^2 + b^2 -= 2 (mod 4)`, `c^2 -= 0 (mod 4)`, 矛盾. 因此 `c` 为奇数. 注意到 `a, b` 不全为偶数, 其中一个为奇数, 则另一个为偶数.

由于 `a, b` 地位对称, 不妨设 `b` 是偶数, 则本原勾股数的全体可以表示为 `a = u^2-v^2`, `quad b = 2u v`, `quad c = u^2+v^2`. 其中 `u gt v gt 0`, `quad (u, v) = 1`, 且 `u, v` 一奇一偶.

容易说明满足上述条件的 `(a, b, c)` 确实是本原勾股数. 下证必要性. 注意 `c-a, c+a, b` 都是正的偶数, 可设 `2A = c-a`, `quad 2B = b`, `quad 2C = c+a`, `A, B, C` 为正整数. 因为 `b^2 = c^2 - a^2 = (c-a)(c+a)`, 我们有 `B^2 = A C`. 下证 `A, C` 互素. 设 `d = (A, C)`, 则 `d | C-A = a`, `quad d | C+A = c`, 从而 `d | (a, c) = 1`, 即 `d = 1`.
因为 `A C` 是平方数, 而 `A, C` 没有公共的素因子, 所以 `A, C` 都是平方数, 可设 `C = u^2`, `quad A = v^2`. 于是 `a = u^2-v^2`, `quad c = u^2+v^2`,
`b = 2 sqrt(B^2)` `= 2 sqrt(A C)` `= 2 u v`. 最后说明 `u, v` 满足的条件. 由 `C gt A` 有 `u gt v gt 0`. 由 `(A, C) = 1` 知 `(u, v) = 1`. 由 `a = u^2 - v^2` 是奇数知 `u, v` 一奇一偶.

    下面使用数形结合的直观重新证明这一定理.
  1. 首先说明, 全体本原勾股数与单位圆在第一象限上的有理点一一对应. 方程两边同除以 `c^2` 得 `(a/c)^2 + (b/c)^2 = 1`, 这说明 `(a/c, b/c)` 是单位圆周上的点; 反之设 `(p, q)` 是单位圆上的有理点, 其中 `p, q` 是最简分数, 用它们分母的最小公倍数通分得到 `(p, q) = (a/c, b/c)`, 从而对应于勾股数 `(a, b, c)`. 容易说明 `(a, b, c)` 是本原的.
  2. 在第一象限的单位圆周上任取一点 `P(x_P, y_P)`. 又设 `A(-1, 0)`, `k` 是 `AP` 的斜率, 则 `P` 点坐标和 `k` 的值一一对应. 显然 `P` 是有理点时, `k` 是 `(0,1)` 中的一个有理数; 下证 `k` 是 `(0,1)` 中的有理数时, 点 `P` 必为有理点. 设 `k = v/u`, 整数 `u gt v gt 0`, 我们求 `P` 的坐标, 可以用 `tan 2 alpha` 的公式; 这里用复数来处理. 由已知, `"arg"(u+"i"v) = /_ PAQ`, 将这个复数平方, 就得到一个具有两倍辐角的复数 `(u+"i"v)^2 = u^2-v^2 + 2u v"i"`. 因为同弧所对的圆心角是圆周角的两倍, 我们有 `"arg"(u+"i"v)^2 = /_ POQ`. 又 `|(u+"i"v)^2|` `= |u+"i"v|^2` `= u^2+v^2`. 利用三角形相似得到 `x_P = (u^2-v^2)/(u^2+v^2)`, `y_P = (2u v)/(u^2+v^2)`, 所以 `P` 是有理点.
  3. 只要让斜率 `k` 取遍集合 `(0,1) nn QQ`, 就得到单位圆在第一象限的全部有理点, 从而得到全体本原勾股数.

可以用代数计算验证, 确实有 `(u^2-v^2)^2 + (2u v)^2 = (u^2+v^2)^2`. 由以上讨论知, 任意一个勾股三角形总是相似于边长为 `u^2-v^2, 2u v, u^2+v^2` 的三角形, 其中 `u gt v gt 0`. 代入 `(u,v) = (2,1)` 得到勾股数 `(3, 4, 5)`, 代入 `(u,v) = (3,2)` 得到勾股数 `(5,12,13)`... 试试看吧!

[来自 レイ] 证明: 单位圆上存在无数个点, 它们两两间的距离均为有理数.

[来自 折棒的网友] 记 `A(-1, 0)`, `B(1, 0)`. 对于任一组勾股数 `a^2+b^2=c^2`, 可取点 `K` 使得 `KA = 2a//c`, `KB = 2b//c`, 于是 `KA^2 + KB^2 = AB^2`, `K` 位于单位圆上. 依此法取 `K_1, K_2`, 则 `A B K_1 K_2` 是圆内接四边形, 由 Ptolemy 定理 `K_1 K_2 * AB + B K_1 * A K_2 = A K_1 * B K_2`. 因此 `K_1 K_2` 为有理数. 但勾股数有无穷多组, 所以这样的点有无穷多个.

不存在面积为平方数的勾股三角形.

    本证明使用无穷递降法.
  1. 设该勾股三角形的三边长为 `a, b, c`, 面积为 `d^2`. 若 `(a, b, c) = m gt 1`, 则 `m^2 | a b = 2 d^2`, 这推出 `m | d`. 因此不妨设 `a, b, c` 是本原的, 从而得到已知条件 `a^2 + b^2 = c^2`, `quad (a, b, c) = 1`, `quad a b // 2 = d^2`. 我们假设 `c` 是满足上述条件的最小正整数, 下面来导出矛盾.
  2. 由勾股数的结论, `a, b, c` 两两互素. 设 `b` 是偶数, 则存在整数 `u, v`, 满足 `u gt v gt 0`, `quad (u, v) = 1`, `quad u, v` 一奇一偶, 使得 `a = u^2 - v^2`, `quad b = 2uv`, `quad c = u^2 + v^2`. 于是 `d^2 = a b // 2 = (u+v)(u-v) u v`.
  3. 容易验证四个因子 `u+v, u-v, u, v` 两两互素. 比如 `(u+v, u-v)` `= (u+v, (u+v)+(u-v))` `= (u+v, 2 u)`, 但 `u + v` 是奇数, 因此上式等于 `(u+v, u) = (v, u) = 1`, 这推出 `(u+v, u-v) = 1`.
  4. 四个互素因子的乘积是平方数 `d^2`, 由此得到这四个因子都是平方数. 设 `A = sqrt(u+v)`, `quad B = sqrt(u-v)`, `quad C = sqrt u`, `quad D = sqrt v`, `A, B, C, D` 也是两两互素的, 其中 `A gt B gt 0` 是奇数, `C, D` 一奇一偶. 注意 `2C^2 = 2u = A^2 + B^2 -= 2 (mod 4)`, 所以 `C` 是奇数, `D` 是偶数.
  5. 令 `a_1 = (A+B)/2`, `quad b_1 = (A-B)/2`, `quad c_1 = C`, `quad d_1 = D/2`, 有 `a_1^2 + b_1^2 = (A^2+B^2)/2 = C^2 = c_1^2`,
    `a_1 b_1 // 2 = (A^2-B^2)/8 = v/4 = (D/2)^2 = d_1^2`.     且 `(a_1, b_1, c_1)` `= (a_1, a_1+b_1, c_1)` `= (a_1, A, C) = 1`.
  6. 我们发现, `a_1, b_1, c_1` 也满足 `a, b, c` 的关系 , 但 `c_1 = C = sqrt u lt u^2+v^2 = c`, 这与 `c` 的最小性矛盾. 原命题得证.

Fermat 大定理 (Fermat's Last Theorem, FLT) 设整数 `n gt 2`, 则不定方程 `x^n + y^n = z^n` 不存在满足 `x, y, z != 0` 的整数解.

    我们有以下观察:
  1. 该不定方程是齐次的. 即, 若 `x, y, z` 是该方程的解, 则对任意整数 `k`, `k x, k y, k z` 也是它的解. 反之若存在非零整数 `k`, 使得 `k x, k y, k z` 是方程的解, 则 `x, y, z` 也是它的解.
  2. 若 FLT 对于整数 `n` 成立, 则它对任意 `n` 的倍数也成立.
    3. 我们来证明 FLT(4), 即 `n = 4` 的情形. 设 `x^4 + y^4 = z^4`, 由观察 1, 可以假设 `(x, y, z) = 1`. 因此, `x^2, y^2, z^2` 是本原勾股数. 设 `y` 是偶数, 故存在 `u, v` 使得 `x^2 = u^2 - v^2`, `quad y^2 = 2 u v`, `quad z^2 = u^2 + v^2`. 上式表明 `u, v, z` 是勾股数, 但它们围成的直角三角形的面积 `u v // 2 = (y/2)^2` 是平方数! 矛盾.
    既然 FLT(4) 已证, 由观察 2, 接下来只需考虑 `n` 为奇素数的情形. 然而, 费马大定理是非常困难的问题, 即使我有绝妙证法, 这里的空白也太小写不下.

`133^5 + 110^5 + 84^5 + 27^5 = 144^5`

平方和

二平方和

二平方和恒等式 `(x_1^2+x_2^2)(y_1^2+y_2^2) = (x_1 y_1+x_2 y_2)^2 + (x_1 y_2-x_2 y_1)^2`. 从而, 如果整数 `m, n` 能表示为两个整数的平方之和, 则 `mn` 也能.

素数 `p` 能表为两个整数的平方和当且仅当 `p = 2` 或 `p -= 1 (mod 4)`. 换言之, `4k+3` 型的素数不能表示为两个整数的平方和.

  1. `p = 2` 时显然有 `2 = 1^2 + 1^2`. 注意整数 `a` 的平方模 4 余 0 或 1, 于是 `a^2 + b^2` 模 4 余 0, 1 或 2, 不可能为 3. 所以 `4k+3` 型素数不能表为平方和.
  2. 下设 `p = 4k+1`. 此时 `-1` 是模 `p` 的二次剩余, 故存在 `x, m` 使得 `x^2 + 1 = m p`, 其中 `1 le x le p-1`, 于是 `m p le (p-1)^2 + 1 le (p-1)p`, 从而 `m lt p`.
  3. 设 `m` 是使得关于 `x, y` 的不定方程 `x^2 + y^2 = m p` 有解的最小正整数, 由 2. 知 `m lt p`. 下证必有 `m = 1`. 首先, 若 `m` 是 `x, y` 的公因数, 则有 `m^2 | m p rArr m | p`, 再由 `m lt p` 推出 `m = 1`. 下设 `m` 不是它们的公因数, 从而 `m gt 1`, 我们来导出矛盾. 分别记 `a, b` 是 `x, y` 除以 `m` 的绝对最小余数, 则 `a, b` 不全为零, 且绝对值小于等于 `m//2`. 因此 `0 lt a^2 + b^2 le 2 (m//2)^2 = m^2//2`. 且 `a^2 + b^2 -= x^2 + y^2 -= 0` `(mod m)`, 从而 `a^2 + b^2 = m q`, `quad 0 lt q le m//2 lt m`.
  4. 下证 `p q` 可以表示成两个整数的平方和, 从而推翻假设. 由二平方和恒等式 `m^2 p q = (a^2+b^2)(x^2+y^2) = (a x+b y)^2 + (a y-b x)^2`, 其中 `a x + b y -= x^2 + y^2 -= 0 (mod m)`, `quad a y - b x -= 0 (mod m)`. 这指出 `m` 是 `a x + b y` 和 `a y - b x` 的公因数, 从而 两边可以同除 `m^2`, 但 `q lt m`, 与 `m` 的最小性矛盾. 证毕.

二平方和定理 正整数 `n` 能表为两个整数的平方和当且仅当它所有的 `4k+3` 型素因子在 `n` 中的次数为偶数.

  1. 充分性. 设 `n = t^2 n_1`, 其中 `n_1` 无平方因子. 若 `4k+3` 型素因子在 `n` 中的次数均为偶数, 则 `n_1` 不含 `4k+3` 型素因子, 因而 `n_1` 可以表为平方和 `a^2+b^2`, 进而 `n` 可以表为平方和 `(t a)^2 + (t b)^2`.
  2. 必要性. 设 `n = x^2 + y^2`, 但存在一个素因子 `p=4k+3`, 它在 `n` 中的次数为奇数, 设这个次数为 `2j+1`. 我们可以从 `n = x^2 + y^2` 两边约去公因子 `d^2`, 而且 `p` 在 `n//d^2` 中的次数仍为奇数. 因此不妨设 `x, y` 互素. 如果 `p|x`, 则由 `p|n` 知 `p|y`, 与 `x, y` 互素矛盾. 所以 `p!|x`, `p!|y`, 此时存在整数 `z` 使得 `x z -= y` `(mod p)`. 从而有 `(1+z^2) x^2 -= x^2 + y^2 -= n -= 0` `(mod p)`, 于是 `1 + z^2 -= 0` `(mod p)`, 即 `-1` 是模 `p` 的二次剩余, 和 `p = 4k+3` 矛盾.

四平方和

本节将证明, 任意正整数可以表为四个整数的平方和. 其证明思路与二平方和定理类似.

[来自百度百科]

Lagrange 恒等式 设 `n in ZZ^+`, `x_i, y_i in RR`, `i = 1, 2, cdots, n`, 则 `(sum_(i=1)^n x_i^2)(sum_(i=1)^n y_i^2)` `= (sum_(i=1)^n x_i y_i)^2 + sum_(1 le i lt j le n) (x_i y_j - x_j y_i)^2`. 从向量的角度理解: `|bm x|^2 |bm y|^2 = |bm x * bm y|^2 + |bm x xx bm y|^2`.

右边 `= sum_(i=1)^n x_i^2 y_i^2 + 2 sum_(1 le i lt j le n) x_i y_i x_j y_j + sum_(1 le i lt j le n) x_i^2 y_j^2` `- 2 sum_(1 le i lt j le n) x_i y_j x_j y_i + sum_(1 le i lt j le n) x_j^2 y_i^2` `= sum_(i=1)^n x_i^2 y_i^2 + sum_(1 le i lt j le n) x_i^2 y_j^2 + sum_(1 le i lt j le n) x_j^2 y_i^2 =`左边.

四平方和恒等式 (Euler, 1743) `(sum_(i=1)^4 x_i^2)(sum_(i=1)^4 y_i^2) = sum_(i=1)^4 z_i^2`. 其中 `z_1 = x_1 y_1 + x_2 y_2 + x_3 y_3 + x_4 y_4`,
`z_2 = x_1 y_2 - x_2 y_1 + x_3 y_4 - x_4 y_3`,
`z_3 = x_1 y_3 - x_3 y_1 + x_4 y_2 - x_2 y_4`,
`z_4 = x_1 y_4 - x_4 y_1 + x_2 y_3 - x_3 y_2`. 从而, 如果整数 `m, n` 能表示为四个整数的平方之和, 则 `mn` 也能.

由 Lagrange 恒等式, 只需验证 `(x_1 y_2 - x_2 y_1)(x_3 y_4 - x_4 y_3)` `- (x_1 y_3 - x_3 y_1)(x_2 y_4 - x_4 y_2)` `+ (x_1 y_4 - x_4 y_2)(x_2 y_3 - x_3 y_2) = 0`. 即可. 上式的左边可由 Laplace 定理展开行列式 `|x_1,x_2,x_3,x_4; y_1,y_2,y_3,y_4; x_1,x_2,x_3,x_4; y_1,y_2,y_3,y_4|` 得到.

如果令 `bm x, bm y, bm z` 表示四元数 `bm x = x_1 - x_2 bb i + x_3 bb j - x_4 bb k`,
`bm y = y_1 + y_2 bb i - y_3 bb j + y_4 bb k`,
`bm z = z_1 + z_2 bb i - z_3 bb j + z_4 bb k`, 则 `bm x bm y = x_1 y_1 + x_2 y_2 + x_3 y_3 + x_4 y_4` `+ (x_1 y_2 - x_2 y_1 + x_3 y_4 - x_4 y_3) bm i` `- (x_1 y_3 - x_3 y_1 + x_4 y_2 - x_2 y_4) bm j` `+ (x_1 y_4 - x_4 y_1 + x_2 y_3 - x_3 y_2) bm k` `= bm z`. 因此四平方和恒等式可以简记为 `|bm x| |bm y| = |bm x bm y|`.

(Euler, 1751) 对任意奇素数 `p`, 同余方程 `x^2+y^2+1 = 0` `(mod p)` 存在整数解 `0 le x, y lt p//2`. 因此对任意奇素数 `p`, 存在正整数 `m` 和整数 `0 le x, y le (p-1)//2`, 使得 `m p = x^2 + y^2 + 1 le (p-1)^2//2 + 1` `lt (p-1)(p+1) + 1 = p^2`. 因此 `m lt p`.

模 `p` 的二次剩余 (即全体平方数 `ZZ^2` 模 `p` 的同余类) 有 `(p+1)//2` 个, 分别为 `0, 1^2, 2^2, cdots, ((p-1)/2)^2`. 若 `(p-1)//2` 是模 `p` 的二次剩余, 则存在 `0 le x lt p//2` 使得 `x^2 -= (p-1)//2` `(mod p)`, 于是 `1 + x^2 + x^2 -= 0` `(mod p)`, 定理得证.
若 `(p-1)//2` 不属于模 `p` 的二次剩余, 将模 `p` 的剩余 (即全体整数模 `p` 的同余类) 分为如下 `(p-1)//2` 组: `{0, p-1}, {1, p-2}, cdots, {(p-1)/2, (p-1)/2}`. 而模 `p` 的 `(p+1)//2` 个二次剩余必然落在前 `(p-3)//2` 组当中. 由鸽巢原理, 必有两个二次剩余落在同一组中. 由于每一组的两个元素 `m, n` 满足 `m + n + 1 -= 0` `(mod p)`, 故存在整数 `x, y`, `0 le x, y lt p/2`, 使 `x^2 + y^2 + 1 -= 0` `(mod p)`.

四平方和定理 (Lagrange, 1770; Euler, 1773) 任何非负整数都可以表示为四个整数的平方之和, 即不定方程 `x_1^2 + x_2^2 + x_3^2 + x_4^2 = n`, `quad n ge 0` 恒有整数解.

  1. 显然定理对 `n = 0, 1, 2` 成立: `0 = 0^2 + 0^2 + 0^2 + 0^2`,
    `1 = 0^2 + 0^2 + 0^2 + 1^2`,
    `2 = 0^2 + 0^2 + 1^2 + 1^2`.     从而由四平方和恒等式知, 只需证定理对任意奇素数 `p` 成立. 又由, 存在最小的正整数 `m lt p` 使得 `m p` 能表示为四个整数的平方和: `m p = x_1^2 + x_2^2 + x_3^2 + x_4^2`.
  2. 下证 `m` 不是偶数, 否则 `m p` 为偶数, `x_i, i = 1, 2, 3, 4` 中的奇数只能是偶数个 (即 0, 2, 4 个). 不失一般性, 设 `x_1, x_2` 奇偶性相同, 且 `x_3, x_4` 奇偶性相同, 则 `x_1+-x_2`, `x_3+-x_4` 均为偶数, 得到 `(m//2)p = ((x_1+x_2)/2)^2 + ((x_1-x_2)/2)^2` `+ ((x_3+x_4)/2)^2 + ((x_3-x_4)/2)^2`. 然而 `m//2 lt m`, 这与 `m` 的最小性矛盾.
  3. 下证 `m = 1`. 首先, 若 `m` 为 `x_1, x_2, x_3, x_4` 的公因数, 则有 `m^2 | m p` `rArr m | p`, 再由 `m lt p` 推出 `m = 1`. 下设 `m` 不是它们的公因数, 从而 `m` 是大于 `1` 的奇数, 我们来导出矛盾. 取 `y_i` 为 `x_i` 除以 `m` 的绝对最小余数, `i = 1, 2, 3, 4`: `y_i -= x_i` `(mod m)`, `quad i = 1, 2, 3, 4`. 则 `y_i` 不全为零, 且绝对值小于 `m//2` (注意 `m` 是奇数). 因此 `0 lt sum_(i=1)^4 y_i^2 lt 4(m/2)^2 = m^2`, 且 `sum_(i=1)^4 y_i^2 -= sum_(i=1)^4 x_i^2 -= 0` `(mod m)`, 从而 `sum_(i=1)^4 y_i^2 = m q`, `quad 0 lt q lt m`.
  4. 下证 `p q` 可以表示成四个整数的平方和, 从而推翻假设. 由四平方和恒等式, 令 `sum_(i=1)^4 z_i^2 = (sum_(i=1)^4 x_i^2) (sum_(i=1)^4 y_i^2) = m^2 p q`, 其中 `z_1 = x_1 y_1 + x_2 y_2 + x_3 y_3 + x_4 y_4`,
    `z_2 = x_1 y_2 - x_2 y_1 + x_3 y_4 - x_4 y_3`,
    `z_3 = x_1 y_3 - x_3 y_1 + x_4 y_2 - x_2 y_4`,
    `z_4 = x_1 y_4 - x_4 y_1 + x_2 y_3 - x_3 x_2`.     由 `x_i -= y_i (mod m)`, `i = 1, 2, 3, 4`, 有 `z_1 -= sum_(i=1)^4 x_i^2 -= 0` `(mod m)`,
    `z_i -= 0 (mod m)`, `i = 2, 3, 4`.     这指出 `m` 是 `z_1, z_2, z_3, z_4` 的公因数, 从而 `p q = sum_(i=1)^4 (z_i//m)^2`. 但 `q lt m`, 与 `m` 的最小性矛盾. 证毕.

说明: 将整数分解为 4 个整数的平方和, 结果不唯一, 这里只给出一个解. 使用最朴素的暴力方法, 对于大素数性能较差.

Pell 方程

设 `d` 为正整数, 且不是平方数, 下面的不定方程称为 Pell 方程: `x^2 - d y^2 = 1`.

Pell 方程的幂形式解 将 Pell 方程的全部正整数解 `x_k, y_k` (后面会证明 Pell 方程确实有解) 按 `lambda_k = x_k + sqrt d y_k` 的值由小到大排列, 有 `lambda_k = lambda_1^k`, `quad k = 1, 2, cdots`. 因此, 由 Pell 方程的最小正整数解 `x_1, y_1` 可以轻松得到通解.

    取共轭 `lambda_k' = x_k - sqrt d y_k`, 由 `x_k, y_k` 满足 Pell 方程知道 `lambda_k lambda_k' = 1`. 下面证明, Pell 方程的正整数解 `x, y` 均满足 `x + sqrt d y = lambda_1^k`, 其中 `k` 为某个正整数.
  1. 记 `x + sqrt d y = lambda_1^k`, 由于 `(x + sqrt d y)(x - sqrt d y)` `= lambda_1^k (lambda_1^k)'` `= lambda_1^k (lambda_1')^k` `= (lambda_1 lambda_1')^k = 1`, 所以 `x, y` 是一组正整数解.
  2. 反之令 `x, y` 是一组正整数解, 且 `lambda = x + sqrt d y` 不等于任何一个 `lambda_1^k`. 因为 `lim_(k to oo) lambda_1^k = oo`, 可以设 `lambda_1^k lt lambda lt lambda_1^(k+1)` 同乘以 `lambda_1^-k = (lambda_1')^k` 得 `1 lt s + sqrt d t lt lambda_1`, 其中 `s + sqrt d t = lambda (lambda_1')^k`. 注意到 `0 lt s - sqrt d t lt 1 lt s + sqrt d t`, 有 `s = 1/2((s + sqrt d t) + (s-sqrt d t)) gt 0`,
    `t = 1/(2 sqrt d) ((s + sqrt d t) - (s - sqrt d t)) gt 0`,     且 `(s + sqrt d t)(s - sqrt d t)` `= lambda (lambda_1')^k lambda' lambda_1^k = 1`, 说明 `s, t` 也是一组正整数解, 然而 `s + sqrt d t lt lambda_1`, 与 `lambda_1` 的最小性矛盾.

设 `d in ZZ^+` 不是平方数, 若不定方程 `x^2 - d y^2 = n` 有最小正整数解 `x_0, y_0`, 则通解 `mu = x + sqrt d y` 由下式给出: `mu_k = mu_0 lambda_1^k`, `quad k = 0, 1, 2, cdots`. 其中 `lambda_1` 对应 Pell 方程 `x^2 - d y^2 = 1` 的最小正整数解.

  1. 首先验证 `mu_k = x_k + sqrt d y_k` 确实给出方程的解. 我们有 `(x_k + sqrt d y_k)(x_k - sqrt d y_k)` `= mu_k mu_k'` `= mu_0 mu_0' lambda_1^k (lambda_1')^k` `= mu_0 mu_0'` `= n`.
  2. 反之令 `x, y` 是一组正整数解, 且 `mu = x + sqrt d y`, 类似可证 ??
  1. 稍加尝试可以知道, 不定方程 `x^2 - 2 y^2 = 1` 的最小正整数解为 `(3, 2)` (依次尝试 `y = 1, 2, 3...`, 看 `1 + 2y^2` 何时为平方数). 记 `lambda = 3 + 2 sqrt 2`, 则 `lambda^2 = 17+12√2`, `lambda^3 = 99+70√2`, `lambda^4 = 577+408√2`, `cdots` 对应于正整数解 `(17, 12)`, `(99, 70)`, `(577, 408)`, `cdots`.
  2. 不定方程 `x^2 - 2 y^2 = 2` 的最小正整数解为 `(2, 1)`. 这个方程的通解由下式生成: `(2+√2)(3+2√2)^n`, `quad n = 0, 1, 2, cdots` 即 `2+√2`, `10+7√2`, `58+41√2`, `338+239√2`, `1970+1393√2`, `cdots` 其中 `(3, 2)` 是 1. 中方程的最小正整数解.

化简 `root 3 (20+14sqrt2)`.

记 `lambda = x + y sqrt2`, 其共轭 `lambda' = x - y sqrt2`. 如果 `lambda^3 = 20+14 sqrt2`, 则有 `(x^2 - 2 y^2)^3` `= (lambda lambda')^3` `= lambda^3 (lambda^3)'` `= (20 + 14 sqrt2)(20-14 sqrt2) = 2^3`. 解不定方程 `x^2 - 2 y^2 = 2`, 得到最小正整数解 `x = 2`, `y = 1`, 发现恰有 `root 3 (20+14sqrt2) = 2 + sqrt 2`.

若 `d` 是正整数且不是平方数, 不定方程 `x^2 - d y^2 = n^k` 有正整数解 `x_k, y_k`, 问 `x^2 - d y^2 = n` 是否有正整数解 `x_1, y_1`, 使得 `(x_1 + sqrt d y_1)^k = x_k + sqrt d y_k` ?

我们来说明 Pell 方程确实有解.

Pell 方程的连分数解 设 `d in ZZ^+` 不是平方数, `p_k//q_k` 是 `sqrt d` 的简单连分数的第 `k` 个收敛子. 记这个连分数的循环节长度为 `n`, 则 `p_(j n-1)^2 - d q_(j n-1)^2 = (-1)^(j n)`, `quad j = 1, 2, 3, cdots`. 上式给出了 Pell 方程 `x^2 - d y^2 = +-1` 的所有正整数解 `(p_(j n-1), q_(j n-1))`. 具体列表如下:
`x^2 - d y^2 = 1` `x^2 - d y^2 = -1`
`n` 为偶数 `j = 1, 2, 3, ...` 无解
`n` 为奇数 `j = 2, 4, 6, ...` `j = 1, 3, 5, ...`

椭圆曲线

[Elliptic Curve Cryptography: a gentle introduction]
    设直线 `y = k x + c` 与椭圆曲线 `y^2 = x^3 + a x + b` (`4a^3 + 27b^2 != 0`) 交于 `P_i(x_i, y_i)` `(i = 1, 2, 3)` 三点 (当其中两点重合时, 直线与曲线相切). 联立方程, 由 Vieta 定理知 `x_1 + x_2 + x_3 = k^2`. 于是当已知 `P_1`, `P_2` 时, `P_3` 的坐标为 `x_3 = k^2 - x_1 - x_2`,
    `y_3 = y_1 + k(x_3-x_1)` `= y_2 + k(x_3-x_2)`.     我们规定椭圆曲线上的点之间的加法运算, 使得它构成 Abel 群:
  1. 加法零元是竖直方向上的无穷远点, 记为 0;
  2. 加法逆元关于 `x` 轴对称;
  3. 若椭圆曲线上 `P_1, P_2, P_3` 三点共线, 则 `P_1 + P_2 + P_3 = 0`. 上式可以写为 `P_1 + P_2 = -P_3`, 即 `P_1 + P_2` 和 `P_3` 关于 x 轴对称. 上式对于其中一点是切点或无穷远点的情形仍成立: 若 `P` 是切点, 则切线与曲线的另一交点 `Q` 满足 `2P + Q = 0`; 若 `P, Q` 关于 x 轴对称, 则它们可以看作与竖直方向的无穷远点共线, 故 `P + Q = 0`.
    4. 椭圆曲线上的全体点关于这一加法构成 Abel 群. 又 `P_3` 的坐标是 `P_1, P_2` 的坐标的有理函数, 所以椭圆曲线上全体有理点是它的一个子群.

[来自 知乎专栏] 求这个不定方程的正整数解: `(🍎)/(🍌+🍍) + (🍌)/(🍍+🍎) + (🍍)/(🍎+🍌) = 4`,
`(a)/(b+c) + (b)/(c+a) + (c)/(a+b) = 4`.

此题可以通过椭圆代数曲线的理论解决. 一组可能的解是 a=154476802108746166441951315019919837485664325669565431700026634898253202035277999,
b=36875131794129999827197811565225474825492979968971970996283137471637224634055579,
c=4373612677928697257861252602371390152816537558161613618621437993378423467772036. 首先该方程是齐次的: 若 `(a,b,c)` 是解, 则 `(t a, t b, t c)` 也是解. 方程变形为 `a^3+b^3+c^3 = 3(a^2 b+a b^2+a^2 c+a c^2+b^2 c+b c^2) + 5abc`. 作代换 (??) `a = (56-x+y)/(56-14x)`, `quad b = (56-x-y)/(56-14x)`, `quad c = (-28-6x)/(28-7x)`, 即 `x = -28(a+b+2c)/(6a+6b-c)`, `quad y = 364(a-b)/(6a+6b-c)`, 方程化为 `gamma: quad y^2 = x^3 + 109 x^2 + 224 x`. 代数曲线 `gamma` 上存在有理点 `P = (-100, 260)`. 过 `P` 作 `gamma` 的切线, 与 `gamma` 交于另一点 `Q`, 点 `Q` 关于 `x` 轴的对称点记为 `2P`: 2P = P + P = (8836/25, -950716/125) 连接 `P` 与 `2P` 两点, 所得直线与 `gamma` 交于另一点, 该点关于 `x` 轴的对称点记为 `3P`: 3P = P + 2P = (-731025/11881, 527529870/1295029) 类似得到 6P = 3P + 3P = (252785840525963937198721/13225347684085115955600, -343764653760831645784970282294394569/1520934975898868459000385442296000), 9P = 3P + 6P = (-66202368404229585264842409883878874707453676645038225/13514400292716288512070907945002943352692578000406921, 58800835157308083307376751727347181330085672850296730351871748713307988700611210/1571068668597978434556364707291896268838086945430031322196754390420280407346469). 将 `9P` 这一点代回原变元 a, b, c: (a,b,c) = (652194680638776317370751188686261401138670498641722947/826345176768069653846031682295795260307016241032351542, 72627067629030455550043880234643101653454184810448427/385489402115598358968822193146517732601759618776822382, 18811002229321433251069036843190834369329875858835562/841819787025663175191882291647234536827567920526661363). 放大适当倍数即得答案.

`bbb F_p` 上的椭圆曲线 是指集合 `{0} uu {(x, y) in bbb F_p^2 | y^2 -= a x^3 + b x + c (mod p)}`, `quad 4a^3 + 27b^2 !-= 0 (mod p)`. `bbb F_p` 上的椭圆曲线的加法与 `RR` 上的定义完全相同, 只不过它的运算是模 `p` 的. 关于 `bbb F_p` 上的椭圆曲线, 一个困难的问题是: 已知两点 `P, Q`, 求 `k` 使得 `Q = k P`, 这称为椭圆曲线上的离散对数问题, 也是许多加密算法的基础.

Schoof 算法 可在多项式时间内求椭圆曲线群 `G` 的阶. 知道了群 `G` 的阶后, 元素 `P` 的阶就是 `G` 的因子中使得 `k P = 0` 成立的最小 `k`.
给定素数 `q`, 可按如下方法在 `G` 中找一个 `q` 阶元: 计算 `|G| // q = h`, 然后任取 `P in G`, 则 `q(h P) = |G| P = 0`, 这指出 `h P` 的阶是 `q` 的因子, 但 `q` 为素数, 所以 `h P = 0` 或 `|h P| = q`.