[latexpage]

求解欧拉函数的近世代数视角

剩余类环

定义.(零因子) 设 $latex R$ 是一个环. 对于 $latex a\in R$, 如果存在 $latex c\in R$ 且 $latex c\ne0$, 使得 $latex ac=0$ 或 $latex ca=0$, 则称 $latex a$ 是一个左零因子或右零因子. 左、右零因子统称为零因子.

命题 设 $latex R$ 是有非零单位元的环, 则 $latex R$ 的零因子不是可逆元.

注 常用上述命题的逆否命题：设 $latex R$ 是有非零单位元的环, 则 $latex R$ 的可逆元不是零因子.

如果一个域中的元素都属于复数集, 那么称这个域是数域. 例如有理数域 $latex \mathbb{Q}$, 实数域 $latex \mathbb{R}$, 复数域 $latex \mathbb{C}$.

命题 若 $latex m$ 是合数, 则 $latex \mathbb{Z}_m$ 不是域.

简证 设 $latex m=m_1m_2$ 是合数, 则 $latex \bar{m}_1$ 为零因子.

定理 在 $latex \mathbb{Z}_m$ 中, $latex \bar{a}$ 是可逆元当且仅当 $latex a$ 与 $latex m$ 互素.

证明 充分性. 设 $latex a$ 与 $latex m$ 互素, 则存在 $latex u,v\in\mathbb{Z}$, 使得
$$ ua+vm=1 \ \Rightarrow \bar{1}=\bar{u}\bar{a}+\bar{v}\bar{m}=\bar{u}\bar{a}.$$这说明 $latex \bar{a}$ 是可逆元.

必要性. 设$latex \bar{a}$ 是可逆元. 若 $latex a$ 与 $latex m$ 不互素, 即 $latex (a,m)=d\ne1$. 则 $latex a=a_1d, m=m_1d$, 从而
$$
\bar{a}\bar{m}_1=\bar{a}_1\bar{m}=\bar{0}.
$$由于 $latex \bar{m}_1\ne\bar{0}$, 所以 $latex \bar{a}$ 是左零因子, 不可逆. 矛盾!

推论 $latex \mathbb{Z}_m$ 的每个元素或者是可逆元, 或者是零因子.

定理 若 $latex p$ 是素数 , 则 $latex \mathbb{Z}_p$ 是一个域.

含有有限多个元素的域称为有限域.

$latex \mathbb{Z}_m$ 的所有可逆元组成的集合记作 $latex \mathbb{Z}^*_m$.

命题 $latex \mathbb{Z}^*_m$ 是一个群, 称它为 $latex \mathbb{Z}_m$ 的单位群.

欧拉函数

定义 设 $latex m$ 是大于 $latex 1$ 的整数, 集合 $latex {1,2,\cdots,m}$ 中与 $latex m$ 互素的整数的个数记作 $latex \varphi(m)$, 称 $latex \varphi(m)$ 为欧拉函数.

命题 $latex \varphi(m)$ 等于 $latex \mathbb{Z}_m$ 中可逆元的个数, 即 $latex \varphi(m)=|\mathbb{Z}_m^*|$.

如何计算 $latex \varphi(m)$ 的值?

命题 设 $latex p$ 是素数, 则 $latex \varphi(p)=p-1$.
简证 当 $latex p$ 为素数时, $latex \mathbb{Z}_p$ 是域.

命题 设 $latex p$ 是素数, 则对任意正整数 $latex r$ 有
$$ \varphi(p^r)=p^{r-1}(p-1).$$

通过计算猜测有下面的结论
设 $latex m=m_1m_2$, 且 $latex (m_1,m_2)=1$, 则 $latex \varphi(m)=\varphi(m_1)\varphi(m_2)$.

