数学杂谈

发布于 2021-05-05  139 次阅读


食用前提示

本文用于记录菜鸡 Alkaid 学习过程中的一些推导与思考。由于作者本人水平有限,有不足之处还请指出,也麻烦喷轻点(。

本文对刚入门的像作者一样的数论萌新比较友好!也请大佬不要因为内容比较基础开D(。

阅读前你需要掌握:基础的数学推导能力(真的很基础)、关于素数和公约数的一些基本知识、逆元的求法。


剩余系

剩余系:是指对于一个正整数 $n$ ,一个整数集中的数对 $n$ 取模得到的余数域。

剩余类 :用于刻画 与模 $n$下的一个剩余 同余的所有数。

完全剩余系 : 一共 $0$ 到 $n-1$ 这 $n$ 个剩余类一起组成了 $n$ 的完全剩余系。

简化剩余系 :在 $n$ 的完全剩余系中选出所有与 $n$ 互质的数,组成 $n$ 的简化剩余系。

注意:剩余系是对于一个正整数来讲的。可以理解为前面必须加一个前缀:应表述为“ 模 $n$ 意义下的剩余系” ,而不能只说一个 “剩余系” 。

几条性质:

如果 $a_1$ , $a_2$ , … , $a_m$ 是模 $m$ 意义下的完全剩余系,且 $\gcd (k,m)=1$ ,则 $ka_1$ , $ka_2$ , … , $ka_m$ 也构成模 $m$ 意义下的完全剩余系。

证明:

由于 $\gcd(k,m)=1$ ,所以 $ka_i \equiv ka_j \Longrightarrow a_i \equiv a_j\pmod m$ 。

此时如果出现 $ka_i\equiv ka_j$ 的情况,就违反了完全剩余系的定义。

所以 $ka_i$ 两两不同余。

证毕。

设 $\gcd(m,m')=1$ , $a$ 取遍 $m$ 的完全剩余系中的值, $a'$ 取遍 $m'$ 的完全剩余系中的值,则 $a'm+am'$ 取遍 $mm'$ 的完全剩余系中的值。

证明: $a$ 和 $a'$ 的取值互不相同, $a'm+am'$ 一共就有 $mm'$ 种不同的取值(不考虑模 $mm'$ 时)。

那么我们只需要证明这 $mm'$ 个取值模 $mm'$ 意义下不同余就好了。

接下来我们使用反证法。

我们假设存在一组 $a_1'm+a_1m' \equiv a_2'm+a_2 m' \pmod {mm'}$ ,其中 $a_1 \not \equiv a_2$ ,$a_1' \not\equiv a_2'$。

那么我们可以移项: $(a_1'-a_2')m+(a_1-a_2)m' \equiv 0 \pmod {mm'}$ 。

插入一条关于 $\gcd$ 的有用性质(下面会用到):

如果 $\gcd(k,p)=d$ ,则 $ka \equiv kb \pmod p \Longrightarrow a \equiv b \pmod {\frac p d}$ 。

这个性质的对于 $k \bot p$ 的特殊形式非常有用(下面的下面会用到):

$\gcd(k,p)=1$ ,则 $ ka \equiv kb \pmod p \Longrightarrow a \equiv b \pmod p$ 。

由于 $\gcd (m,m')=1$ ,所以根据上面的性质,分别为令 $d=m$ 和 $d=m'$ 可以得到:
$$
\begin{cases}
(a_1'-a_2') \times m \equiv 0 \pmod {m'}
\\
(a_1-a_2) \times m' \equiv 0 \pmod m
\end{cases}
$$
则还是由于 $\gcd(m,m')=1$ ,有
$$
\begin{cases}
m \not\equiv 0 \pmod {m'}
\\
m' \not\equiv 0 \pmod m
\end{cases}
$$
所以
$$
\begin{cases}
a_1 \equiv a_2 \pmod {m'}
\\
a_1' \equiv a_2' \pmod m
\end{cases}
$$
推出矛盾,则原命题成立。

证毕。


欧拉函数:

欧拉函数 $\varphi$ ,读作 phi ,第一声。

$\varphi (x)$ 表示 $1$ 到 $x$ 中与 $x$ 互质的正整数个数。

比如说 $\varphi(1)=1$ ,因为 $1$ 与 $1$ 互质。

几条性质:

当 $p$ 为质数时, $\varphi(p)=p-1$ 。

证明:显然 $1$ 到 $p-1$ 都和 $p$ 互质。

当 $p$ 是质数时, $\varphi(p^a) = p^a - p^{a-1} $ 。

证明:由于 $p^a$ 的质因子只有 $p$ 一个,所以 $\gcd (x,p^a)=1 \Longleftrightarrow \gcd(x,p)=1$ 。

显然 $[1,p^a]$ 中只有 $p$ 的倍数与 $p$ 不互质,而 $p^a=p \times p^{a-1}$ ,也就是一共有 $p^{a-1}$ 个这样的数。

所以 $\varphi(p)=p^a-p^{a-1}$ ,证毕。

欧拉函数是积性函数。

积性函数:如果对于任意 $\gcd(a,b)=1$ ,有 $f(a \times b )=f(a) \times f(b)$ ,则 $f$ 为积性函数。

这里提供两种证明。

一种是源于《哈代数论》 的,基于简化剩余系的证明。


费马小定理:

对于任意质数 $p$ 和 整数 $a$,满足 $\gcd(a,p)=1$,有 $a^{p-1} \equiv 1 \pmod p$ 。

或者说:

对于任意质数 $p$ 和整数 $a$ ,有 $a^p \equiv a \pmod p$ 。

证明?OI不需要证明。

费马小定理实际上是欧拉定理的一种特殊情况($p$ 为质数)。

而欧拉定理前面已经证明过了,那么费马小定理就不用证了吧。

其实是我懒

咕咕咕,还没写完,Alkaid正在努力填坑!


我们无法选择过去,但我们可以改变未来。