根式运算

化简二重根式 记 `sqrt(u^2-v) = n`, 则 `sqrt(u+-sqrt v) = sqrt((u+n)/2) +- sqrt((u-n)/2)`. 如 `sqrt((3-sqrt 5)/2) = (sqrt 5 - 1)/2`, `sqrt(2+sqrt 3) + sqrt(2-sqrt 3) = sqrt 6`, `sqrt(-1+2"i") + sqrt(-1-2"i") = sqrt(2sqrt5-2)` 等等.

记 `a = u + sqrt v`, `b = u - sqrt v`, 则 `sqrt a +- sqrt b` `= sqrt(a + b +- 2 sqrt(a b))` `= sqrt(2(u +- n))`. 解出 `sqrt a`, `sqrt b` 即得结论.

等号右边可以有超过两项吗? 我们考虑 `(sqrt a + sqrt b + sqrt c)^2` `= a+b+c+2(sqrt(ab) + sqrt(bc) + sqrt(ca))`, 其中 `a b, b c, c a` 至少两个数有相同的非平方因子. 这里的非平方因子是指从一个数中约去最大的平方因子的结果. 不妨设 `a b, b c` 有相同的非平方因子 `d`, 那么 `a b * b c // d^2` 是平方数, 即 `a c` 是平方数. 反设 `a, b, c` 的非平方因子均不相同, 特别 `a, c` 有不同的非平方因子, 那么 `a c` 不可能为平方数. 因此, `a, b, c` 中至少两个数有相同的非平方因子. 换言之等号右边最多只有两项.

一元多项式方程

二次方程

熟知一元二次方程 `a x^2 + b x + c = 0`, `a, b, c in RR`, `a != 0` 的求根公式为 `x_(1,2) = (-b +- sqrt(b^2-4 a c))/(2 a)`. 于是, 方程在 `Delta = b^2 - 4 a c gt 0` 时有两个不同实根, `Delta = 0` 时有一对实二重根, `Delta lt 0` 时有一对共轭复根.
一元二次方程的 Vieta 定理是说, `x_1 + x_2 = -b/a`, `quad x_1 x_2 = c/a`. 最后, 如果 `c != 0`, 则方程 `a + b y + c y^2 = 0` 的根存在, 且满足 `y_1 = x_2^-1, y_2 = x_1^-1`, 其中 `y_(1,2) = (-b +- sqrt(b^2-4 a c))/(2 c)` `= (2 a)/(-b ∓ sqrt(b^2-4 a c))`.

也可以由 Vieta 定理得到一元二次方程的求根公式: 设 `a x^2+b x + c = 0` 的两根为 `A+B`, `A-B`, 则 `(A+B) + (A-B) = -b/a`, `quad (A+B)(A-B) = c/a`. 解得 `A = -b/(2a)`, `B = +-sqrt(b^2-4a c)/(2a)`.

一般的一元 `n` 次方程形如 `a_n x^n + a_(n-1) x^(n-1) + cdots + a_1 x + a_0 = 0`, `quad a_n != 0`. 两边同除以 `a_n`, 就可将方程左边化为首一 (最高次项系数为 1) 的多项式: `x^n + b_(n-1) x^(n-1) + cdots + b_1 x + b_0 = 0`. 再作变元替换 `x = y - b_(n-1)/n` (即配 `n` 次方), 可将 `n-1` 次项系数化为零: `y^n + c_(n-2) y^(n-2) + cdots + c_1 y + c_0 = 0`. 下面我们就从首一的, `n-1` 次项系数为零的方程入手, 讨论三次和四次方程的解法.

三次方程

解三次方程 `x^3 + p x + q = 0`.

(Cardano 公式) 令 `x = u + v`, 代入方程有 `u^3 + v^3 + (3 u v + p)(u+v) + q = 0`. 可见 `x` 是方程的解的一个充分条件是 `{ u^3 + v^3 = -q; 3 u v = -p; :}` 令 `alpha = u^3`, `beta = v^3`, 则 `alpha`, `beta` 应当满足 `{ alpha + beta = -q; alpha beta = -p^3/27; :}` 从而由一元二次方程根与系数的关系 (Vieta 定理), `alpha`, `beta` 是 关于 `z` 的方程 `z^2 + q z -p^3/27 = 0` 的两根, 即 `alpha, beta = -q/2 +- sqrt((q/2)^2 + (p/3)^3)`. 以 `omega = -1/2 + (sqrt 3)/2 "i"` 记三次方程 `x^3 = 1` 的一个根, 又记 `root 3 alpha`, `root 3 beta` 分别为三次方程 `u^3 = alpha`, `v^3 = beta` 的一个根, 且满足 `root 3 alpha root 3 beta = -p//3` (在 `p` 为实数时, 将 `root 3 alpha` 和 `root 3 beta` 取为实数, 或一对共轭复数即可). 容易验证, `u^3 = alpha` 的全部根和 `v^3 = beta` 的全部根为 (注意, `n` 次多项式最多只有 `n` 个根) `u = root 3 alpha, omega root 3 alpha, omega^2 root 3 alpha`,
`v = root 3 beta, omega root 3 beta, omega^2 root 3 beta`. 再利用 `u v = -p//3`, 原方程的三个根为: `root 3 alpha + root 3 beta`, `omega root 3 alpha + omega^2 root 3 beta`, `omega^2 root 3 alpha + omega root 3 beta`.

    (三角解法, 苏剑林. (2010, Aug 08). 《三次方程的三角函数解法 》[Blog post].) 假设 `p, q in RR`. 引理: 三角恒等式 (前两个是万能代换的变形, 后一个是三倍角公式) `2/(tan 2A) = 1/(tan A) - tan A`,
    `2/(sin 2A) = 1/(tan A) + tan A`,
    `cos 3A = 4cos^3 A - 3 cos A`.     `p = 0` 时, 容易得到惟一实根 `x = root 3 (-q)`. `p != 0` 时, 设 `r = -q |3/p|^(3/2)`, 下面分三种情形讨论方程的解法.
  1. `p gt 0` 时, 令 `x = sqrt(p/3) z` 得 `z^3 + 3 z = r`. 再令 `z = w^-1 - w`, 有 `w^-3 - w^3 = (w^-1 - w)(w^-2 + 1 + w^2)` `= z(z^2 + 3) = r`. 令 `w^3 = tan A`, 由引理, `2/(tan 2A) = r`, `quad A = 1/2 arctan{:2/r:}`, `quad w = root 3(tan A)`. 由于 `"d"/(dz) (z^3 + 3 z) = 3 z^2 + 3 gt 0`, 函数 `z^3 + 3 z` 在 `(-oo, +oo)` 上单调增, 且取遍一切实数值, 所以 `z^3 + 3 z = r` 恒有一个实根.
  2. `p lt 0`, `|r| ge 2` 时, 令 `x = sqrt(|p|/3) z` 得 `z^3 - 3 z = r`. 再令 `z = w^-1 + w`, 有 `w^-3 + w^3 = (w^-1 + w)(w^-2 - 1 + w^2)` `= z(z^2 - 3) = r`. 令 `w^3 = tan A`, 由引理, `2/(sin 2A) = r`, `quad A = 1/2 arcsin{:2/r:}`, `quad w = root 3(tan A)`. 由反正弦函数的定义域知, 上述公式只对 `|r| ge 2` 有效. 事实上, 由 `"d"/(dz) (z^3 - 3 z) = 3 z^2 - 3` 知, 函数有两个极值点 `z = +- 1`, 因而容易推出 `z^3 - 3 z = r` 在 `|r| gt 2` 时只有一实根, `|r| = 2` 时有一对实的重根和另一实根, 而 `|r| lt 2` 时, 有三个不同实根.
  3. `p lt 0`, `|r| lt 2` 时, 令 `z = 2 cos A`, 利用引理, `r = z^3 - 3 z = 2 (4 cos^3 A - 3 cos A) = 2 cos 3A`,
    `A = 1/3 (arccos{:r/2:} + 2 k pi)`, `quad k = 0, 1, 2`.
    (盛金公式) 方程 `a x^3 + b x^2 + c x + d = 0`, `quad a, b, c, d in RR`. 计算三个重根判别式: `A = b^2 - 3 a c`,
    `B = b c - 9 a d`,
    `C = c^2 - 3 b d`     和总判别式 `Delta = B^2 - 4 A C`, 有:
  1. `A = B = 0` 时, 有三重实根 `x_(1, 2, 3) = -b/(3a) = -c/b = -(3d)/c`.
  2. `Delta = 0`, 且 `A != 0` 时, 有一实单根和一实二重根 `x_1 = B/A - b/a`, `quad x_(2,3) = -B/(2A)`.
  3. `Delta gt 0` 时, 有一实根, 一对共轭复根 `x_1 = (-b - (root 3 y_1 + root 3 y_2))/(3a)`,
    `x_(2, 3) = (-b + 1/2(root 3 y_1 + root 3 y_2) +- (sqrt 3)/2(root 3 y_1 - root 3 y_2)"i")/(3 a)`.     其中 `y_(1, 2) = A b + 3 a((-B+-sqrt Delta)/2)`.
  4. `Delta lt 0`, `A gt 0`, 且 `T = (2 A b - 3 a B)/(2 sqrt (A^3)) in [-1, 1]` 时, 有三个不同实根 `x_1 = (-b - 2 sqrt A cos{:theta/3:})/(3 a)`,
    `x_(2, 3) = (-b + sqrt A(cos{:theta/3:} +- sqrt 3 sin{:theta/3:}))/(3 a)`.     其中 `theta = arccos T`.
    三次方程 `x^3 + p x + q = 0` (`p, q in RR`) 的判别式记为 `Delta = (q//2)^2 + (p//3)^3`.
  1. `Delta gt 0` 时, 方程有一实根, 一对共轭复根;
  2. `Delta lt 0` 时, 方程有三个不同的实根; 记 Cardano 公式中的 `alpha, beta = r "e"^(+-"i"theta)`, 则三个根是 `2 * root 3 r cos(theta/3 + varphi)`, `quad varphi = 0, (2pi)/3, (4pi)/3`.
  3. `Delta = 0` 时, 方程有一个一重实根 `-2 root 3(q//2)`, 一个两重实根 `root 3(q//2)`.

解方程 `27 x^3 + 54 x^2 - 369 x - 370 = 0`.

