$U(\Z/m\Z)$ 的结构

想把自己数论课/概率论课/组合数学课的笔记摘抄过来，但却不知道从哪里开始呢……

对于环 $R$，$U(R)$ 为 $R$ 中单位的集合，则其关于乘法为一个群，称为单位群。

$\Z/m\Z$ 为 $\Z/p^\alpha\Z$ 的直积。

引理. 设 $\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}$

$q_p(g+p)\equiv q_p(g)-g^{-1}\pmod p$，$q_p$ 为 Fermat 商。故存在 $g'\in\{g,g+p\},q_p(g')\not\equiv 0\pmod p$，即 $g'^{p-1}\not\equiv 1\pmod {p^2}$。我们断言 $g'$ 是 $p^\alpha$ 的原根。

令 $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-1)|n\to p-1$。$(p-1)\nmid n\to g^nS\equiv S,S\equiv 0$。

例. 设 $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$。