既约剩余系

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 n)`, 同余式两边同乘 `a^(-delta q)` 得 `a^r -= 1 (mod n)`, 再由 `delta` 的最小性知 `r = 0`.
2. 不妨取 `0 le j le i lt delta`, 则 `a^i -= a^j (mod n) iff a^(i-j) -= 1 (mod n)`, 由 `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(n)`, 且 `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` 是唯一的.

[来自群友 西伯利亚的猫猫] 设 `n`, `a` 为正整数, `a gt 1`, 则 `n | varphi(a^n-1)`.

这是因为 `"ord"_(a^n-1) a = n`.

阶的若干计算性质.
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`.

原根的存在性

[来自铁球@知乎、 OI Wiki]

讨论模 `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. 设 `m = a b`, 其中 `a, b` 互素. 若 `g` 是模 `m` 的原根, 则它也是模 `a, b` 的原根, 且 `varphi(a), varphi(b)` 互素.
2. 设 `g` 是模 `p^(n+1)` 的原根, 则它也是模 `p^n` 的原根.

1. 对任意 `g in ZZ_m^ast`, 我们有公式 `"ord"_m g = lcm("ord"_a g, "ord"_b g)`. 假如 `g` 是模 `m` 的原根, 等号左边等于 `varphi(m)`, 且右边整除 `lcm(varphi(a), varphi(b))` `le varphi(a) varphi(b)` `= varphi(m)` 要使左右相等, 只有让 `"ord"_a g = varphi(a)`, `"ord"_b g = varphi(b)`, 即 `g` 也是模 `a`, `b` 的原根; 并且还要求 `varphi(a)`, `varphi(b)` 互素.
2. ??

模 `p` 的原根存在 设 `p` 为素数, 则
1. (Lagrange 定理) `k` 次同余方程 `f(x) -= 0 (mod p)` 最多有 `k` 个解. 这个性质实际上对域上的多项式方程都成立.
2. 特别当 `k | p-1` 时, `x^k -= 1 (mod p)` 恰有 `k` 个解.
3. 对任意 `k | p-1`, 模 `p` 的 `k` 阶元数目等于 `varphi(k)`. 特别 `p-1` 阶元数目等于 `varphi(p-1) gt 0`, 因此模 `p` 的原根存在.

1. 一次同余方程 `a x + b -= 0 (mod p)` 最多有一个解. 假设命题对 `k-1` 成立, 考虑 `k` 次同余方程 `f(x) -= 0 (mod p)`. 不妨设方程有解 `x = r`, 于是 `f(x) -= (x-r) g(x) (mod p)`. 由于 `p` 是素数, `p | a b iff p | a or p | b`, 我们有 `f(x) -= 0 (mod p)` `iff x - r -= 0 (mod p)` `or g(x) -= 0 (mod p)`. 由归纳假设 `g(x) -= 0 (mod p)` 最多有 `k-1` 个解, 因此原方程最多有 `k` 个解.
2. 设 `p-1 = k q`, 则 `x^(p-1) - 1` `= (x^k-1)(1 + x^k + cdots + x^((q-1)k))` `:= (x^k-1) g(x)`. 由 1. 知, `x^(p-1) -= 1 (mod p)` 的解数
   `le x^k -= 1 (mod p)` 和 `g(x) -= 0 (mod p)` 的解数
   `le k + k(q-1)` `= p-1`. 但由 Fermat 小定理, 同余方程 `x^(p-1) -= 1 (mod p)` 恰有 `p-1` 个解, 这意味上式等号全部成立, `x^k -= 1 (mod p)` 恰有 `k` 个解.
3. 把全体成员 `ZZ_p^ast = {1, cdots, p-1}` 按阶分类. 记 `k` 阶元的个数为 `N(k)`. 例如, 1 阶元只有 1, 2 阶元只有 -1, 于是 `N(1) = N(2) = 1`. 由于所有阶都是 `p-1` 的因子, 有 `sum_(k | p-1) N(k) = p-1`. 另一方面, `ZZ_p^ast` 中的数还可以按与 `p-1` 的最大公约数分类. 若 `a` 满足 `gcd(a, p-1) = k`, 则 `gcd(a, (p-1)//k) = 1`, 因此这样的 `a` 共有 `varphi((p-1)//k)` 个: `sum_(k | p-1) varphi((p-1)//k) = sum_(k | p-1) varphi(k) = p-1`. 对任意 `k | p-1`, 由 2. 知道同余方程 `x^k -= 1 (mod p)` 恰有 `k` 个解.
   (1) 如果存在 `k` 阶元 `a`, 可以验证 `a^1, cdots, a^k` 就是方程的 `k` 个解, 因此 `k` 阶元只需从这 `k` 个解中寻找. 由阶数公式, `a^r` 的阶等于 `k//(gcd(r, k))`, 从而 `"ord" a^r = k iff gcd(r, k) = 1`. 这样的 `a^r` 共有 `varphi(k)` 个, 即 `N(k) = varphi(k)`.
   (2) 如果不存在 `k` 阶元, 此时 `N(k) = 0`. 但这样一来等式 `sum_(k | p-1) N(k) = sum_(k | p-1) varphi(k)` 无法成立, 因此对任意 `k | p-1` 都存在 `k` 阶元. 证毕.

另一个证明. 任取 `a, b in Z_p^ast`, 由给定阶元素的存在性定理, 存在 `c in Z_p^ast` 使得 `"ord" c = lcm("ord" a, "ord" b)`. 对 `1 ~ p-1` 反复使用结论, 可知存在 `g in Z_p^ast` 使得 `"ord" g = lcm("ord" 1, cdots, "ord"(p-1))`. 记 `"ord" g = d`, 于是 `1 ~ p-1` 都是同余方程 `x^d -= 1 (mod p)` 的解, 从而由 Lagrange 定理知道 `d ge p-1`. 又显然 `"ord" g le p-1`, 所以 `"ord" g = p-1`.

模 `p` 的 `k` 次同余方程 `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|`.

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

1. 前面例题已经讨论了 `m` 为 2 的幂的情形: 模 `2, 4` 有原根, 而 `n ge 3` 时 `2^n` 无原根.
2. 设 `g` 是模 `m` 的原根, 下证 `m` 至多含有一个奇素数因子. 否则设 `m = p^r q^s n`, `p, q` 是不同的奇素数, 且与 `n` 互素. 由引理知道 `m` 也是模 `p^r`, `q^s` 的原根, 且 `varphi(p^r), varphi(q^s)` 互素. 但由于 `p, q` 为奇素数, 所以 `varphi(p^r), varphi(q^s)` 都是偶数, 不可能互素. 同理, `m` 不能同时有一个奇素数因子和一个因子 `2^n` (`n ge 2`), 这是因为 `varphi(p^r)` 和 `varphi(2^n)` 都是偶数.
3. 我们只剩下证明模 `p^n` 和 `2 p^n` 都是有原根的, `p` 为奇素数. 先取模 `p` 的原根 `g`, 对任意正整数 `n`, 记 `delta = "ord"_(p^n) g`. 事实上 `delta` 等于某个 `varphi(p^m)`, 这是因为 `varphi(p) | delta` 和 `delta | varphi(p^n)`, 所以存在 `1 le m le n` 使得 `delta = p^(m-1)(p-1)` `= varphi(p^m)`.
4. 由 Euler 定理, `g^(varphi(p^n)) -= 1 (mod p^n)`, 故存在唯一整数 `k_n` 使得 `g^(varphi(p^n)) = 1 + k_n p^n`. 下面证明 `k_1 -= k_2 -= cdots -= k_n (mod p)`. 利用 `varphi(p^(n+1)) = p varphi(p^n)` 有 `g^(varphi(p^(n+1)))` `= (g^(varphi(p^n)))^p` `= (1 + k_n p^n)^p` `= 1 + k_n p^(n+1) + R p^(n+2)` `= 1 + (k_n + R p) p^(n+1)`. 因此 `k_(n+1)` 和 `k_n` 模 `p` 同余.

   ---

   [注] 上述论证对 `p=2, n=1` 失效, 此时 `(1+k_n p^n)^p` 的展开中不存在 `p^(n+2)` 次项; 这就是为什么我们要求奇素数.
5. 下证 `g` 和 `g + p` 至少有一个是模 `p^n` 的原根. 设 `g^(p-1) = 1 + k p`, `(g+p)^(p-1) = 1 + k' p`, 则 `k !-= k' (mod p)`, 这是因为 `(g+p)^(p-1) -= g^(p-1) + p(p-1) g^(p-2)` `-= 1 + k p - g^(p-2) p (mod p^2)`, 即 `k' -= k - g^(p-2) (mod p)`, 其中 `g^(p-2) !-= 0 (mod p)`.
   因此, `k` 和 `k'` 至少有一个不是 `p` 的倍数, 不妨设 `p !| k`. 结合上一条结论知道对任意正整数 `n` 都有 `g^(varphi(p^n)) !-= 1 (mod p^(n+1))`. 特别 `g^delta !-= 1 (mod p^(m+1))`, 因此 `m ge n`, 综上有 `m = n`, 即 `delta = varphi(p^n)`.

   ---

   TODO: 和 Hensel 引理的关系??
6. 最后考虑模 `2p^n` 的原根, `p` 为奇素数. 设 `g` 是模 `p^n` 的原根, 则两个原根 `g` 和 `g + p^n` 中有一个是奇数, 不妨设它是 `g`, 则 `gcd(g, 2 p^n) = 1`. 设 `delta = "ord"_(2 p^n) g`, 则 `g^delta -= 1 (mod 2 p^n)`, 这推出 `g^delta -= 1 (mod p^n)`. 于是 `varphi(2 p^n) = varphi(p^n) | delta`, 这说明 `g` 也是模 `2 p^n` 的原根.

分圆多项式

设 `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^**`.

杂例

我们知道, `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`.