最高次项系数化为 1, `x^3 + 2 x^2 - 41/3 x -370/27 = 0`. 令 `x = y - 2/3`, `y^3 - 15 y - 4 = 0`. 故 `q/2 = -2`, `p/3 = -5`, `Delta = (q/2)^2 + (p/3)^3 lt 0`, 有三个不 同实根. 解得 `alpha = 2 + 11"i" = (2+"i")^3`, `quad beta = 2 - 11"i" = (2-"i")^3`. 所以三个实根为 `4, -2-sqrt3, -2+sqrt3`. 而原方程的根为 `10/3, -8/3-sqrt3, -8/3+sqrt3`.

  1. 化简 `root 3(3+sqrt(275/27)) + root 3(3-sqrt(275/27)) = root 3 2`.
  2. 化简 `root 3(2+sqrt 5) = (1+sqrt 5)/2`.
  3. 化简 `root 3(2+11 "i") + root 3(2-11 "i") = 4`.
  1. 利用 Cardano 公式 `root 3(-q/2 + sqrt((q/2)^2 + (p/3)^3))` `+ root 3(-q/2 - sqrt((q/2)^2 + (p/3)^3))`, 原式化为方程 `x^3 + 2^(5/3) x - 6 = 0` 的一根. 由于判别式大于 0, 该方程只有一个实根, 观察知该实根等于 `root 3 2`.
  2. 利用 Cardano 公式, `root 3(2+sqrt 5) + root 3(2 - sqrt 5)` 是 `x^3 + 3x - 4` 的唯一实根, 观察知 `x = 1`. 又 `root 3(2+sqrt 5) root 3(2-sqrt 5) = -1`, 于是由 `u + v = 1`, `u v = -1` 解得 `u, v = (1 +- sqrt 5)/2`. 其中 `root 3(2+sqrt 5)` 取较大的一个, 即 `(1+sqrt 5)/2`.
  3. 表达式含有虚数, 对应的三次方程有三个实根. 怎么办呢? 先注意到 `|2+11"i"| = sqrt(125)`, 所以 `|root 3 (2+11"i")| = sqrt 5`, 猜测 `(2+"i")^3 = 2+11"i"` 并验证即可. 于是原式等于 `2+"i"+2-"i" = 4`.

四次方程

解四次方程 `x^4 + p x^2 + q x + r = 0`.

设方程左侧可以因式分解为 `x^4 + p x^2 + q x + r = (x^2 - a x + b)(x^2 + a x + c)` 注意我们已将两个二次因式中的一次项系数设为相反数, 这是因为它们相乘的结果的三次项系数为零. 比较各次项系数有: `{ b + c -a^2 = p; a(b-c) = q; b c = r; :}` 由前两式得 `2a b = a(a^2 + p) + q`,
`2a c = a(a^2 + p) - q`. 代入第三式, `4a^2 r = a^2 (a^2 + p)^2 - q^2`, 即 `a^6 + 2p a^4 + (p^2 - 4r)a^2 - q^2 = 0`. 上式看作关于 `a^2` 的一元三次方程, 取它的任一根 (比如实根), 就可得到 `b, c` 的值, 进而解两个一元二次方程 `x^2 - a x + b = 0`, `quad x^2 + a x + c = 0` 得到原方程的根.

[来自 bilibili@千梓猫鹿] 一个类似三次方程 Cardano 公式的解法. 设 `x = u + v + w` 是方程的解, 则 `x^2 = sum u^2 + 2 sum u v`,
`x^4 = (sum u^2)^2 + 4(sum u^2)(sum u v)` `+ 4 sum u^2 v^2 + 8 u v w sum u`, 代入原方程得 `(sum u^2)^2 + 4 sum u^2 v^2` `+ (8 u v w + q) sum u + (4 sum u^2 + 2 p) sum u v` `+ p sum u^2 + r = 0`. 因此 `x` 是方程的解的充分条件为 `{ (sum u^2)^2 + 4 sum u^2 v^2 + p sum u^2 + r = 0; 8 u v w + q = 0; 4 sum u^2 + 2 p = 0; :}` 化简得到 `u^2, v^2, w^2` 满足的方程组: `{ sum u^2 = -p // 2; u^2 v^2 w^2 = (q//8)^2; sum u^2 v^2 = (p//4)^2 - r//4; :}` 利用 Vieta 定理, 它们是三次方程 `z^3 + p/2 z^2 + [(p/4)^2 - r/4] z - (q/8)^2 = 0` 的三根. 至此问题化为求解三次方程.

策略1: 两根和等于另外两根和 解方程 `x^4+6x^3+11x^2+6x-1 = 0`.

[来自群友 Gzz] 注意到左边可以写成 `(x^2+3x+1)^2-2`. 我注意不到😭

待定系数法. 令 `y = x(x+a)`, 再令方程左边等于 `y^2 + b y -1` `= x^4 + 2a x^3 + (a^2+b) x^2 + a b x -1`, 于是 `2a = 6`, `quad a b = 6`, `quad a^2+b=11`. 解得 `a = 3`, `b = 2`. 后面的处理是容易的.
一般地, 若四次方程的两根和等于另外两根和, 则它可以分解为 `(x^2+a x+b)(x^2+a x+c) = 0`, 进而可以采用上面令 `y = x(x+a)` 的换元方法.

策略2: 尝试在 `ZZ` 上分解 解方程 `x^4 + 5 x^3 + 2 x^2 + 20 x + 16 = 0`.

假设左边可以分解为 `(x^2 + a x + c)(x^2 + b x + d)`, 则 `a + b = 5`, `quad a b + c + d = 2`, `quad a d + b c = 20`, `quad c d = 16`. 假设 `c, d` 均为整数, 列举 16 的因子, 发现当 `c = d = 4` 时, 上述方程组有解: `a + b = 5`, `a b = -6`. 于是 `a, b` 是方程 `y^2 - 5 y - 6 = 0` 的两根, `{a, b} = {6, -1}`. 后面的处理是容易的.

[题源网络] 郭小弟有四個女朋友，恰好一個比一個大兩歲，且他們年齡的乘積是 3465，請問最大的女孩年齡是多少？

设她们年龄的平均值是 `x`, 则 `(x+1)(x-1)(x+3)(x-3) = 3465`, 上式可轻松化为 `x^2` 的二次方程, 这就避免了四次方程. 解得 `x = 8`, 于是四个女朋友的年龄分别是 5, 7, 9, 11 😅.

即使你不小心设了 `x` 是最小的那个年龄, 得到了下面这样的四次方程: `x^4 + 12x^3 + 44x^2 + 48x - 3465 = 0`, 没有关系! 由题意知道方程有两根和等于另外两根和, 故可以换元 `y = x(x+a)`, 方程化为 `y^2 + b y - 3465 = 0`. 解方程组 `2a = 12`, `quad a b = 48`, `a^2 + b = 44`, 得到 `a = 6`, `b = 8`. 先解 `y^2 + 8 y - 3465 = 0` 得 `y = 55, -63`; 再解 `x(x+6) = y` 得 `x = -3+-sqrt(9+y)`, 其中只有 `x=5` 符合题意.

Gauss 引理与 Eisenstein 判别法

    解高次方程的实用策略
  1. 消去重根. 从 `f(x)` 中约去 `(f(x), f'(x))`, 得到最多只含一重根的多项式. 最大公因式可用辗转相除法求.
  2. Gauss 引理 (见下文).
  3. Eisenstein 判别法 (见下文).
    Gauss 引理 称 `f in ZZ[x]` 是本原多项式, 如果它各系数的最大公约数是 1.
  1. 两个本原多项式的乘积仍是本原多项式.
  2. 若 `f in ZZ[x]` 在 `QQ` 上可约, 那么它也在 `ZZ` 上可约.
  3. 若 `f, g` 都是首一多项式, `f in ZZ[x]`, `g in QQ[x]`, 且 `g | f`, 那么 `g in ZZ[x]`.
  1. 设 `f, g in ZZ[x]` 是本原多项式, `h = f g`. 反设 `h` 不是本原多项式, 则存在素数 `p` 整除它的所有系数. 由于 `f, g` 本原, 存在最小的整数 `i, j` 使得 `p !| f_i`, `p !| g_j`. 考虑 `h` 的 `i+j` 次系数 `h_(i+j) = sum_(k=0)^(i+j) f_k g_(i+j-k)`, 由于所有 `f_k` `(k lt i)` 和 `g_(i+j-k)` `(k gt i)` 都被 `p` 整除, 因此 `h_(i+j) -= f_i g_j (mod p)`. 然而 `p !| f_i`, `p !| g_j`, 故 `p !| h_(i+j)`, 与假设矛盾.
  2. 设 `h in ZZ[x]` 在 `QQ` 上可约, 则存在不为常数的 `f_1, g_1 in QQ[x]` 使得 `h = f_1 g_1`. 适当选取有理数 `a, b`, 可使 `f := a f_1 in ZZ[x]` 和 `g := b g_1 in ZZ[x]` 都是本原多项式. 由 1. 知, `f g` 也是本原多项式, 因此 `h` 只能是 `f g` 的整数倍, 从而 `h` 在 `ZZ` 上可约.
  3. 由 2. 知存在 `k in QQ` 使得 `f = k g h`, 其中 `k g in ZZ[x]`, `h in ZZ[x]`. 但 `f, g` 首一, 为使 `h` 的首项系数为整数必须有 `k = +-1`. 所以 `g in ZZ[x]`.
    设 `f(x) = sum_(k=0)^n f_k x^k in ZZ[x]`.
  1. 有理根由首尾系数决定 如果 `c//d` 是 `f` 的有理根, 且为最简分数. 那么 `c | f_0`, `d | f_n`, 即分子整除常数项, 分母整除首项系数.
    推论1: `f` 首一时, 它的有理根只能是整数.
    推论2: 设 `a, n` 为正整数, 则 `root n a` 不是整数, 就是无理数.
  2. Eisenstein 判别法 设 `f` 的次数 `n ge 2`, 且存在素数 `p` 整除 `f` 首项系数以外的每个系数, 且 `p^2` 不整除常数项, 换言之: `p !| f_n`, `quad p^2 !| f_0`, `quad p | f_i` `quad (AA i lt n)`, 则 `f` 在 `QQ` 上不可约, 更不存在有理根.
  1. 将有理根 `c//d` 代入 `f`: `sum_(k=0)^n f_k c^k d^(n-k) = 0`. 等式两边分别模 `c` 可得 `f_0 d^n -= 0 (mod c)`. 但 `(c, d) = 1`, 故 `c | f_0`. 同理两边模 `d` 可得 `d | f_n`.
  2. 先证 `f` 不存在有理根. 假设 `c//d` 是一个有理根 (最简分数), 1. 中的等式两边模 `p` 得到 `f_n c^n -= 0 (mod p)`. 但已知 `p !| f_n`, 所以 `p | c`. 现在等式两边模 `p^2`. 由于 `n ge 2`, 除了常数项外各项均被 `p^2` 整除, 得到 `f_0 d^n -= 0 (mod p^2)`. 由于 `c, d` 互素, `p !| d`, 上式推出 `p^2 | f_0`, 矛盾.
  3. 现在证 `f` 实际上在 `QQ` 中不可约. 反设 `f` 可约, 则由 Gauss 引理它也在 `ZZ` 上可约: `f = g h`. 其中 `g` 是 `s` 次多项式, `h` 是 `n - s` 次多项式. 由 `f_0 = g_0 h_0` 和 `p | f_0`, `p^2 !| f_0` 得到 `p` 能且只能整除 `g_0, h_0` 中的一个. 不妨设 `p | g_0`, `p !| h_0`, 那么: `f_1 = g_0 h_1 + g_1 h_0 -= g_1 h_0 (mod p)`. 但 `f_1 -= 0 (mod p)`, 所以 `p | g_1`. 一般地, 设 `k le s lt n`, 且对任意 `j lt k` 成立 `p | g_j`, 则 `g_k h_0 = f_k - sum_(j=0)^(k-1) g_j h_(k-j)` `-= 0 (mod p)`. 从而 `p | g_k`. 由数学归纳法, `p` 整除 `g` 的各项系数, 从而整除 `f` 的各项系数, 这与 `p !| f_n` 矛盾.
    设 `p` 为素数,
  1. `n ge 2` 时, 由 Eisenstein 判别法, `x^n +- p` 在 `QQ` 上不可约.
  2. `f(x) = (x^p-1)/(x-1)` `= 1 + x + cdots + x^(p-1)` 在 `QQ` 上不可约.

