$U(\Z/m\Z)$ 的结构
MatrixGroup
·
·
算法·理论
想把自己数论课/概率论课/组合数学课的笔记摘抄过来，但却不知道从哪里开始呢……
U(\Z/m\Z) 的结构
对于环 R，U(R) 为 R 中单位的集合，则其关于乘法为一个群，称为单位群。
引理. 设 $\mathbb F$ 为域，$f(x)\in \mathbb F[x]$ ，则 $\deg f(x)=n\Rightarrow f(x)=0$ 最多有 $n$ 个根。
定理. 设 $\mathbb F$ 为域，$G$ 为乘法群 $F^*$ 的有限子群，$|G|=n$，则 $d|n$ 时，$x^d=1$ 在 $F$ 中有 $d$ 个不同的根，它们都在 $G$ 中。
$d=1$ trivial。
$d>1$，$x^n-1=(x^d)^{n/d}-1=(x^d-1)g(x)$。显然 $G$ 中所有元素都满足 $x^n-1=0$，取满了，那么只能 $d$ 个 $x^d-1=0$，其他 $g(x)=0$。
定理. $G$ 是循环群，有 $\varphi(|G|)$ 个生成元。
设 $\psi(d)$ 为 $G$ 中所有 $d$ 阶元的集合（$d||G|$），则 $|\psi(d)|=\varphi(m)$。故 $G$ 有 $|G|$ 阶元，故其为循环群。
设 $a$ 与 $m$ 互素，则 $\min\limits_{a^d\equiv 1\pmod m,d>0}d$ 称为 $a$ 模 $m$ 的阶。
若 $g$ 模 $m$ 的阶为 $\varphi(m)$，称 $g$ 为 $m$ 的一原根。
定理. 模素数存在原根。证：由上易得。
定理. 若 $m$ 存在原根，则有 $\varphi(\varphi(m))$ 个原根。证：由上易得。
孙猜想：对于每个素数 $p$ 存在原根 $g<p$ 形如 $x^2+1$。
引理：设 $p$ 为奇素数，$p\perp a$，$\alpha\in \Z^+$，则 $1+ap$ 模 $p^\alpha$ 的阶为 $p^{\alpha-1}$。
只需证 $(1+ap)^{p^{n-2}}\equiv 1+ap^{n-1}\pmod {p^n}$（归纳）
定理. 设 $p$ 为奇素数，$\alpha\in \Z^+$，则 $p^\alpha$ 存在原根。
设 $g$ 为模 $p$ 以原根，则 $(g+p)^{p-1}\equiv g^{p-1}-pg^{p-2}\pmod {p^2}
令 $g'^{p-1}=1+ap$，则 $a\perp p$，则 $1+ap$ 模 $p^\alpha$ 的阶为 $p^{\alpha-1}$。换言之 $g'^{(p-1)p^{\alpha-2}}\not\equiv 1$。
又 $(g')^{n(p-1)}=(1+ap)^n\not\equiv 1\pmod {p^\alpha}$，$1\le n<p^{\alpha-1}$。故 $(p-1)|$ 阶。
综上 $g'$ 是原根。
例. 设 $p$ 为奇素数，$\sum\limits_{i=1}^{p-1}i^n\bmod p=?
例. 设 $p$ 为奇素数，则 $(p-1)!\equiv g^{p(p-1)/2}\equiv g^{(p-1)/2}\equiv -1\pmod p$。
引理. $n\ge 3$ 时，$5^{2^{n-3}}\equiv 1+2^{n-1}\pmod {2^n}$。归纳即可。
定理. 模 $2,4$ 时有原根，模 $2^k,k\ge 3$ 时没有原根。
$U(\Z/2^k\Z)\cong \langle-1\rangle\times\langle5\rangle$，$\langle x\rangle $ 表示 $x$ 生成的模 $2^k$ 的循环群。
证. $2,4$ trivial. $5$ 模 $2^k$ 的阶为 $2^{k-2}$。
$(-1)^a5^b$ 为简化剩余系？$(-1)^a5^b\equiv (-1)^c5^d\pmod {2^k}$，模 $4$ 得 $a=c$，又 $b=d$。$\square
定理. 设 m\in \Z^+,p 为奇素数，则模 m 有原根当且仅当其形如 1,2,4,p^\alpha,2p^\alpha。
【模 2p^\alpha 原根的存在性】令 g 为模 p^\alpha 原根，则 g 与 g+p^\alpha 中的奇数是模其原根。
【其余情况的不存在性】（若）不妨设 m=m_1m_2,\gcd(m_1,m_2)=1,m_1,m_2>2，则 U(\Z/m\Z)\cong U(\Z/m_1\Z)\times U(\Z/m_2\Z)，但 (-1,1) 和 (1,-1) 均为二阶元，矛盾！
离散对数：\operatorname{ind}_ga\equiv n\pmod{\varphi(m)}。和对数相似。
定理. 设模 m 有原根 g，a\perp m，则 a 为 k 次剩余当且仅当 a^{\varphi(m)/\gcd(k,\varphi(m))}\equiv 1\pmod m。