上式左边的 $ \varphi(m)$ 是 $ \mathbb{Z}_m$ 的可逆元个数. 上式右边的 $latex \varphi(m1)$ 是 $ \mathbb{Z}{m_1}$ 的可逆元个数, $latex \varphi(m2)$ 是 $ \mathbb{Z} {m _ 2}$ 的可逆元个数, 那么 $latex \varphi(m_1)\varphi(m2)$ 有没有可能是某一个环的可逆元个数呢? 考虑 $ \mathbb{Z} {m 1}$ 与 $ \mathbb{Z} {m 2}$ 的笛卡尔积 $ \mathbb{Z}{m1}\times \mathbb{Z}{m_2}$, 在其中规定加法和乘法如下
$$
\begin{aligned}
(a_1,b_1)+(a_2,b_2)&:=(a_1+a_2,b_1+b_2)\\
(a_1,b_1)(a_2,b_2)&:=(a_1a_2,b_1b_2)
\end{aligned}
$$

容易验证 $ \mathbb{Z}_{m1}\times \mathbb{Z}{m2}$ 成为一个有单位元 $latex (1,1)$ 的交换环, 把这个环叫做环 $ \mathbb{Z} {m 1}$ 与 $ \mathbb{Z} {m 2}$ 的直和, 记作 $ \mathbb{Z}{m1}\oplus \mathbb{Z}{m_2}$.

容易验证 $latex (a,b)$ 为 $ \mathbb{Z}_{m1}\oplus \mathbb{Z}{m2}$ 的可逆元当仅当 $latex a$ 为 $ \mathbb{Z} {m 1}$ 的可逆元且 $latex b$ 为 $ \mathbb{Z} {m_ 2}$ 的可逆元. 那么

命题 $ \mathbb{Z}_{m1}\oplus \mathbb{Z}{m_2}$ 的可逆元个数等于 $latex \varphi(m_1)\varphi(m_2)$.

这个命题给出了 $latex \varphi(m)=\varphi(m_1)\varphi(m_2)$ 的一个结构性的解释

域的特征

模 $latex p$ 剩余类域 $latex \mathbb{Z}_p$ 与数域 $latex K$ 有什么不同点呢？在 $latex \mathbb{Z}_p$ 中有
$$
\begin{aligned}
p\bar{1}&=\bar{p}=\bar{0}\\
l\bar{1}&=\bar{l}\ne\bar{0},\ \forall 0< l< p.
\end{aligned}
$$在数域 $latex K$ 中,
$$
n1=n\ne0,\ \forall n\in \mathbb{N}^*.
$$对任一域 $latex F$, 它的单位元 $latex e$ 的正整数倍有什么规律？我们有如下结论：

定理 设域 $latex F$ 的单位元为 $latex e$, 则或者 $latex ne\ne0, \forall n\in \mathbb{N}^*$, 或者存在素数 $latex p$ 使得 $latex pe=0$, 而 $latex le\ne0, \forall 0< l< p.$

证明 Case1. $latex ne\ne0, \forall n\in \mathbb{N}^*$
Case2. 存在正整数 $latex n$ 使得 $latex ne=0$. 设 $latex n$ 是使 $latex ne=0$ 成立的最小正整数. 若 $latex n$ 不是素数, 则
$$ n=n_1n_2,\ 1< n_1 < n,\ 1< n_2< n.$$ 那么
$$ (n_1e)(n_2e)=\cdots=ne=0.$$ 由 $latex n$ 的定义得 $latex n_1e\ne0, n_2e\ne0$. 于是 $latex n_1e$ 为零因子, 进而为不可逆元. 又 $latex n_1e\ne0$, 这与 $latex F$ 是域矛盾, 因此 $latex n$ 是素数.

定义 设域 $latex F$ 的单位元是 $latex e$. 如果 $latex ne\ne0, \forall n\in \mathbb{N}^*$, 则称域 $latex F$ 的特征为 $latex 0$; 如果存在素数 $latex p$, 使得 $latex pe=0$, 而 $latex le\ne0, \forall 0< l< p,$ 则称域 $latex F$ 的特征为 $latex p$. 域 $latex F$ 的特征记作 $latex \mathrm{char}\ F$.

模 $latex p$ 剩余类域 $latex \mathbb{Z}_p$ 的特征为 $latex p$; 任意数域的特征为 $latex 0$. 这就是 $latex \mathbb{Z}_p$ 与数域的本质区别.

命题 设域 $latex F$ 的特征为素数 $latex p$, 则 $latex pa=0,\forall a\in F$.
证明 只需注意到 $latex pa=p(ea)$.