只证 2. 令 `y = x-1`, 则 `f(x) = ((y+1)^p - 1) // y`, 这也是多项式, 且首项系数为 1, 常数项为 `p`, 且中间各项都被 `p` 整除. 由 Eisenstein 判别法知道它在 `QQ` 上不可约.

数域上的不可约多项式

本节讨论数域 `K supe QQ` 上的多项式.

    通常, `K` 上多项式可约, 不代表它一定有根. 但有两种情况, 可约一定有根:
  1. 对于 2 次或 3 次多项式, 可约一定有根.
  2. 对于 `K` 上的多项式 `f(x) = x^p - a`, 可约一定有根, `p` 是素数.

只证 2. 任取 `f` 的一个根 `u in CC`, 则 `f(x) = prod_(k=0)^(p-1) (x - u zeta_p^k)`, `quad zeta_p = "e"^(2 pi "i"//p)`, 现在设 `g` 是 `f` 的非平凡因式, 次数为 `n`, 则 `(n, p) = 1`. 考虑 `g` 的常数项 `g_0 = u^n zeta_p^m`, 其中 `m in ZZ`, 于是 `g_0^p = u^(p n) = a^n`. 但 `(n, p) = 1`, 所以存在 `x, y in ZZ` 使得 `n x + p y = 1`, 故 `(g_0^x * a^y)^p` `= g_0^(p x) * a^(p y)` `= a^(n x + p y)` `= a`. 这说明 `g_0^x * a^y in K` 是 `f` 的根.

我们称 `x^n = a` 是纯方程. 上例说明, 数域上的 `p` 次纯方程无根则一定不可约. 例如 `x^5 - 4` 在 `QQ` 上不可约.

数域 `K` 中 `n` 次非零多项式最多有 `n` 个根 (含重数).

对 `n` 归纳. `n = 0` 时命题成立. 设命题对 `n-1` 次非零多项式成立, 考虑 `n` 次多项式 `f`. 若 `f` 在 `K` 中无根, 命题成立; 否则任取一根 `alpha`, 由因式定理 `f(x) = (x-alpha) g(x)`, `g(x)` 是 `n-1` 次多项式, 由归纳假设最多有 `n-1` 个根, 于是 `f` 最多有 `n` 个根.

  1. 设 `f, g in K[x]` 有公共根 `alpha`, 且 `g` 不可约, 则 `g | f`, 从而 `g` 的所有根都是 `f` 的根.
  2. 设 `f in K[x]` 有一个根 `alpha`, 则存在不可约多项式 `g`, 使得 `alpha` 也是 `g` 的根.
  1. 由因式定理知道 `(f, g) != 1`, 但 `g` 不可约, 因此 `(f, g) = g` (只相差一个常数), 即 `g | f`.
  2. 记 `K[x]` 中全体以 `alpha` 为根的多项式集合为 `T`, 则 `f in T`, `T != O/`. `T` 中存在最小次数的多项式 `g`, `g` 必不可约, 否则 `g = u v`, `u, v` 当中必有一个以 `alpha` 为根, 且次数小于 `g`, 与 `g` 的取法矛盾.

数域上的不可约多项式无重根.

假设 `a` 是 `f` 的重根, 那么 `a` 也是 `f'` 的根, 由于 `f` 不可约, 立即得到 `f | f'`. 而 `"deg"(f') lt "deg"(f)`, 推出 `f' = 0`. `f` 不是常数, 而导数 `f' = 0`, 这在特征为零的域上是不可能的.

    仍不可约引理 [来自 知乎@IURT]
  1. 设 `f, g` 是 `K` 上的不可约多项式, 则它们无重根. 记 `alpha_i`, `i = 1, cdots, n` 是 `g` 的所有根. 若 `f` 在扩域 `K(alpha_1)` 上可约, 记 `f(x) = u(x, alpha_1) v(x, alpha_1)`, `quad u, v in K[x, y]`. 则 `f` 在每个扩域 `K(alpha_i)` 上都可约, 且有 `f(x) = u(x, alpha_i) v(x, alpha_i)`, `quad i = 1, cdots, n`.
  2. 假设同 1. 特别当 `f` 的次数 `p` 是素数时, `p` 必整除 `g` 的次数 `n`.
  3. 仍不可约引理 设 `f` 是 `K` 上的素数次不可约多项式, `g` 是 `K` 上次数小于 `f` 的多项式, 那么在添加 `g` 的任一根得到的扩域 `K(alpha)` 上, `f` 仍不可约. 例如, 设 `f` 是 `p` 次不可约多项式, 那么在添加 `p` 次单位根得到的扩域 `K(zeta_p)` 上 `f` 仍不可约.
  1. 固定一个有理数 `q in QQ sube K`, 定义 `h(x) = f(q) - u(q, x) v(q, x) in K[x]`, 由已知, `h(alpha_1) = 0`. 但 `alpha_1` 也是不可约多项式 `g in K[x]` 的根, 这意味 `g | h`, 从而 `g` 的所有根都是 `h` 的根: `h(alpha_i) = f(q) - u(q, alpha_i) v(q, alpha_i) = 0`. 上式对任意有理数 `q` 都成立, 这意味多项式 `f(x) - u(x, alpha_i) v(x, alpha_i) in K(alpha_i)[x]` 有无数个根, 从而只能是零多项式. 这就证明了 `f` 在 `K(alpha_i)` 上可约, 且 `f(x) = u(x, alpha_i) v(x, alpha_i)`.
  2. 将 `n` 个等式 `f(x) = u(x, alpha_i) v(x, alpha_i)`, `quad i = 1, cdots, n` 相乘得到 `f(x)^n = prod_(i=1)^n u(x, alpha_i) prod_(i=1)^n v(x, alpha_i)` `:= U(x) V(x)`. `U, V` 均是扩域 `L = K(alpha_1, cdots, alpha_n)` 上的多项式, 且各次项系数是关于 `alpha_i` 的对称多项式. 这意味着 `U, V` 的系数能用 `g` 的系数表出, 但 `g in K[x]`, 所以 `U, V in K[x]`. 注意 `f` 在 `K` 上不可约, 所以, 至多相差一个常数, 有 `U(x) = f(x)^a`, `quad V(x) = f(x)^b`. 检查上式的次数, 设 `deg u(x, alpha_i) = l`, 则 `deg U(x) = n l`, 另一方面 `deg f(x)^a = p a`, 所以 `n l = p a`. 注意 `l lt p`, 所以 `p | n`.
  3. 我们知道, 对于 `g` 和它的根 `alpha`, 存在一个 `g` 的不可约因式 `g_1`, 使得 `alpha` 也是 `g_1` 的根, 而 `g_1` 的次数仍小于 `f` 的次数. 假设 `f` 在 `K(alpha)` 上可约, 由 2. 知道 `p` 整除 `g_1` 的次数, 这是不可能的.

有限域上的不可约多项式

判断 `ZZ` 上多项式不可约的另一个方法是对素数 `p` 取模. 如果取模后的多项式不可约, 则原多项式也不可约. 这引出有限域上的多项式理论.

    有限域上不可约多项式的结构 考虑有限域 `bbb F_q`, `q` 为素数幂. 用 `Omega_n` 表示 `bbb F_q[x]` 中所有 `n` 次首一不可约多项式的集合.
  1. `x^(q^n) - x = prod_(f in Omega_d; d | n) f(x)`.
  2. 记 `N(n) = |Omega_n|`, 则 `q^n = sum_(d | n) d N(d)`.
  3. `N(n) = 1/n sum_(d | n) q^d mu(n//d)`.
  1. 首先任意 `f in Omega_d` 的根落在域 `bbb F_(q^d)` 中, 满足 `a^(q^d) = a`, 所以 `a` 也是 `F = x^(q^n) - x` 的根.
    反之若 `a` 是 `F` 的根, 则存在最小正整数 `d` 使得 `a^(q^d) = a`, 即 `a in bbb F_(q^d)`, `a` 是某个 `f in Omega_d` 的根. 注意 `bbb F_(q^d)` 是 `bbb F_q` 到 `bbb F_(q^n)` 的中间域, 所以扩张次数 `d | n`.
  2. 利用 1. 将 `x^(q^n) - x` 拆解为不可约多项式的乘积, 然后比较两边次数.
  3. 利用 Möbius 反演.

有限域上判定不可约多项式的 Rabin 判别法 [来自群友 stupidpig] 设 `p` 为素数, `n` 次多项式 `f(x) in bbb F_p[x]` 不可约当且仅当 `f | x^(p^n) - x`, 且对 `n` 的任意素因子 `q` 成立 `gcd(f, x^(p^(n//q)) - x) = 1`. 该判别法的时间复杂度是 `O((n log n log p)^2)`.

  1. 由公式 `F_n(x) := x^(p^n) - x` `= prod_(g in Omega_d; d | n) g(x)` `= prod_(g in Omega_n) g(x) prod_(g in Omega_d; d | n; d lt n) g(x)` `:= Pi_1 * Pi_2`. 知道, `n` 次多项式 `f` 不可约当且仅当它是 `F_n` 的因子, 且与 `Pi_2` 互素. 为了使 `gcd(f, Pi_2) = 1`, 只需对 `n` 的每个素因子 `q` 成立 `gcd(f, F_(n//q)) = 1`. 这是因为 `F_(n//q)` 由所有次数 `d | (n//q)` 的首一不可约多项式组成, 因此事实上 `prod_(q 是素数; q | n) F_(n//q)` 和 `Pi_2` 具有相同的不可约因式, 只不过前者的因式有重复而已.
    1. 预处理步骤: 枚举 `n` 的素因子花费时间 `O(sqrt n)`, 和后面的计算量相比可以忽略不计.
    2. 使用快速幂验证同余 `x^(p^n) -= x (mod f)` 需要做 `O(log(p^n)) = O(n log p)` 次多项式乘法和模运算. 借助快速 Fourier 变换 (FFT), 多项式乘法和模运算均可以在 `O(n log n)` 次域运算中完成. 每次域运算的时间以 `O(log p)` 计算. 这一步的总时间是 `O(n^2 log n log^2 p)`.
    3. gcd 部分. 先求 `x^(p^(n//q)) mod f` 将它的次数降到 `n` 以内. 和第一步一样, 花费时间 `O(n^2 log n log^2 p)`. 接下来求两个不超过 `n` 次多项式的 gcd, 需要做 `O(log n)` 次多项式模运算, 花费时间 `O(n log^2 n log p)`, 和前一项相比可以忽略不计. 由于 gcd 部分要对 `n` 的所有素因子进行, 而 `n` 的素因子个数少于 `log n`, 所以 gcd 部分花费时间 `O((n log n log p)^2)`.

