既约剩余系

Euler `varphi` 函数 (Euler's totient function) 设 `n` 为正整数, `1` 到 `n` 中与 `n` 互素的整数个数记为 `varphi(n)`.
比如, 8 以内与 8 互素的正整数有 1, 3, 5, 7 共 4 个, 于是 `varphi(8) = 4`.

[证明参见 Euler 函数]
1. 对一切正整数 `n gt 1` 有 `varphi(n) lt n`.
2. 对素数 `p` 有 `varphi(p) = p-1`. `varphi(p^k) = p^k - p^(k-1)`. 这是因为 `p^k` 以内, `p` 的倍数有 `p^(k-1)` 个.
3. `varphi` 是积性函数, 即若 `a, b` 互素, 则 `varphi(a b) = varphi(a) varphi(b)`.
4. 综上有 `varphi(n) = n prod_(p | n) (1-1/p)`.

既约剩余系 若 `a -= b (mod n)`, 则由辗转相除法知道 `(a, n) = (b, n)`. 特别 `(a, n) = 1` 当且仅当 `(b, n) = 1`. 因此可以从模 `n` 的完全剩余系 `ZZ_n` 中取出一个子集, 称为模 `n` 的既约剩余系: `ZZ_n^** = { bar a | (a, n) = 1 } sube ZZ_n`. 显然 `|ZZ_n^**| = varphi(n)`.

`ZZ_n^**` 按模 `n` 的乘法构成一个 Abel 群, 单位元是 `bar 1`.

乘法交换律与结合律是显然的.
1. 封闭性. 若 `(a, n) = (b, n) = 1`, 可设 `x_1 a + y_1 n = 1`, `quad x_2 b + y_2 n = 1`, 相乘得 `X a b + Y n = 1`, 其中 `X, Y` 为整数. 这说明 `(a b, n) = 1`.
2. 逆元的存在性. 若 `(a, n) = 1`, 可设 `x a + y n = 1`, 即 `x a -= 1 (mod n)`, `x` 即为 `a` 的逆.

若 `G` 为一群, `a in G`, 则左平移变换 `l_a: g mapsto a g` 为双射. 于是 `a G = {a g | g in G} = G`. 推论: 若 `S = {r_i}_(i=1)^s` 为模 `n` 的完全 (或既约) 剩余系, `a in S`, 则 `{a r_i}_(i=1)^s` 也是模 `n` 的完全 (或既约) 剩余系.

由 `a g_1 = a g_2` 两边左乘 `a^-1` 得 `g_1 = g_2`, 故 `l_a` 是单射. 另一方面, 对任意 `g in G`, 存在 `a^-1 g in G` 被 `l_a` 映到 `g`, 故 `l_a` 是满射.

阶的定义与性质

设 `a in ZZ_n^**`, 称满足 `a^d -= 1 (mod n)` 的最小正整数 `d` 为 `a` 对模 `n` 的指数或阶, 记为 `"ord"_n a`. 上下文确定时, 下标 `n` 可以省略.

对于一般的整数 `a`, 若 `a^d -= 1 (mod n)`, 则 `(a^d, n) = 1`, 也能推出 `(a, n) = 1`. 下面总假定 `n gt 1` 且 `(a, n) = 1`, 即 `a in ZZ_n^**`.

阶的唯一性 若 `a -= b (mod n)`, 则对任意 `k ge 0`, `a^k -= b^k (mod n)`. 从而 `a, b` 的阶相等.

阶的存在性 满足 的正整数 `d` 是存在的, 且 `"ord"_n a lt n`.

设 `n gt 1`, 因为 `(a, n) = 1`, 可设 `a^i -= r_i (mod n)`, `quad 0 lt r_i lt n`, `quad i = 0, 1, cdots, n-1`, `n` 个余数 `r_i` 只能取 `n-1` 个值, 由鸽巢原理, 必有两个余数相等, 设 `a^i -= a^j (mod n)`, `i gt j`. 同余式两边同乘 `a^-j` 得 `a^(i-j) -= 1 (mod n)`. 取 `d = i-j` 即得结论.

事实上 `"ord " a` 的上界可进一步降低, 这就是下面的 Euler-Fermat 定理:

Euler-Fermat 定理 (Euler's totitent theorem) 设 `a in ZZ_n^**`, 则 `a^(varphi(n)) -= 1 (mod n)`. 特别当 `n` 为素数 `p` 时, 上式即 Fermat 小定理 `a^(p-1) -= 1 (mod p)`.

设 `{r_i}_(i=1)^(varphi(n))` 是模 `n` 的既约剩余系, 乘 `a` 平移, `{a r_i}_(i=1)^(varphi(n))` 也是模 `n` 的既约剩余系. 从而 `prod r_i -= prod (a r_i) -= a^(varphi(n)) prod r_i` `(mod n)`, 两边约去 `prod r_i` 即得结论.

由 Euler-Fermat 定理, `"ord"_n a le varphi(n)`. 当等号成立时, 称 `a` 是模 `n` 的原根 (primitive root).

`"ord"_n a` 就是 `a` 在群 `ZZ_n^**` 中的阶. 若 `a` 为原根, 则 `a` 的阶等于群的阶 `varphi(n)`, 此时 `a` 是群的生成元, 既约剩余系具有循环群的简单结构.

若 `x^a -= x^b -= 1 (mod n)`, 这推出 `(x, n) = 1`. 运用辗转相除知 `x^((a,b)) -= 1 (mod n)`.

设 `a in ZZ_n^**`, `"ord "a = delta`, 则
1. 整除性质. `a^k -= 1 (mod n) iff delta | k`.
2. 对数性质. 若 `a^i -= a^j (mod n)`, 则 `i -= j (mod delta)`.

1. 只证必要性. 设 `n = delta q + r` (`0 le r lt delta`), 若 `a^n -= 1 (mod m)`, 同余式两边同乘 `a^(-delta q)` 得 `a^r -= 1 (mod m)`, 再由 `delta` 的最小性知 `r = 0`.
2. 不妨取 `0 le j le i lt delta`, 则 `a^i -= a^j (mod m) iff a^(i-j) -= 1 (mod m)`, 由 `delta` 的最小性知 `i-j = 0`, 即 `i -= j (mod delta)`.

1. 的另一证法. 利用引理, 若 `a^k -= a^delta -= 1 (mod n)`, 则 `a^((k, delta)) -= 1 (mod n)`. 由 `delta` 的最小性知道 `(k, delta) = delta`, 即 `delta | k`.

1. 由结论 1 知道, `delta | varphi(m)`, 且 `a^k` (`k = 0, 1, 2, cdots`) 模 `n` 的余数以 `delta` 为周期重复.
2. 由结论 2 知道, 在一个周期内, `a^k` (`k = 0, 1, cdots, delta-1`) 模 `n` 的 `delta` 个余数两两不同. 特别当 `a` 是原根时, 这 `delta = varphi(n)` 个数构成模 `n` 的既约剩余系.

若 `a^x = b (mod n)`, 则 `x` 称为 `b` (关于模 `n`, 以 `a` 为底) 的离散对数. 由结论 2 知道, 离散对数若存在, 则它关于模 `delta = "ord "a` 是唯一的.

讨论模 `m = 2^n` 的指数与原根. 此时有 `varphi(2^n) = 2^(n-1)`.
1. 模 `m = 2, 4` 时有原根;
2. `n ge 3` 时, 模 `m = 2^n` 无原根. 事实上对任意奇数 `a` 有 `a^(2^(n-2)) -= 1 (mod 2^n)`. 由于 `varphi(2^n) = 2^(n-1) gt 2^(n-2)`, 故此时无原根;
3. `n ge 3` 时, `"ord"_m 5 = 2^(n-2)`. 这时数字 5 是原根这一角色的一个 "替代品".

1. `m = 2` 时, `1` 是原根; `m = 4` 时, `"ord"(-1) = 2`, 故 `-1` 是原根.
2. 对 `n` 进行归纳. 设 `a = 2t+1`, 则 `n = 3` 时 `a^2 = 4t(t+1) + 1 -= 1 (mod 2^3)`, 结论成立. 假设结论对整数 `n ge 3` 成立, 则对 `n+1` 有 `2^(n+1) | (a^(2^(n-2))-1)(a^(2^(n-2))+1)` `= a^(2^(n-1)) - 1`, 结论也成立.
3. 2. 中已经证明 `"ord"_m 5 | 2^(n-2)`, 因而只需证 `"ord"_m 5 !| 2^(n-3)`, 即证 `5^(2^(n-3)) !-= 1 (mod 2^n)`, `quad n ge 3`. 对 `n` 进行归纳. `n=3` 时结论成立. 假设结论对整数 `n ge 3` 成立, 则 `n+1` 时, 由于 `5^(2^(n-3)) -= 1 (mod 2^(n-1))`, `quad n ge 3`. 可设 `5^(2^(n-3)) = 2^(n-1) s + 1`, 于是 `5^(2^(n-2)) = (2^(n-1) s + 1)^2` `= 2^n s(2^(n-2) s + 1) + 1`. 由归纳假设, `2 !| s`, 因此 `5^(2^(n-2)) !-= 1 (mod 2^(n+1))`.

阶的若干计算性质.
1. `n | m rArr` `"ord"_n a | "ord"_m a`;
2. 若 `(m, n) = 1`, 则 `"ord"_(m n) a = ["ord"_m a, "ord"_n a]`;

1. 只需注意 `n | m` 时, `a^delta -= 1 (mod m) rArr a^delta -= 1 (mod n)`;
2. 分别记 `"ord"_m a = M`, `"ord"_n a = N`, `"ord"_(m n) a = delta`. 由 1. 得 `[M, N] | delta`. 另一方面, 有 `a^([M,N]) -= 1 (mod m)`, `quad a^([M,N]) -= 1 (mod n)`, 由 `(m, n) = 1` 得 `a^([M,N]) -= 1 (mod m n)`, 因此 `delta | [M,N]`.

求模 `n` 的阶, 只需作分解 `n = prod n_i = prod p_i^(a_i)`, 就有 `"ord"_n a = ["ord"_(n_1) a, cdots, "ord"_(n_r) a]`.

阶数公式 设 `a, b in ZZ_n^**`:
1. 逆元的阶. `"ord"(a^-1) = "ord "a`;
2. 乘积的阶. `"ord"(a b) = "ord "a * "ord "b` 当且仅当 `("ord "a, "ord "b) = 1`;
3. 幂的阶. `"ord"(a^k) = delta//(k, delta)`, 其中 `delta = "ord "a`. 特别,
   1. 若 `delta = s t`, 则 `"ord"(a^s) = t`;
   2. `"ord"(a^k) = "ord "a` 当且仅当 `(k, delta) = 1`.

1. 只需注意对任意 `k ge 0`, `a^k -= 1 (mod n)` 当且仅当 `a^-k -= 1 (mod n)`.
2. 分别记 `a, b, a b` 的指数为 `A, B, delta`. 先证必要性: 我们有 `(a b)^([A,B]) -= 1 (mod n)`, 故 `A B = delta | [A,B]`. 这推出 `(A, B) = 1`.
   再证充分性. 一方面有 `(a b)^(A B) -= 1 (mod n)`, 故 `delta | A B`; 另一方面 `a^(delta B) = a^(delta B) b^(delta B) -= (a b)^(delta B) -= 1 (mod n)`, 故 `A | delta B`, 再由 `(A, B) = 1` 得 `A | delta`; 同理 `B | delta`. 再次由 `(A, B) = 1` 得 `A B | delta`.
3. 记 `"ord"(a^k) = l`, `(k, delta) = d`. 一方面, `(a^k)^(delta // d) = (a^delta)^(k//d) -= 1 (mod n)`, 故 `l | delta/d`; 另一方面 `a^(k l) = (a^k)^l -= 1 (mod n)`, 故 `delta | k l`, 即 `delta/d | k/d l`. 因为 `(delta/d, k/d) = 1`, 所以 `delta/d | l`. 综上有 `l = delta/d`.

原根的数目 `ZZ_n^**` 中若存在原根, 则原根的数目为 `varphi(varphi(n))`.

记 `"ord "a = delta`. 由幂的阶数公式, `ZZ_n^**` 中至少有 `a^k`, `quad 0 le n lt delta`, `(k, delta) = 1` 这 `varphi(delta)` 个数的阶等于 `delta`. 特别当 `a` 为原根时即得结论.

给定阶元素的存在性
1. 若 `(m, n) = 1`, 则对任意 `a, b`, 存在 `c` 使得 `"ord"_(m n) c = ["ord"_m a, "ord"_n b]`.
2. 对任意 `a, b`, 存在 `c` 使得关于模 `n` 有 `"ord "c = ["ord "a, "ord "b]`.

1. 因为 `(m, n) = 1`, 由孙子定理, 同余方程组 `x -= a (mod m)`, `quad x -= b (mod n)` 存在唯一解 `x -= c (mod m n)`. 因为 `c` 和 `a, b` 分别关于模 `m, n` 同余, 所以 `"ord"_m c = "ord"_m a`, `"ord"_n c = "ord"_n b`. 再由 `"ord"_(m n) c = ["ord"_m c, "ord"_n c]` 即得结论.
2. 分别记 `A = "ord "a`, `B = "ord "b`, `eta = [A, B]`. 作分解 `A = a_1 a_2`, `quad B = b_1 b_2`,
   其中 `(a_2, b_2) = 1`, `quad a_2 b_2 = eta`. 这样的分解是可行的: 设素因子 `p` 在 `eta` 中的次数为 `k`, 则 `p` 在 `A, B` 中的次数较高的那个也等于 `k`. 对 `eta` 的每个素因子都如此分类即可得到 `a_2, b_2`.
   现在由阶数公式, `"ord"(a^(a_1)) = a_2`, `quad "ord"(b^(b_1)) = b_2`, 取 `c = a^(a_1) b^(b_1)`, 由乘积的阶数公式, `"ord "c = "ord"(a^(a_1) b^(b_1)) = a_2 b_2 = eta`.

原根存在的充要条件

模 `m` 有原根的充要条件是 `m = 1, 2, 4, p^n, 2p^n`. 其中 `p` 是奇素数, `n ge 1`.

先证必要性, 充分性将在下文分几个定理完成证明. ??

`p` 为素数, `p !| n`, 则
1. 同余方程 `x^k -= 1 (mod p)` 共有 `(p-1, k)` 个解;
2. 同余方程 `x^k -= n (mod p)` 有 `0` 个或 `(p-1, k)` 个解.

1. 设 `g` 是模 `p` 的原根, `x = g^r`, 则 `g^(r k) -= 1(mod p)` `iff p-1 | r k` `iff (p-1)/((p-1,k)) | r`. 因此这样的 `r` 共有 `(p-1, k)` 个.
2. 线性叠加原理: 若 `x^k -= n (mod p)` 有解, 设为 `a`, 我们可以建立"齐次方程" `x^k -= 1 (mod p)` 的解集 `S` 到 "非齐次方程" `x^k -= n (mod p)` 的解集 `T` 之间的映射: `eta: S to T`,
   `s mapsto a s` 容易验证, 若 `s^k -= 1 (mod p)`, 则 `(a s)^k -= n (mod p)`, 即 `a s in T`. `eta` 是左平移变换因而是双射, 这说明 `|S| = |T|`.

我们知道, `1//7 = 0. dot 1 4285 dot 7`, 其循环节恰有 `7-1 = 6` 位. 在 100 以内, 除 2 以外, 满足 `1//n` 的循环节恰有 `n-1` 位这一性质的正整数 `n` 有: 7, 17, 19, 23, 29, 47, 59, 61, 97. 它们都是素数以外, 还有什么共同特点?

共同特点是: 10 是模 `n` 的原根. 原因是若 `10^d -= 1 (mod n)`, 即 `n | 10^d - 1`, 则分数 `1//n` 可以化为循环节 `d` 位的循环小数. 如 `10^6 -= 1 (mod 7)`, 则 `1/7 = 142857/999999 = 0. dot 1 4285 dot 7`. 又如 `10^6 -= 1 (mod 13)`, 则 `1/13 = 076923/999999 = 0. dot 0 7692 dot 3`. 因此, 当 `(10, n) = 1` 时, 循环节的长度就是 10 模 `n` 的指数. 要使循环节恰有 `n-1` 位, 就要求 10 模 `n` 的指数等于 `n-1`; 这当且仅当 `n` 是素数, 且 10 是模 `n` 的原根.

[manim 短篇 离散猫变换] 设 `bm A = [2, 1; 1, 1]`, `bm I = [1, 0; 0, 1]`. 依次取 `m = 11, 59, 2855`, 求 `"ord"_m bm A`, 即求最小的正整数 `n` 使得 `bm A^n -= bm I (mod m)`.

`bm A` 是对称矩阵, 因此可以对角化, 即存在模 `m` 可逆矩阵 `bm P` 使得 `bm A = bm P^-1 bm D bm P`, `quad bm D = [x, ; , y]`. 其中 `x, y` 是 `bm A` 模 `m` 的特征值. 若 `bm A^n -= bm I (mod m)`, 必有 `bm D^n -= bm I (mod m)`, 即 `{ x^n -= 1; y^n -= 1 :} (mod m)`. 注意 `|bm A| = 1`, 所以不论 `m` 取何值, `bm A` 总是非奇异的, 这蕴含 `x^n !-= 0, y^n !-= 0 (mod m)`, 特别当 `m` 为素数时, 上面的方程组总是有解.
1. `m = 11` 时, 由 `x + y -= 3, x y -= 1(mod 11)`, 利用求根公式得 `x, y -= (3 +- sqrt 5)//2` `-= (3 +- 4) * 6` `= -2, 5 (mod 11)` `mod 11` 下 `"ord" (-2) = "ord" 5 = 5`, 取最小公倍数得到 `"ord"_11 bm A = 5`.
2. `m = 59` 时特征值为 `(3 +- 8) * 30 -= -24, -32 (mod 59)`. 从而 `"ord"_59 bm A` `= lcm("ord"(-24), "ord"(-32))` `= lcm(29, 29) = 29`.
3. `m = 2855 = 5 * 571` 时, 模 `5` 的特征值为 `-1 (mod 5)` (2 重根), `"ord"_5 (-1) = 2`. 模 `571` 的特征值为 `(3 +- 24) * 286 -= 299, 275 (mod 571)`, 且 `"ord"_571 299 = "ord"_571 275 = 285`. 从而 `"ord"_2855 bm A = 2 * 285 = 570`.

分圆多项式

设 `lambda in CC`, 若 `n` 是使得 `lambda^n = 1` 成立的最小正整数, 则称 `lambda` 的阶为 `n`, 记为 `"ord"lambda = n`. 分圆多项式 (或割圆多项式)定义为 `phi_n(x) = prod_("ord"lambda = n) (x - lambda)`. `phi_n(x)` 的所有根称为 `n` 次本原单位根 `Theta_n = {zeta_n^k | (k, n) = 1 }`, `quad zeta_n = "e"^(2pi"i"//n)`. 因此 `phi_n(x)` 的次数就等于 `|Theta_n| = varphi(n)`.

若 `lambda, mu` 是两个 `n` 次本原单位根, 则存在与 `n` 互素的整数 `m` 使得 `mu = lambda^m`.

`lambda = zeta_n^j`, `mu = zeta_n^k`, `(j, n) = (k, n) = 1`, 只需取 `m` 使得 `j m -= k (mod n)`, 就有 `lambda^m = zeta_n^(j m) = zeta_n^k = mu`.

本原单位根与原根的概念不同. 原根 `r` 可以生成整个既约剩余系 `1, r, r^2, cdots`, 而本原单位根无此性质.

`x^n-1 = prod_(d | n) phi_d(x)`.

这个等式是对所有 `n` 次单位根按阶分类的结果. 注意和整数的阶一样, 我们有 `lambda^n = 1 iff "ord"lambda | n`.

尽管从定义看来不很显然, 但分圆多项式的系数都是整数!

分圆多项式 `phi_n(x)` 是首 1 的整数系数多项式, 其常数项 `in {1, -1}`.

首 1 性由定义立即看出. 对 `n` 进行归纳, `n=1` 时 `phi_1(x) = x-1`, 结论成立. 假设结论对一切 `d lt n` 成立, 考虑 `n` 的情形, 有 `x^n - 1 = prod_(d | n) phi_d(x) = F(x) phi_n(x)`, 其中 `F(x) = sum_(j=0)^l a_j x^j`, `quad phi_n(x) = sum_(j=0)^(n-l) b_j x^j`, 由归纳假设, `a_0 in {1, -1}`, 比较系数得 `b_0 in {1, -1}`. 又假定 `b_0, b_1, cdots b_(k-1)` 已被证实为整数, 比较两边 `x^k` 的系数知 `a_0 b_k + sum_(j=0)^(k-1) a_(k-j) b_j` 为整数, 因此 `a_0 b_k` 为整数, 从而 `b_k` 为整数.

`n = 105` 时, 分圆多项式的系数中首次出现 `{1, -1, 0}` 以外的数: `phi_105(x) = x^48+x^47+x^46-x^43-x^42- color(red)2 x^41-x^40-x^39+x^36+x^35+x^34` `+x^33+x^32+x^31-x^28-x^26-x^24-x^22-x^20+x^17+x^16+x^15+x^14+x^13` `+x^12-x^9-x^8-color(red)2 x^7-x^6-x^5+x^2+x+1`.

设 `a ge 1`, 当 `n = p^a` (`p` 为素数) 或 `2p^a` (`p` 为奇素数) 时, 分圆多项式的形式比较简单: `phi_(p^a)(x)` `= phi_(2p^a)(-x)` `= sum_(k=0)^(p-1) x^(k p^(a-1))` `= (x^(p^a)-1)/(x^(p^(a-1))-1)`.

1. `n = p^a` 次的本原单位根有 `Theta_n = {zeta_n^k | (k, n) = 1}` `= {zeta_n^k | p !| k}`, 所以 `phi_n(x)` 就等于从 `x^n-1` 中排除掉以下因子: `prod_(k=1)^(p^(a-1)) (x-zeta_n^(p k))` `= prod_(k=1)^(p^(a-1)) (x-zeta_(p^(a-1))^k)` `= x^(p^(a-1)) - 1`.
2. 设 `p` 为奇素数. 下证 `lambda` 的阶为 `p^a` 当且仅当 `-lambda` 的阶为 `2p^a`.
   若 `"ord"lambda = p^a`, 容易验证 `(-lambda)^(2p^a) = 1`; 又对任意 `d | 2p^a`, 若 `(-lambda)^d = 1`, 则 `d` 必为偶数, 有 `lambda^d = 1`; 因而 `2 b` 必为 `p^a` 的倍数, 只能 `d = 2 p^a`. 这指出 `-lambda` 的阶是 `2p^a`.
   反之若 `-lambda` 的阶为 `2p^a`, 则 `(-lambda)^(p^a)` 只能是 `-1`. 两边约去 `(-1)^(p^a)` 得 `lambda^(p^a) = 1`. 又对任意 `d | p^a`, 若 `lambda^d = 1`, 则 `(-lambda)^(2d) = 1`, 迫使 `d = p^a`, 即 `lambda` 的阶为 `p^a`.
   另一方面, `varphi(p^a) = varphi(2p^a) = p^a-p^(a-1)`, 这指出 `p^a` 次本原单位根和 `2p^a` 次本原单位根一样多. 因此, 只要将 `phi_(p^a)(x)` 中的 `x` 换成 `-x`, 就得到 `phi_(2p^a)(x)`.

`f(x) = phi_(p^a)(x)` 在 `QQ` 上不可约.

令 `g(x) = f(x+1)` `= ((x+1)^(p^a)-1)/((x+1)^(p^(a-1))-1)` `-= (x^(p^a)+1-1)/(x^(p^(a-1))+1-1)` `-= x^(p^a - p^(a-1)) (mod p)`. 这表明 `g(x)` 除最高项系数为 1 之外, 其余系数均为 `p` 的倍数. 另一方面 `g(x)` 的常数项为 `g(0) = f(1) = p`; 由 Eisenstein 判别法知 `g` 不可约, 因此 `f` 也不可约.

任意分圆多项式在 `ZZ` 上不可约, 从而由 Gauss 引理, 在 `QQ` 上也不可约.

1. 反设 `phi_n(x) = g(x) h(x)`, 其中 `g, h` 是首 1 的, 次数 `ge 1` 的整系数多项式, 且 `g` 不可约. 任取 `g` 的一根 `lambda` 和素数 `p !| n`, 下证 `lambda^p` 也是 `g` 的根.
2. 由分圆多项式定义, `lambda^p` 是 `phi_n(x)` 的根; 若它不是 `g` 的根, 则它是 `h` 的根, 因此 `lambda` 是 `g(x)` 和 `h(x^p)` 的公共根. 现在对 `p` 取模, 由 Fermat 小定理, `h(x^p) -= h(x) (mod p)`, 即 `g` 和 `h` 在模 `p` 意义下有公共根. 下证 `phi_n(x) = g(x) h(x)` 在模 `p` 意义下无重根, 从而引出矛盾.
3. `phi_n(x)` 是 `x^n-1` 的因子, 故只需证 `f(x) = x^n-1` 模 `p` 意义下无重根. 事实上, `(f(x), f'(x)) = (x^n-1, n x^(n-1)) = 1`, 因此它无重根.
4. 综上有 `lambda^p` 是 `g` 的根. 任取 `n` 次本原单位根 `lambda^m`, `(m, n) = 1`, 作素因子分解 `m = prod p_i`, 则 `lambda^m = ((lambda^(p_1))^(p_2))^cdots` 也是 `g` 的根. 这就是说 `phi_n(x)` 的所有根都是 `g` 的根, 从而 `phi_n(x) = g(x)` 是不可约多项式.

分圆域 是多项式 `x^n - 1 in QQ[x]` 的分裂域. 将任一本原单位根 `zeta_n` 加到 `QQ` 中都得到同一个分圆域 `QQ(zeta_n)`, 且 `phi_n(x)` 是 `zeta_n` 在 `QQ` 上的最小多项式. `QQ(zeta_n) // QQ` 是 Galois 扩张, 扩张次数为 Euler 函数 `varphi(n)`. 其 Galois 群 `Gal(QQ(zeta_n)//QQ)` 同构于 `ZZ_n^**`.