数论笔记整理2
威尔逊定理:
判定一个自然数是否为素数的充要条件:$ (p - 1)! \equiv -1 \;( mod \; p) $,当且仅当p为素数。
证明:
一、充分性(逆否命题):若p不是素数,即p是合数,则 $ (p - 1)! \not\equiv -1 \;( mod \; p) $。
特殊情况:当 $ p = 4 $ 时,$ [(p - 1) !\equiv 6 \equiv 2 \;(mod \; p)] \not\equiv -1 \;( mod \; p) $,显然成立;
当 $ p > 4 $ 时,分2种情况讨论:
①若p不是完全平方数,则 $ \exists \; a, b \in [1, p) \land (a \neq b) $,使得 ,
则 ,显然成立。
②若p是完全平方数,即 $ \exists \; k > 2 \land (k, 2k < p) $,使得 $ p = k^2 $,
则 ,显然也成立。
二、必要性:若p为素数,则 $ (p - 1)! \equiv -1 \;(mod \; p) $。
当 $ p = 2 \vee p = 3 $ 时,显然恒等式成立;
当 $ p \ge 5 $ 时,令集合 $ A = {1,2,3,\cdots,p-1} $,显然集合A中每个元素都与p互质,即集合A是模p的一个缩系;令集合 $ B = {2,3,\cdots,p-2} $,对 $ \forall \; a \in B $,令集合 $ C = {a,2a,\cdots,(p-1)a} $,由缩系的性质可得集合C也是模p的一个缩系,即集合C中每个元素:模p不同余且不能被p整除。
下面证明集合C是模p的一个缩系:
①因为 $ (p\nmid a \in B) \land (p \nmid b \in A)$,所以素数p不整除集合C中的每个元素
;
②若 $ \exists \; t_1, t_2 \in A \land (t_1 \neq t_2) $,使得 ,则由同余的性质可得 ,又因 ,显然这与集合C中每一个元素不能被p整除相矛盾,所以 ,即集合C中每个元素模p不同余
!
因此,$ C \; mod \; p = A $,则对 $ \forall \; a \in B $,必 $ \exists \; b \in A $,使得 $ ab \equiv 1 \;(mod \; p) $。
下面证明 $ b \notin {1,p-1,a} $:
若 $ b = 1 $,则 $ a \equiv a \not\equiv 1 \; (mod \; p) $,显然不成立;
若 $ b = p - 1 $,则 $ a(p - 1) \equiv (p - a) \not\equiv 1 (mod \; p) $,显然不成立;
若 $ b = a $,则 $ a^2 \equiv 1 \;(mod \; q)$,解得 $ a = 1 \vee a = p - 1 $,因为 $ a \in B $,所以不成立。
综上所述,$ \forall \; a, b \in B $,当a不同时,b也随之不同,即对于集合B中的每一个元素a都能够找到一个与之配对的b,使得 $ ab \equiv 1 \;(mod \; p) $,所以 .证毕!
备注:
①剩余类(也称同余类):设模数为m,则根据余数可将所有的整数分为m类,把所有与整数a模m同余的整数构成的集合叫做模m的一个剩余类,记作 $ [a] $,并把a叫作剩余类 $ [a] $ 的一个代表元。
②简化剩余系(也称既约剩余系、缩系):如果一个模m的剩余类里面的数与m互素(显然,只需有一个与m互素,其余的均与m互素)就称之为一个与模m互素的剩余类,在与模m互素的全部剩余类中,各取一数所组成的集合叫做模m的一个简化剩余系。
③缩系的性质:1)、对于任意一个与m互素的正整数k,即 $ \gcd(k, m) = 1 $,若 为模m的一个缩系,则 也为模m的一个缩系。2)、。
费马小定理:
定义:当 $ p $ 是素数时,对 $ \forall \; a \in \mathbb{Z}$,都有 $ a^p \equiv a \;(mod \; p) $。
特别地,当 $ \gcd(a,p)=1 $ 时,有 $ a^{p-1} \equiv 1 \; (mod \; p) $。
证明:
用完系的性质证明特殊情况:已知p是素数,令集合A为模p的最小非负完系的一个子集(去掉余数0),即 $ A = {1,2,3,\cdots,p-1} $,显然
集合A中每个元素都与p互质
。对 $ \forall \; a \in \mathbb{Z} \land \gcd(a,p)=1 $,令集合 $ C = {a,2a,\cdots,(p-1)a} $,由完系的性质2可得集合C也是模p的一个完系的一个子集(去掉余数0),
则 ,
$ \Rightarrow (p-1)! \equiv (p-1)! * a^{p-1} \; (mod \; p) $,因为 $ \gcd\left((p-1)!,p\right)=1 $,
由同余式的性质约去 $(p-1)! $ 得 $ a^{p-1} \equiv 1 \;(mod \; p) $,证毕!
备注:
④完全剩余系(简称完系):从模m的每个剩余类中各取一个数,得到一个由m个数组成的集合,叫做模m的一个完全剩余系。
完系的性质:1)、对于m个整数,其构成模m的完系等价于其关于模m两两不同余
;2)、对于任意一个与m互素的整数k,即 $ k \in \mathbb{Z} \land \gcd(k, m) = 1 $,若 $ {a_1,a_2,\cdots,a_m} $ 为模m的一个完系,则 也为模m的一个完系。3)、$ {0,1,\cdots,m-1} $ 称为模m的最小非负完全剩余系。
欧拉定理:
定义:若 $a,m \in \mathbb{N}^+ \land \gcd(a,m) =1 $,则 $ a^{\varphi(m)} \equiv 1\;(mod\;m)$。
证明:
证明用到缩系的性质:令 与m互素的数 构成集合A,即 ,显然集合A为模m的一个缩系。
由缩系的性质可得对于任意一个与m互素的正整数a,即 $ a \in \mathbb{N}^+ \land \gcd(a, m) = 1 $,令 ,显然集合C也为模m的一个缩系,
下面证明集合C是模m的一个缩系:
①集合C中任意两个数模m都不同余。用反证法证明:若 ,其中 ,则根据同余的性质可得 ,
又因为 ,所以 ,
即集合C中任意两个数模m都不同余!
②集合C中每个元素模m的余数都与m互素。
证明:因为 ,所以 。根据欧几里得算法:因为 ,所以 ,即集合C中任意一个数模m得余数都与m互素。
综上,集合C是模m的一个缩系。
则 ,
因为 ,
由同余的性质约去 $ \prod_{i=1}^{\varphi(m)} x_i $ 得 $ a^{\varphi(m)} \equiv 1\;(mod\;m)$,证毕!
推论:
若 $ \;a,b,m \in \mathbb{N}^+ \land \gcd(a,m)=1 $,则 $ a^b \equiv a^{b \% \varphi(m)} \;(mod\;m) $
证明:设 $ b=k \times \varphi(m)+r$,其中 $ k \in \mathbb{Z} \land 0 \leq r < \varphi(m) $。
因为 $ a^{\varphi(m)} \equiv 1\;(mod\;m)$,所以 $ (a^{\varphi(m)})^k \equiv 1 \;(mod\;m) $,
则 $ a^b \equiv a^{k \times \varphi(m)+r} \equiv (a^{\varphi(m)})^k \times a^r \equiv a^r \equiv a^{b\%\varphi(m)} \;(mod\;m)$,证毕!
扩展欧拉定理:
若 $a,b,m \in \mathbb{N}^+ $ (扩展到a和m不互质的情况),则有:
备注:
注意:当 $ b \leq \varphi(m) $ 时,不能套用第二个公式,举个栗子:
$ 2^2 \;(mod\;8) \neq 2^{2\%4+4} \;(mod\;8) $。
中国剩余定理:
经典栗子:韩信点兵。
求解用到的引理:①两个数不能整除,若被除数扩大(或缩小)a倍,除数不变,则商和余数也扩大(或缩小)a倍。
②两个数相加,若存在一个数不能被整数a整除,则它们的和也不能被整数a整除。
一元线性同余方程组:其中 均两两互质,求x的最小非负整数解。
解法:令 ,即M是所有模数的最小公倍数,是除了当前方程的模数外其他所有方程的模数的最小公倍数,设 为同余方程 的最小非负整数解,则该方程组的一个解为,通解为 ,其中 。特别地,最小非负整数解为 。
扩展中国剩余定理:
同样是一元线性同余方程组,若n个同余方程的模数不都两两互质,那该如何求解呢?
首先我们从简单入手,考虑一下同余方程组只有两个式子的情况,目标:合二为一。将两个式子变形得
联立并移项得 $ m_1 \cdot k_1=r_2-r_1+m_2\cdot k_2 $,由贝祖定理得方程有解的充要条件是 $ \gcd(m_1,m_2)\;|\;(r_2-r_1)$。若有解,则方程两边同除以 $\gcd(m_1,m_2)$ 得
转换为同余关系得
到这里,$k_2$ 被消去了,接着同余式两边同除以 $ \frac{m_1}{\gcd(m_1,m_2)}$ 得
其中 $inv(a,b) $ 表示a在模b意义下的乘法逆元,将同余式表示为方程得
把 $k_1$ 代入 $ x= r_1 + m_1 \cdot k_1$ 得
转化为同余关系得
终于,我们成功地将两个同余方程合并成一个同余方程:$ x \equiv r_2’ \;(mod\;m_2’)$,其中
亦即 $ r_2’=k_1’ \times m_1 + r_1, m_2’=lcm(m_1,m_2)$。
注意:通过ext_gcd可以解出 $ k_1 $,其为模 $\frac{m_2}{\gcd(m_1,m_2)}$ 意义下的一个非负整数解,那么对于裴蜀等式 $ax+by=c$ 来说:若该方程有解,用ext_gcd求解出来的x和y的一组解是 $ x’ = \frac{c}{\gcd(a,b)}x_0,y’=\frac{c}{\gcd(a,b)}y_0$,则通解为
综上所述,每次把两个同余式合并,求解之后得到一个新的同余式,再把新的同余式和其他的联立合并,最终就可以求出满足条件的解x。
- 本文链接: http://blog.wzomg.cn/posts/545d3697.html
- 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!