区分“有根”与“可约” [来自群友 rei] 注意, 如果对 `a = 0, cdots, p-1` 均有 `f(a) != 0`, 只能说明 `f` 在 `bbb F_p` 上没有根, 不能说明它不可约. 比如: `x^5 + x + 1` 显然在 `bbb F_2` 上没有根, 因为它的常数项为 1, 且系数为 1 的项有奇数个, 即 `f(0) = f(1) = 1`. 但是它在 `ZZ` 上可约, 从而在 `bbb F_2` 上也是可约的: `x^5 + x + 1` `= (x^3 - x^2 + 1)(x^2 + x + 1)`. 当然, 若 `f` 的次数 `le 3`, 则此法奏效: `f` 不可约当且仅当它没有根.

    [来自群友 幂零群, Fran] 考虑 `bbb F_2` 上的多项式 `p_N(x) = x^N + x + 1`, `N` 为正整数. 手工验证 `N = 1, 2, 3, 4` 时 `p_N` 均不可约. 问 `N = 2^n`, `n ge 3` 时, `p_N` 都可约吗? 下面给出 `n ge 3` 为奇数以及 `n -= 2 (mod 4)` 时的证明:
  1. 当 `N = 3n+2` 时, `p_2 = x^2+x+1` 整除 `p_N`;
    当 `N = 7n+3` 时, `p_3 = x^3+x+1` 整除 `p_N`;
    当 `N = 15n+4` 时, `p_4 = x^4+x+1` 整除 `p_N`.
  2. 当 `N = 2^n`, `n` 为奇数时, `p_2 = x^2+x+1` 整除 `p_N`.
    当 `N = 2^n`, `n = 4k+2` 时, `p_4 = x^4+x+1` 整除 `p_N`.
  1. 事实上 `p_2 | x^3 - 1`. 进一步对任意 `n` 有 `x^3 - 1| x^(3n)-1 = x^(3n)+1`. 因此 `p_N -= x^(3n+2) + x^2` `-= x^2(x^(3n) + 1) -= 0 (mod p_2)`. 同理, 利用 `p_3 | x^7 - 1` 和 `p_4 | x^15-1` 可以推出后面两个结论. (`p_3` 是三次不可约多项式, 它的根属于 `bbb F_(2^3)`, 必定满足 `x^8 = x`; `p_4` 同理).
  2. 因为 `n` 为奇数时 `N = 2^n -= (-1)^n -= -1 -= 2 (mod 3)`, 所以 `p_2` 整除 `p_N`. 又因为 `n = 4k+2` 时 `N = 2^(4k+2) -= 4 * 16^k -= 4 (mod 15)`, 所以 `p_4` 整除 `p_N`.

对称多项式

若一个 `n` 元代数式 `f(x_1, x_2, cdots, x_n)` 对任意实数 `t` 满足 `f(t x_1, t x_2, cdots, t x_n) = t f(x_1, x_2, cdots, x_n)`, 就称它为 `n` 元齐次式. 齐次的 `n` 元多项式称为 `n` 元齐次多项式. 容易知道, 一个多项式是齐次的当且仅当它的各项次数都相等, 如 `x^3 - 2x^2 y` 就是一个齐次多项式.

    若一个 `n` 元代数式 `f(x_1, x_2, cdots, x_n)` 满足:
  1. 交换其中任意两个字母 `x_i`, `x_j` 后都保持不变, 即 `f(x_1, cdots, x_i, cdots, x_j, cdots, x_n)` `= f(x_1, cdots, x_j, cdots, x_i, cdots, x_n)`, 就称它为 `n` 元对称式.
  2. 交换其中任意两个字母 `x_i`, `x_j` 后恰好变为原来的 -1 倍, 即 `f(x_1, cdots, x_i, cdots, x_j, cdots, x_n)` `= -f(x_1, cdots, x_j, cdots, x_i, cdots, x_n)`, 就称它为 `n` 元交代式.
  3. 将字母 `x_1, x_2, cdots, x_(n-1), x_n` 分别换成 `x_2, x_3, cdots, x_n, x_1` 后保持不变, 即 `f(x_1, x_2, cdots, x_(n-1), x_n)` `= f(x_2, x_3, cdots, x_n, x_1)`, 就称它为 `n` 元轮换式. 显然对称式必为轮换式.
    4. 对称的 (交代的, 轮换的) `n` 元多项式分别称为 `n` 元 对称多项式 (symmetric polynomial) (交代多项式, 轮换多项式).
  1. 对称式的例子: `(x+y)/(x y)`, `x+y`, `x y`, `x^2 + y^2 + z^2`, `x y+y z+z x`.
  2. 交代式的例子: `(x-y)/(x+y)`, `x-y`, `(x-y)(y-z)(z-x) = |1, 1, 1; x, y, z; x^2, y^2, z^2|`.
  3. 轮换式的例子: `x^2 y + y^2 z + z^2 x`.

初等对称多项式

初等对称多项式 (基本对称多项式, elementary symmetric polynomial) 关于 `n` 个变元 `x_1, cdots, x_n` 的初等对称多项式定义为 `sigma_i(x_1, cdots, x_n) = sum_(C sube N, |C| = i) prod_(j in C) x_j`, `quad i = 0, 1, cdots, n`. 其中 `N = {1, 2, cdots, n}`. 上式也可以写成 `sigma_0 = 1`, `quad sigma_1 = sum_i x_i`, `quad sigma_2 = sum_(i lt j) x_i x_j`, `quad sigma_3 = sum_(i lt j lt k) x_i x_j x_k`, `quad cdots`, `quad sigma_n = x_1 x_2 cdots x_n`. 初等对称多项式是每个变元最高次数为 1 的齐次对称多项式, 其中 `sigma_i` 的次数为 `i`, 它等于 `x_1` 到 `x_n` 中任取 `i` 个变量相乘的所有情况之和.

Vieta 定理 `n` 次多项式 `f(x) = sum_(i=0)^n a_i x^i` 的全部 `n` 个根记为 `x_i`, `i = 1, 2, cdots, n`. 我们有根与系数的关系: `sigma_i(x_1, cdots, x_n) = (-1)^i a_(n-i)/a_n`, `quad i = 0, 1, cdots, n`.

初等对称多项式的生成函数 观察下式: `(1+x_1)(1+x_2) cdots (1+x_n)` `= 1 + sigma_1 + sigma_2 + cdots + sigma_n`. 如果将每个 `x_i` 都乘以 `t`, 就得到 `prod_(i=1)^n (1 + x_i t)` `= sum_(i=0)^n sigma_i t^i`, 这是一个多项式, `i` 次项系数恰为 `sigma_i`, 因此它是生成函数.

对称多项式基本定理 任一 `n` 元对称多项式 `f(x_1, x_2, cdots, x_n)` 可以唯一表示为初等对称多项式 `sigma_i^((n)) := sigma_i(x_1, x_2, cdots, x_n)`, `i = 1, 2, cdots, n` 的多项式.

首先注意, 令 `x_n = 0`, 就能将任一 `n` 元对称多项式降为 `n-1` 元对称多项式. 特别在 `sigma_i^((n))` 中令 `x_n = 0`, 就得到 `sigma_i^((n-1))`: `sigma_i(x_1, cdots, x_(n-1), 0) = sigma_i(x_1, cdots, x_(n-1))`. 对 `n` 进行归纳证明. `n = 1` 时显然成立. 设 `n gt 1`, 且结论对 `n-1` 成立. 由归纳假设, `f|_(x_n=0) := f(x_1, cdots, x_(n-1), 0)` 是 `n-1` 元对称多项式, 它能表示为 `f|_(x_n=0)` `= p(sigma_1^((n-1)), cdots, sigma_(n-1)^((n-1)))`, 其中 `p` 是一个多项式. 令 `g(x_1, cdots, x_n)` `= p(sigma_1^((n)), cdots, sigma_(n-1)^((n)))`, 则 `{:g|_(x_n=0) = {:f|_(x_n=0)`. 令 `h = f - g`, 有 `h|_(x_n=0) = 0`, 这说明 `x_n | h`. 由对称性, `sigma_n^((n)) = x_1 x_2 cdots x_n | h`. 如果 `h` 的次数不小于 `n`, 就令 `f_1 = h//sigma_n`, 代替原来的 `f` 进行操作, 直到得到的 `h` 次数小于 `n`. 这时由 `sigma_n^((n)) | h` 知 `h -= 0`. 零多项式当然是初等对称多项式的多项式, 证毕.

    `n` 元对称多项式的标准化 [来自 bilibili@凡人忆拾]
  1. 记号 设 `n` 元 `m` 次对称多项式的变元为 `x_1, cdots, x_n`. 用记号 `[k_s, cdots, k_1, k_0]` 表示一个对称求和, 其中有 `k_0` 个变元为 `0` 次, `k_1` 个变元为 `1` 次, `cdots`, `k_s` 个变元为 `s` 次, 满足 `k_0 + k_1 + cdots + k_s = n`,
    `0 * k_0 + 1 * k_1 + cdots + s * k_s = m`.     比如 `[1, 1, 0, 2] = sum_"sym" x_1^3 x_2^2 x_3^0 x_4^0`, 其中 3 次和 2 次的变元各有一个, 0 次的变元有两个.
    又比如, `n` 元初等对称多项式 `sigma_k = [k, n-k]`, 因为它的每一项都是 `k` 个变量的一次方的乘积.
  2. 乘法法则 我们的目标是降低 `f = [color(red)(k_s), cdots, k_0]` 中的最高次方 `k_s`, 为此, 将它与另一个多项式比较: `g = [color(red)(k_s + k_(s-1)), cdots, k_0]`. 考虑乘积 `sigma_k * g`, `k = k_s`. 一个对称多项式乘上 `sigma_k`, 效果是给它的 `k` 个变元 `x_(i_1), cdots x_(i_k)` 升阶. 其中 `i_1, cdots, i_k` 取遍 `1` 到 `n` 的所有组合. 假如我们只给 `g` 的 `k` 个最高次变元升阶, 得到的就是多项式 `f`, 因此 `f` 是 `sigma_k * g` 的结果的一部分: `sigma_k * g = f + cdots`. 一般地, 假如我们给 `g` 的任意 `k` 个变元升阶, 得到多项式 `h = [a_s, cdots, a_0]`, 其中 `a_s le k`, 等号成立当且仅当 `h = f`. 则 `h` 在 `sigma_k * g` 中的系数等于 `(a_s;b_s)cdots(a_0;b_0)`. 其中 `(a_i; b_i)` 表示在 `h` 的 `a_i` 个次数为 `i` 的变元中, 有 `b_i` 个是升阶得到的, 其余的次数原本就等于 `i`, 保持不变. 总之 `sigma_k * g = sum (a_s;b_s) cdots (a_0;b_0) [a_s, cdots, a_0]`. 上式对 `g` 的一切可能升阶方案求和.

化简 4 元对称式 `-[1, 1, 0, 2] - 2[1, 3, 0] + [2, 1, 1]`.

应用乘法法则:
`[1, 1, 0, 2]` `= sigma_1[2, 0, 2] - (color(red)2;0)(color(red)1;1)(color(red)1;0)[2, 1, 1]` `= sigma_1[2, 0, 2] - [2, 1, 1]`,
`[2, 1, 1] = sigma_2[3, 1] - (color(red)1;1;)(color(red)3;1)(color(red)0;0)[1, 3, 0]` `= sigma_2 sigma_3 - 3[1, 3, 0]`,
`[2, 0, 2]` `= sigma_2[2, 2] - (color(red)1;1)(color(red)2;1)(color(red)1;0)[1, 2, 1] - (color(red)4;2)(color(red)0;0)[4,0]` `= sigma_2^2 - 2[1, 2, 1] - 6 sigma_4`,
`[1, 3, 0] = sigma_1[4, 0] = sigma_1 sigma_4`,
`[1, 2, 1] = sigma_1[3, 1] - (color(red)4;1)(color(red)0;0)[4, 0] = sigma_1 sigma_3 - 4 sigma_4`,
将上面材料代入化简得 `-[1, 1, 0, 2] - 2[1, 3, 0] + [2, 1, 1]` `= 2σ_1^2 σ_3 - σ_1 σ_2^2 - 10 σ_1 σ_4 + 2 σ_2 σ_3`.

注: 下面程序的结果需要做一些多项式运算将它化简.

Newton-Girard 公式

Newton-Girard 公式 设 `S_i` 是 `n` 元 `i` 次对称多项式: `S_i = sum_(j=1)^n x_j^i`, `quad i = 0, 1, 2, cdots`. `sigma_i` 是 `n` 元 `i` 次初等对称多项式, 则 `S_i = { sum_(j=1)^n (-1)^(j-1) sigma_j S_(i-j), if i ge n; sum_(j=1)^(i-1) (-1)^(j-1) sigma_j S_(i-j) + (-1)^(i-1) sigma_i * i, if i lt n; :}` 需要注意, 一般来说 `i lt n` 时 `S_0` 被认为是未定义的, 因此最后一项被单独提出.

    利用 `sigma_0 = 1`, 我们只需证明公式的等价形式: `{ sum_(j=0)^n (-1)^j sigma_j S_(i-j) = 0, if i ge n; sum_(j=0)^(i-1) (-1)^j sigma_j S_(i-j) + (-1)^i sigma_i * i = 0, if i lt n; :}`
  1. `i ge n` 时, 设多项式 `f(x) = sum_(j=0)^n a_(n-j) x^(n-j)` 的 `n` 个根恰为 `x_1, cdots, x_n`, 且 `a_n = 1`. 于是 `sum_(j=0)^n a_(n-j) S_(i-j)` `= sum_(j=0)^n a_(n-j) sum_(k=1)^n x_k^(i-j)` `= sum_(k=1)^n x_k^(i-n) f(x_k) = 0`. 由 Vieta 定理, `a_(n-j) = (-1)^j sigma_j a_n`, 代入上式得 `sum_(j=0)^n (-1)^j sigma_j S_(i-j) = 0`.
  2. 现在设 `i lt n`. 对 `k = n-i gt 0` 作归纳, 设结论对任意 `k' lt k` 已经成立. 用 `f_(n,i)(x_1, x_2, cdots, x_n)` 表示 Newton-Girard 公式 (等价形式) 的左边, 因为 `sigma_j(x_1, cdots, x_(n-1), 0) = sigma_j(x_1, cdots, x_(n-1))`,
    `S_j(x_1, cdots, x_(n-1), 0) = S_j(x_1, cdots, x_(n-1))`.     有 `f_(n,i)(x_1, cdots, x_(n-1), 0)` `= f_(n-1,i)(x_1, cdots, x_(n-1))`. 由归纳假设, 上式右边等于零, 这说明 `x_n | f_(n,i)`. 由 `f_(n,i)` 的对称性, `sigma_n = x_1 x_2 cdots x_n | f_(n,i)`. 注意到 `f_(n,i)` 的次数不超过 `i`, 且 `i lt n`, 我们得到 `f_(n,i) = 0`. 证毕.

当变元数 `n = 3` 时, Newton-Girard 公式写为 `{ S_1 = sigma_1; S_2 = sigma_1 S_1 - 2 sigma_2; S_3 = sigma_1 S_2 - sigma_2 S_1 + 3 sigma_3; :}`

当变元数 `n = 3` 时, `a = b = c` 当且仅当 `S_2 = sigma_2`, 即 `a^2+b^2+c^2 = a b+b c+c a`. 这是因为配方得: `a^2+b^2+c^2-(a b+b c+c a)` `= (a-b)^2/2 + (b-c)^2/2 + (c-a)^2/2`.

设 `f(x) = (x-1)(x-2)(x-3)` `= x^3 - 6x^2 + 11x - 6`. 分别求 `sigma_i` 和 `S_i`, `i in {1, 2, 3, -1, -2, -3}`.

多项式的三个根记为 `a, b, c`, 于是 `a+b+c = sigma_1 = 6`,
`ab+bc+ca = sigma_2 = 11`,
`abc = sigma_3 = 6`,
`1/a+1/b+1/c = sigma_(-1) = sigma_2//sigma_3 = 11/6`,
`1/(ab) + 1/(bc) + 1/(ca) = sigma_(-2) = sigma_1//sigma_3 = 1`,
`1/(abc) = sigma_(-3) = 1//sigma_3 = 1/6`. 用 Newton-Girard 公式计算: `a+b+c = S_1 = sigma_1 = 6`,
`a^2+b^2+c^2 = S_2 = sigma_1 S_1 - 2 sigma_2 = 14`,
`a^3+b^3+c^3 = S_3 = sigma_1 S_2 - sigma_2 S_1 + 3 sigma_3 = 36`,
`1/a+1/b+1/c = S_(-1) = sigma_(-1) = 11/6`,
`1/a^2+1/b^2+1/c^2 = S_(-2) = sigma_(-1) S_(-1) - 2 sigma_(-2) = 49/36`,
`1/a^3+1/b^3+1/c^3 = S_(-3) = sigma_(-1) S_(-2) - sigma_(-2) S_(-1) + 3 sigma_(-3) = 251/216`.

`(a x_1+b)(a x_2+b) = a^2 sigma_2 + a b sigma_1 + b^2`,
`(a x_1+b)(a x_2+b)(a x_3+b) = a^3 sigma_3 + a^2 b sigma_2 + a b^2 sigma_1 + b^3`.

[题源 学而思] 解方程组 `{ x - y + z - w = 2; x^2 - y^2 + z^2 - w^2 = 6; x^3 - y^3 + z^3 - w^3 = 20; x^4 - y^4 + z^4 - w^4 = 66; :}`

注意到方程组的对称性, 故使用对称多项式进行换元: 令 `m = x + z`, `quad n = x z`,
`u = y + w`, `quad v = y w`, 于是 `m^2 = x^2 + z^2 + 2n`,
`m^3 = x^3 + z^3 + 3m n`,
`m^4 = x^4 + z^4 + 4m^2 n - 2n^2`. 关于 `u^2, u^3, u^4` 也有类似的公式; 代入原方程组得到 `{ m = u + 2, (1); m^2 - 2n = u^2 - 2v + 6, (2); m^3 - 3m n = u^3 - 3u v + 20, (3); m^4 - 4m^2 n + 2n^2 = u^4 - 4u^2 v + 2v^2 + 66, (4); :}` 将 (1) 代入 (2) 得 `n = 2u + v - 1`. `quad (5)` 将 (1) (5) 代入 (3) 得 `u = 2(v+1)`. `quad (6)` 再联系 (5), `n = 5v + 3`. `quad (7)` 将 (1) (6) (7) 代入 (4) 得 `v = 0`, `u = 2`, `n = 3`, `m = 4`. 最终得 `{x, z} = {1, 3}`, `{y, w} = {0, 2}`.

  1. 设 `n` 为整数, 记 `x_n = t^n+t^-n`, 显然 `x_n = x_(-n)`, 即 `x` 关于 `n` 是偶函数. 又容易验证 `x_m x_n = x_(m+n) + x_(m-n)`, 特别取 `m = 1`, `n = n-1` 有 `x_n = x_1 x_(n-1) - x_(n-2)`. 从而任意 `x_n` 都是 `x_1` 的多项式, 记 `x_1 = x`, 这一系列多项式定义为 `x_n = { 2, if n = 0; x, if n = 1; x x_(n-1) - x_(n-2), if n ge 2; :}`
  2. 记 `y_n = t^n-t^-n`, 则 `y` 关于 `n` 是奇函数. 又 `x_m y_n = y_(m+n) - y_(m-n)`, 取 `m=1`, `n = n-1` 有 `y_n = x_1 y_(n-1) - y_(n-2)`. 则 `w_n := y_n//y_1` 是 `x := x_1` 的多项式. 可以定义 `w_n = { 0, if n = 0; 1, if n = 1; x w_(n-1) - w_(n-2), if n ge 2; :}`
    3. 两种多项式的迭代步骤相同, 而初值不同.
`n` `x_n` `w_n`
`0` `2` `0`
`1` `x` `1`
`2` `x^2-2` `x`
`3` `x^3-3x` `x^2-1`
`4` `x^4-4x^2+2` `x^3-2x`
`5` `x^5-5x^3+5x` `x^4-3x^2+1`

高次方程

Lagrange 预解式

[来自 Hilbert@知乎]

预解式 设 `f(x_1, cdots, x_n)` 是一个 `n` 元多项式, `sigma, tau in S_n` 是 `1` 到 `n` 的排列. 如果 `f(x_(sigma(1)), cdots, x_(sigma(n))) = f(x_(tau(1)), cdots, x_(tau(n)))`, 则称 `sigma` 与 `tau` 是等价的, 显见 `S_n` 商掉这个等价关系后为一群 `G := { f_1, cdots, f_m }`. 当 `f` 为对称多项式时, `m = 1`; `f` 为交代式时, `m = 2`.
构造一个关于 `y` 的一元多项式 `g(y) = prod_(i=1)^m (y - f_i)`. 由韦达定理知道, `g(y)` 的系数是 `f_i` 的初等对称多项式, 从而是 `x_1, cdots, x_n` 的对称多项式.
现在设 `x_1, cdots, x_n` 是 `n` 次方程的 `n` 个根, 则 `f(x_1, cdots, x_n)` 称为原方程的一个预解式, `g(y) = 0` 称为原方程的一个预解方程.

Lagrange 预解式 设 `zeta` 是 `n` 次本原单位根, 则下面的 `n` 个多项式称为 Lagrange 预解式: `L_i(x_1, cdots, x_n)` `:= sum_(j=0)^(n-1) zeta^(i j) x_(j+1)`, `quad i = 0, cdots, n-1`. 假如知道 `L_0, cdots, L_(n-1)` 的值, 通过解线性方程组就可以得到 `x_1, cdots, x_n` 的值: `x_(j+1) = 1/n sum_(i=1)^(n-1) zeta^(-i j) L_i` `quad j = 0, cdots, n-1`.

验证矩阵互逆: `sum_(k=0)^(n-1) zeta^(i k) zeta^(-k j)` `= sum_(k=0)^(n-1) zeta^(k (i-j))` `= {n, if i = j; (zeta^(n(i-j)) - 1)//(zeta^(i-j) - 1) = 0, otherwise :}`

Lagrange 预解式的主要应用是推导二到四次方程的求根公式; 因其计算过程繁琐, 可以参见本节开头的链接, 这里从略.

五次及以上一般方程无根式解的证明思路

根式可解

设 `a^n in bbb F`, 即 `a` 是 `bbb F` 中某个元素的 `n` 次方根. 把 `a` 加到 `bbb F` 中生成的域 `bbb F(a)` 称为 `bbb F` 的一个单根式扩域. 若存在单根式扩张的链条 `bbb F sube bbb F_1 sube bbb F_2 sube cdots sube bbb K`, 则 `bbb K` 称为 `bbb F` 的一个根式扩域.

设 `f` 是 `bbb F` 上的 `n` 次多项式, 且在 `bbb F` 的扩域 `bbb K` 上能被完全因式分解: `f(x) = a(x-k_1)cdots(x-k_n)`, `quad k_1, cdots, k_n in bbb K`, 满足上式的最小域 `bbb K` 称为 `bbb F` 的分裂域.

于是, `f in bbb F[x]` 根式可解定义为: `f` 的分裂域 `bbb K` 是 `bbb F` 的一个根式扩域. 换言之, 存在 `bbb F` 的一个根式扩域包含 `f` 的所有根.

可解群与 Galois 群

一个群是 `G` 可解的, 是指存在正规子群的链条 `{e} normal H_1 normal H_2 normal cdots normal G`, 且相邻两个群之商 `H_(i+1) // H_i` 都是 Abel 群.

设 `bbb K` 是 `bbb F` 的扩域, 则 `bbb K` 上全体保持 `bbb F` 中元素不变的自同构组成一个群, 称为 `bbb K` 在 `bbb F` 上的 Galois 群 `Gal(bbb K, bbb F)`.

为理解 Galois 群, 任取 `f in bbb F[x]`, `k in bbb K` 和 `varphi in Gal(bbb K, bbb F)`, 由于 `varphi` 保持 `bbb F` 中元素不变, 所以它保持 `f` 的系数不变, `varphi(f(k)) = f(varphi(k))`. 特别取 `k = x_i` (`x_i` 是 `f` 的根) 时, 有 `f(varphi(x_i)) = varphi(f(x_i)) = 0`. 这推出 `varphi(x_i)` 亦是 `f` 的根. 因此 Galois 群实际就是对 `f` 的根的置换, 是 `S_n` 的一个子群.

Galois 定理 `f in bbb F[x]` 根式可解当且仅当其分裂域 `bbb K` 在 `bbb F` 上的 Galois 群可解.

由于一般的五次多项式的 Galois 群不可解, 故一般五次方程无根式解.

下面的定理给出根式可解的一个必要条件:

Kronecker 定理 [来自 知乎@IURT] 设奇素数次不可约多项式 `f in QQ[x]` 根式可解, 则要么它仅有一个实根, 要么所有根都是实根.

  1. 由于 `f` 根式可解, 存在域链 `QQ sube bbb F_1 cdots sube bbb F_n`, 使得 `bbb F_n` 包含 `f` 的所有根. 其中每个扩张 `bbb F_i // bbb F_(i-1)` 都是单根式扩张, 不妨设它们都是添加素数次方根得到的扩张, 即 `bbb F_i = bbb F_(i-1)(alpha_i)`, `alpha_i` 是 `f_i(x) = x^(p_i) - c_i in bbb F_(i-1)` 的一个根.
  2. 接下来对域链提出一些要求. 首先, 由“仍不可约引理”, `f` 在添加 `p` 次单位根的域 `E_(-1) = QQ(zeta_p)` 上仍不可约, `p` 是 `f` 的次数.
    其次, 为了保证 `bbb F_i // bbb F_(i-1)` 是正规扩张, 即 `bbb F_i` 包含 `f_i` 的所有根, 我们事先把所有 `p_i` 次单位根添加进来, 记 `E_0 = E_(-1)(zeta_(p_1), cdots, zeta_(p_n))` 接下来, 对 `i ge 1`, 记 `E_i = E_(i-1)(alpha_i, bar alpha_i)`. 得到新的域链 `E_(-1) sube E_0 sube E_1 sube cdots sube E_n`. 显然 `E_n supe bbb F_n`, 所以它包含 `f` 的所有根. 必定在某一步扩张中, `f` 由不可约变为可约: 设它在 `E_(i-1)` 不可约, `E_i` 可约.
  3. 分两种情况: (1) 若 `f` 在 `E_(i-1)(alpha_i)` 可约, 则记 `K = E_(i-1)`, `L = E_(i-1)(alpha_i)`. (2) 否则, 考虑中间域 `M = E_(i-1)(alpha_i bar alpha_i)`, 若 `f` 在 `M` 上可约, 则记 `K = E_(i-1)`, `L = M`; 否则 `K = M`, `L = E_i`. 总之在任何一种情况, 都有: `f` 在 `K` 上不可约, 在扩域 `L = K(lambda_1)` 上可约, 这里 `lambda_1` 是 `g(x) = x^q - c in K[x]` 的一个根, `q` 为素数. (我们把形如 `x^n = a` 的方程称为纯方程, 相应的多项式称为纯方程多项式).
  4. 下证 `g` 在 `K` 上不可约, 这是因为它有一个根 `lambda_1 !in K`, 而 `q` 次单位根 `zeta_q in E_0 sube K`, 所以 `g` 的所有根都不属于 `K`. 我们知道, 纯方程多项式可约则必有根, 现在 `g` 在 `K` 上没有根, 于是它在 `K` 上不可约.
  5. 注意 `f`, `g` 在 `K` 上不可约, 但 `f` 在添加一个 `g` 的根的扩域 `L = K(lambda_1)` 上可约, 由“仍不可约引理”, 我们得到两个结论: (1) `p` 整除 `g` 的次数 `q`. 但它们均为素数, 所以 `p = q`. (2) `f` 在每个扩域 `K(lambda_i)` 上都可约, `lambda_i` 是 `g` 的 `p` 个不同的根. 由于 `p` 次单位根 `zeta_p in E_(-1) sube K`, 所以这些 `K(lambda_i)` 都等于 `L`.
  6. 下证 `L` 含有 `f` 的全部 `p` 个根. 设 `varphi(x, lambda_1)` 是 `f` 在 `L` 上的一个不可约因式, `varphi in K[x, y]`. 用“仍不可约引理”的同样思路, 可以证明: `varphi(x, lambda_i)` 都在 `L` 上不可约, 且两两不等. 于是 `prod_(i=1)^p varphi(x, lambda_i)` 整除 `f`. 但 `f` 的次数是 `p`, 因此 `varphi(x, lambda_i)` 就是 `f` 的全部一次因式.
  7. 需要指出, 数域 `K` 是复共轭封闭的, 即对任意 `k in K` 有 `bar k in K`. 事实上, `E_(-1) = QQ(zeta_p)` 是复共轭封闭的, 因为 `bar zeta_p = zeta_p^(p-1) in E_(-1)`. 同理 `E_0 = E_(-1)(zeta_(p_1), cdots, zeta_(p_n))` 也是复共轭封闭的. 一般地, 若域 `bbb F` 复共轭封闭, 而 `lambda !in bbb F` 是纯方程 `x^n = c` 的根, `c in bbb F`, 则扩域 `bbb F(lambda, bar lambda)` 也复共轭封闭. 从而由 `K` 的构造过程知道它是复共轭封闭的.
  8. 由于 `f` 是奇数次实系数多项式, 必有一实根, 记为 `omega`. 下面对 `g(x) = x^p - c` 的常数项 `c` 分类讨论: 当 `c in RR` 时, `g` 也是奇数次实系数多项式, 取 `g` 的一个实根 `lambda`, 于是 `L = K(lambda)`. 由于 `omega in L`, 有 `omega = sum_(i=0)^(p-1) k_i lambda^i`, `quad k_i in K`. 于是 `0 = omega - bar omega = sum_(i=0)^(p-1) (k_i - bar k_i) lambda^i`. 根据 `K` 的共轭封闭性, 系数 `k_i - bar k_i in K`. 这说明 `lambda` 是 `K` 上一个次数小于 `p` 的多项式的根. 但 `g` 是不可约多项式, 是 `lambda` 在 `K` 上的最小多项式. 这说明上式右端是零多项式, `k_i = bar k_i`, 即所有 `k_i` 都是实数. 现在考察 `f` 的其它根. 由于 `x - omega` 是 `f` 的一次因式, 且 `varphi(x, lambda)` `= x - omega` `= x - sum_(i=0)^(p-1) k_i lambda^i`. 所以 `f` 的其它一次因式为 `varphi(x, lambda_j)` `= x - omega_j` `= x - sum_(i=0)^(p-1) k_i lambda_j^i`. 因此 `omega_j = sum k_i lambda_j^i` `= sum k_i lambda^i zeta_p^(j i)`,
    `bar omega_j = sum k_i lambda^i zeta_p^(-j i)` `= omega_(p-j)`.     这就是说 `omega_j` 与 `omega_(p-j)` 互为共轭复数. 因为它们不相等, 所以它们不是实数. 综上在 `c in RR` 的情况下, `f` 有一个实根, `(p-1)//2` 对共轭复根.
  9. 最后, 设 `c !in RR`. 我们转而考虑多项式 `g_1(x) = x^p - c bar c in K[x]` 和扩域 `K sube M_1 sube L_1`, 其中 `M_1 = K(lambda bar lambda)`,
    `L_1 = M_1(lambda) = K(lambda bar lambda, lambda)`,
    `lambda` 是 `g(x) = x^p - c` 的任一根.     显然 `L_1 supe L = K(lambda)`, 所以 `f` 在 `L_1` 上可约. 如果 `f` 在 `M_1` 上可约, 那么 `K` 与 `M_1` 之间只相差 `g_1` 的一个实根 `lambda bar lambda`, 化为讨论过的情况 `c in RR`.
    现在设 `f` 在 `M_1` 上不可约. 好消息是, `g` 也在 `M_1` 上不可约. 和前面一样, 只需验证它的根 `lambda !in M_1`: 假如 `lambda in M_1`, 则 `L_1 = M_1`, 但 `f` 在 `M_1` 上不可约, 在 `L_1` 上可约, 推出矛盾.
  10. 回到 `f` 的根的表达式 `omega = sum k_i lambda^i`,
    `omega_j = sum k_i lambda_j^i`,
    `bar omega_j = sum bar k_i bar lambda_j^i`, `quad k_i in M_1`;     我们要证明 `bar omega_j = omega_j`. 利用 `omega` 是实根, `bar omega = omega`, 于是 `sum (k_i lambda^i - bar k_i bar lambda^i) = 0`. 记 `Lambda = lambda bar lambda`, 上式两边同乘 `lambda^(p-1)` 得到 `sum (k_i lambda^(i+p-1) - bar k_i Lambda^i lambda^(p-1-i)) = 0`. 考查上式系数, 由于 `M_1` 复共轭封闭, `k_i, bar k_i in M_1`, 又 `Lambda in M_1`, 从而上式表明, `lambda` 是 `M_1` 上某个 `2(p-1)` 次多项式 `h` 的根. 由于 `lambda` 也是 `M_1` 上不可约多项式 `g` 的根, 所以 `g | h`, 从而 `g` 的所有根 `lambda_j = lambda zeta_p^j` 都是 `h` 的根, 得到 `sum (k_i lambda_j^(i+p-1) - bar k_i Lambda^i lambda_j^(p-1-i)) = 0`. 注意 `lambda_j bar lambda_j = Lambda`, 上式两边同除以 `lambda_j^(p-1)` 得到 `sum (k_i lambda_j^i - bar k_i bar lambda_j^i) = 0`. 于是 `omega_j = bar omega_j`. 这意味 `c !in RR` 时, `f` 的所有根都是实数, 从而我们证明了 Kronecker 定理.

五次方程的级数解

五次方程的 Bring-Jerrard 标准形 `x^5 +- x + k = 0`. 一般地, `n` 次方程可以化简消去 `n-1`, `n-2`, `n-3` 次项. [来自 stackexchange]

  1. 对方程的根作 Tschirnhaus (契尔恩豪森) 变换, 消去 4 次和 3 次项. 设 `x_i`, `i = 1, cdots, 5` 是原方程的根, 令 `y_i = x_i^2 + m x_i + n`, 只需将原方程与 `y = x^2 + m x + n` 联立, 求解结式 (resultant), 比如使用 wolfram 语言: 
    Collect[Resultant[x^5+ax^4+bx^3+cx^2+dx+e, y-(x^2+mx+n), x],y]
    就得到 `y^5 + c_1 y^4 + c_2 y^3 + c_3 y^2 + c_4 y + c_5 = 0`. 其中 `c_1 = -a^2 + 2 b + a m - 5 n`,
    `c_2 = b^2 - 2 a c + 2 d + (3c - a b)m + (4a-8b)n + b m^2 - 4 a m n + 10 n^2`.     通过求解二次方程组, 选择适当的 `m, n`, 就能使 `c_1 = c_2 = 0`, 得到 `y^5 + u y^2 + v y + w = 0`.
  2. 要继续消去方程的 2 次项, 一个简单的想法是使用 3 次 Tschirnhaus 变换, 但这会引出 1 次, 2 次和 3 次方程的方程组, 最终需要求解一个 6 次方程. Bring 与 Jerrard 另辟蹊径, 使用 4 次 Tschirnhaus 变换, 利用额外多出的一个参数来避免高次方程: `z = y^4 + p y^3 + q y^2 + r y + s`, 与 联立有 `z^5 + d_1 z^4 + d_2 z^3 + d_3 z^2 + d_4 z + d_5 = 0`, 其中 `d_1 = -5s + 3p u + 4v`,
    `d_2 = 10s^2 - 12p s u + 3p^2 u^2 - 3q u^2 + 2q^2 v - 16 s v` `+ 5 p u v + 6 v^2 + 5p q w - 4u w + r(color(#823)(3q u + 4p v + 5 w))`,
    `d_3 = ** r^3 + ** r^2 + ** r + **`.     令 `d_1 = d_2 = 0` 以及 `color(#823)(3q u + 4p v + 5 w) = 0`, 只需求解二次方程组即可得到 `p, q, s` 的值. 注意我们的条件使得前两个方程与变量 `r` 无关, 因此可以独立地使用 `d_3 = 0` 的任一解作为 `r` 的值. 总之我们有 `z^5 + d_4 z + d_5 = 0`.
  3. 最后, 应用伸缩变换 `z = t // f`, `t^5 + d_4 f^4 t + d_5 f^5 = 0`, 再令 `d_4 f^4 = +-1` 解出 `f` 的值即可.
  4. 注: 如果你想手动得到 1. 中的结式, 可以展开 `prod (y - x_i^2 - m x_i - n) = 0`, 利用 Vieta 定理和 Newton 多项式消去展式中的 `x_i`, 便得到 `y` 的五次方程.

[来自 Frits Beukers《Hypergeometric Functions, How Special Are They?》] 利用 Lagrange 反演获得五次方程 `z x^5 = x - 1` 的一个解.

令 `x = y+1`, 于是 `z = y/(y+1)^5 := f(y)`. 它的反演是 `y = f^-1(z)`
`= sum_(n ge 1) z^n/n [z^(n-1)] (z/(f(z)))^n`
`= sum_(n ge 1) z^n/n [z^(n-1)] (z+1)^(5n)`
`= sum_(n ge 1) z^n/n (5n; n-1)`
`= sum_(n ge 1) (5n;n) z^n/(4n+1)`. 于是 `x = y+1 = sum_(n ge 0) (5n;n) z^n/(4n+1)`. 遗憾的是, 上式的收敛半径不算很大: `lim_(n to oo) ((5n;n)//(4n+1))/((5n+5;n+1)//(4n+5))` `= lim_(n to oo) ((4n+4)...(4n+1)(n+1))/((5n+5)...(5n+1))` `= (4/5)^4 * 1/5` `= 0.08192`. 例如取 `z = 0.01` 时, 上式算出五次方程 `0.01 x^5 = x-1` 的一个解 `x ~~ 1.0105`. 一般情况, 将五次方程化为 Bring-Jerrard 标准形 `x^5 = a x + b`, 同样可以用 Lagrange 反演获得一个解.

代数学基本定理

设 `f` 是复数域上的多项式 `f(z) = sum_(k=0)^n a_k z^k`, `quad a_n != 0`. 令 `A = max_(0 le k lt n) |a_k|`, `r = A/|a_n| + 1`, 则 `|z| gt r` 时, 首项的模大于其余各项的模之和: `|a_n z^n| gt sum_(k=0)^(n-1) |a_k z^k|`. 这一结论可以类比于盖尔圆盘定理.

`sum_(0 le k lt n) |a_k z^k|` `le A sum_(0 le k lt n) |z|^k` `= A (|z|^n-1)/(|z|-1)` `lt A |z|^n/(r-1)` `= |a_n z^n|`.

设 `z^n + a_(n-1) z^(n-1) + cdots + a_1 z + a_0 = 0`, `A = max_(0 le k lt n) |a_k|`, 则 `|z| le max{1, n A}`.

不妨设 `|z| gt 1`, 下证 `|z| le n A`. 移项并取模 `|z|^n = |a_(n-1) z^(n-1) + cdots + a_1 z + a_0|` `le A |z^(n-1) + cdots + z + 1|` `le n A |z|^(n-1)`. 两边同除以 `|z|^(n-1)` 即得证.

代数学基本定理 `n` 次复系数多项式 (`n ge 1`) `f(z) = sum_(k=0)^n a_k z^k`, `quad a_n != 0` 在复数域内有零点.

    若 `f` 的常数项为零, 显然 `z = 0` 就是 `f` 的零点. 下设 `a_0 != 0`.
  1. 因为 `a_0 != 0`, 有 `lim_(z to oo) |f(z)| = oo` (将 `f` 的各项同除以首项可以证明. 这是因为 `z to oo` 时, `f` 的高次项是最主要的项). 因此存在 `R gt 0`, 使得 `|f|` 在闭圆盘 `D = bar(B(0, R))` 外大于 `1`. 换言之, `f` 的零点若是存在, 只可能出现在 `D` 中. 由于 `D` 是紧集, 可以取 `z_0 in D`. 使得 `|f(z_0)| = min_(z in D) |f(z)|`.
  2. 下证 `f(z_0) = 0`. 若不然, 设 `f(z_0) = a != 0`, 我们来证明存在 `z_1 in D`, 使得 `|f(z_1)| lt |f(z_0)|`, 从而与 `z_0` 是最小值点矛盾. 令 `Delta z = z - z_0`, 将 `f(z)` 在 `z_0` 处 Taylor 展开 (由于 `f` 是多项式函数, 只需将 `z = z_0 + Delta z` 代入 `f(z)` 的表达式即可): `f(z) = f(z_0 + Delta z) = f(z_0) + Delta z^m g(Delta z)`, 其中 `m ge 1`, `g` 是多项式. 由 `f` 的次数 `ge 1` 推出 `g` 不是零多项式, 因此可以设 `g(0) = b != 0`.
  3. 由多项式函数的连续性知, 存在 `delta gt 0`, 对任意 `|Delta z| lt delta` 有 `|g(Delta z) - b|` `= |g(Delta z) - g(0)| lt |b|//2`. 令 `0 lt t lt min{1, delta^m |b//a|}`, 又取 `Delta z in CC` 满足 `t = -Delta z^m b//a` (注意在复数域中总是可以开 `m` 次方), 则 `|Delta z^m b| = t |a| lt delta^m |b|` `rArr |Delta z| lt delta`,
    `a + Delta z^m b` `= (1 + Delta z^m b // a) a` `= (1-t) a`.     记 `z_1 = z_0 + Delta z`, 于是 `|f(z_1)|` `= |f(z_0) + Delta z^m g(Delta z)|`
    `= |a + Delta z^m b + Delta z^m g(Delta z) - Delta z^m b|`
    `le |a + Delta z^m b| + |Delta z|^m |g(Delta z) - b|`
    `lt (1-t) |a| + |Delta z|^m |b|//2`
    `= (1-t) |a| + t/2 |a|`
    `= (1-t/2) |a| lt |a| = |f(z_0)|`.     定理证毕.
    `QQ` 上因式分解的暴力算法 对于 `ZZ` 上的多项式 `f(x)`
  1. 若 `f` 有重因式, 则重因式是 `f` 和 `f'` 的最大公因式.
  2. 若 `f` 存在一次因式, 即 `f` 存在有理根. 则这个有理根的分母是 `f` 的最高次项系数的因子, 分子是 `f` 常数项的因子. 通过枚举因子可以得到这个一次因式. 下面设 `f` 的因式都是大于一次的, 且重数为 1.
  3. 由 Gauss 引理, 若 `f` 在 `QQ` 上可约, 则 `f` 在 `ZZ` 上也可约.
  4. 在复平面上可以找到一个圆盘, 包含 `f` 的所有根. 事实上 `|z| le max{1, n A}` 就是这样一个圆盘, 其中 `A` 是 `f` 各系数模的最大值.
  5. 利用韦达定理确定 `f` 的因式 `g` 的系数的界. 例如, 设 `g` 的次数为 `m`, 且它的所有根位于单位圆盘内, 则 `g` 的 `k` 次项系数的模有上界 `|c_k| le (m;k)`. 由于 `g` 的次数有限, 系数是整数且有上界, 可以对其系数进行枚举.

结式

[来自知乎@三维欧氏心]

判断两个多项式是否互素, 一种方法是用辗转相除法求出最大公因式, 再判断其是否为常数. 不过, 这种方法要求多项式至少是 Euclid Domain 上的, 方能进行辗转相除. 结式给出了判断多项式是否互素的另一种方法.

没有另行说明的情况下, 本节始终假定 `f, g in R[x]`, `deg f, deg g ge 1`, 且 `f(x) = sum_(k=0)^m a_k x^k`, `quad g(x) = sum_(k=0)^n b_k x^k`, `quad a_m, b_n != 0`.

`f, g` 不互素的充要条件是存在 `u, v in R[x]`, `deg u lt deg g`, `deg v lt degf`, 使得 `u(x) f(x) = v(x) g(x)`.

  1. `rArr`: 若 `f, g` 有非平凡的公因子 `d`, 设 `f = v d`, `g = u d`, 则 `deg u lt deg g = n`, `deg v lt deg f = m`, 且 `u f = u v d = v g`.
  2. `lArr`: 设 `d = gcd(f, v)`, `f = f_1 d`, `v = v_1 d`, 则由 `u f = v g` 得 `u f_1 d = v_1 d g`, 即 `u f_1 = v_1 g`. 但 `gcd(f_1, v_1) = 1` 所以 `f_1 | g`. 这说明 `f_1` 是 `f, g` 的公因子. 又 `deg d le deg v lt deg f`, 所以 `deg f_1 ge 1`.

`f, g` 的 Sylvester 行列式或结式 (Resultant) 定义为 `"Res"(f, g) = | a_m, a_(m-1), a_(m-2), cdots, a_0; , a_m, a_(m-1), cdots, a_1, a_0; , , ddots, ddots, , ddots, ddots; , , , a_m, a_(m-1), cdots, a_1, a_0; b_n, b_(n-1), b_(n-2), cdots, b_0; , b_n, b_(n-1), cdots, b_1, b_0; , , ddots, ddots, , ddots, ddots; , , , b_n, b_(n-1), cdots, b_1, b_0; | {: {:; ; ; ;} n 行; {:; ; ; ;} m 行 :}` 这个行列式的阶数为 `m+n`, 前 `n` 行由 `f` 的系数组成, 后 `m` 行由 `g` 的系数组成. 行列式的主对角线由 `n` 个 `a_m` 和 `m` 个 `b_0` 组成.

由 Sylvester 行列式立即得到, 对于非零常数 `a, b` 有 `"Res"(a f, b g) = a^n b^m "Res"(f, g)`.

`f, g` 不互素 `iff "Res"(f, g) = 0`.

由引理, `f, g` 不互素当且仅当存在系数不全为零的 `u(x) = sum_(k=0)^(n-1) u_k x^k` 和 `v(x) = - sum_(k=0)^(m-1) v_k x^k` 使得 `f(x) u(x) = g(x) v(x)`, 比较等号两边系数得到 `{ a_m u_(n-1) = - b_n v_(m-1); a_(m-1) u_(n-1) + a_m u_(n-2) = - b_(n-1) v_(m-1) - b_n v_(m-2); cdots; a_0 u_1 + a_1 u_0 = - b_0 v_1 - b_1 v_0; a_0 u_0 = - b_0 v_0; :}` 这个方程组含有 `m+n` 个变元 `u_0, cdots, u_(n-1), v_0, cdots, v_(m-1)` 和 `m+n` 个方程. 该方程组存在非零解, 因此系数行列式等于零.

设 `f(x) = 2x^3 - 3x^2 + lambda x + 3`, `g(x) = x^3 + lambda x + 1`, 若 `f, g` 不互素, 求 `lambda` 可能的值.

令 `"Res"(f, g) = | 2, -3, lambda, 3; , 2, -3, lambda, 3; , , 2, -3, lambda, 3; 1, 0, lambda, 1; , 1, 0, lambda, 1; , , 1, 0, lambda, 1; |` `= -(2+lambda)(2 lambda^2 + 14 lambda - 13)` `= 0`, 解得 `lambda = 2` 或 `lambda = -(7 +- 5 sqrt 3)/2`.

结式的等价定义 `"Res"(f, g) = a_m^n b_n^m prod_(i,j) (x_i - y_j)`, 其中 `x_i`, `y_j` 分别是 `f, g` 的根.

  1. 把 `"Res"(f, g)` 看成是 `x_i, y_j` 的 `m+n` 元多项式. 对任意 `i, j`, 若 `x_i = y_j`, 则 `f, g` 不互素, 由 知 `"Res"(f, g) = 0`. 因此 `(x_i - y_j)` 是 `"Res"(f, g)` 的一个因式.
  2. 另一方面, 由 Vieta 定理, 系数 `a_i, b_j` 分别可以写成根 `x_i, y_j` 的对称多项式, 比如 `a_(m-1) = sum x_i`, `a_0 = prod x_i` 等. 注意到 Sylvester 行列式展开的每一项 (视为 `x_i, y_j` 的多项式) 次数均为 `m n`, 所以 `"Res"(f, g)` 的次数是 `m n`, 其形如 `(x_i - y_j)` 的因式都是一次的. 即 `"Res"(f, g) = c prod_(i,j) (x_i - y_j)`, `quad c` 为待定系数.
  3. 最后来确定常数 `c`. 不妨设 `f, g` 首一, Sylvester 行列式展开中主对角线的那一项为 `a_m^n b_0^m = b_0^m = prod_j y_j^m`. 但 `c prod_(i,j) (x_i - y_j)` 的展开式中相应的一项为 `c prod_j y_j^m`, 由此得到 `c = 1`. 再利用 得到最终结论.

将 `f(y_j) = a_m prod_i (x_i - y_j)` 代入结式的乘积表达式中得到 `"Res"(f, g) = b_n^m prod_j f(y_j)` `= a_m^n prod_i g(x_i)`.

`"Res"(f - g h, g) = b_n^(delta - m) "Res"(f, g)`, 其中 `delta = deg(f - g h)`.

`"Res"(f - g h, g) = b_n^delta prod_j (f - g h)(y_j)` `= b_n^delta prod_j f(y_j)` `= b_n^(delta - m) "Res"(f, g)`.

判别式 多项式 `f(x)` 的判别式定义为 `Delta(f) := (-1)^s/a_m "Res"(f, f')` `= a_m^(2m-2) prod_(i lt j) (x_i - x_j)^2`. 其中 `s = m(m-1)//2`, 最高次项系数 `a_m != 0`, `f'` 是 `f` 的求导, `x_i` 是 `f(x)` 的根. 因此 `f` 有重根 `iff f` 与 `f'` 不互素 `iff Delta(f) = 0`. 特别地, `Delta(a x^2 + b x + c) = b^2 - 4 a c`,
`Delta(a x^3 + b x^2 + c x + d)` `= -27 a^2 d^2 + 18 a b c d - 4 a c^3 - 4 b^3 d + b^2 c^2`.

  1. 判别式的乘积公式. 设 `f(x) = a_m prod_i (x-x_i)` 则 `f'(x) = a_m sum_i prod_(j != i) (x - x_j)`,
    `f'(x_i) = a_m prod_(j != i) (x_i - x_j)`.     于是 `"Res"(f, f')` `= a_m^(m-1) prod_i f'(x_i)` `= a_m^(m-1) a_m^m prod_(i != j) (x_i - x_j)` `= (-1)^s a_m^(2m-1) prod_(i lt j) (x_i - x_j)^2`.
  2. 二次多项式的判别式 `Delta(a x^2 + b x + c)` `= -1/a "Res"(a x^2 + b x + c, 2a x + b)` `= -1/a| a, b, c; 2a, b; , 2a, b; |` `= -1/a(a b^2 - 2a b^2 + 4a^2 c)` `= b^2 - 4 a c`.
  3. 三次多项式的判别式 
    from sympy import *
from sympy.abc import a, b, c, x
expand(resultant(a*x**3 + b*x**2 + c*x + d, 3*a*x**2 + 2*b*x + c, x)/(-a))

二元高次方程组 考虑 `{F(x, y) = 0; G(x, y) = 0:}`, 先把 `y` 看作常数, 从而得到一元多项式 `f(x) := F(x, y)` 和 `g(x) := G(x, y)`. 方程组有解时, `f, g` 不互素, 即 `"Res"(f, g) = 0`, 问题化为 `y` 的一元高次方程. 解出 `y` 后代入原方程组求解 `x`.

解方程组 `{ 5x^2 - 6xy + 5y^2 - 16 = 0; 2x^2 - (1+y) x + y^2 - y - 4 = 0 :}`

    视 `y` 为常数, 求结式: `"Res"_x(5x^2 - 6x y + 5y^2 - 16, 2x^2 - (1+y)x + y^2 - y - 4)` `= 32(y - 2)(y - 1)(y + 1)^2`. 用计算机验证: 
      factor(resultant(5*x**2-6*x*y+5*y**2-16, 2*x**2-(1+y)*x+y**2-y-4, x))
    从而 `y = 2` 或 `+-1`.
  1. `y = 2` 时, 解 `{5x^2 - 12 x + 4 = 0; 2x^2 - 3x - 2 = 0:}` 得 `x = 2`;
  2. `y = 1` 时, 解 `{5x^2 - 6x - 11 = 0; 2x^2 - 2x - 4 = 0:}` 得 `x = -1`;
  3. `y = -1` 时, 解 `{5x^2 + 6x - 11 = 0; 2x^2 - 2 = 0:}` 得 `x = 1`;
    4. 综上解为 `(2, 2)`, `(1, -1)`, `(-1, 1)`.

参数方程与结式 [来自《A guide to plane algebraic curves》] 设曲线的参数方程为 `{x = p(t); y = q(t):}`, `p, q` 为多项式, 则我们总能得到隐方程 `F(x, y) = 0`, `F` 为二元多项式. 参见这里.