数论 > 初等数论 > 初等数论/同余
同余的定义在第一章已经说明了,即a
当m|a-b时,数论中很多定理和证明用一般带余数除法的表示法也能做得出来,但是这些定理和证明若用同余式表示往往更加地简便明了
由同余的定义和基本的算术运算法则,可推出:
- 若
且
,则有
,和
,但是反过来时不一定成立
- 若
且
,则![{\displaystyle a\equiv b{\pmod {m/|n|}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a92dacd3a97230441545570d59bb231ea04296fe)
- 若
则存在整数C,使得![{\displaystyle Ca=1{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/021429d68d60d4d97dd0e78b8fdcc86307a3c67d)
同余类:对于模m的元素,将所有对模m两两同余的数取出,所形成的集合称之为模m的同余类,即若
,则r和s属于模m的同一个同余类
剩余系:对于模m的不同同余类的元素,各取一个出来所形成的集合称之为模m的剩余系,即模m的一个剩余系中的所有元素两两不同余
函数(又称欧拉函数)是指小于等于n的自然数中与n互质的数的数目。
例子:
=2,因为在1,2,3,4,5,6中只有1,5是和6互质
若正整数n个标准分解式为
,则
函数的值为:
用逻辑集合的概念、排列组合及算术基本定理可验证此式的成立
如果(m,n)=1,:![{\displaystyle \phi (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52ddd8905bfc0ea59762651f0d18b1ec147006c2)
=
,即
函数为一积性函数
例子:
=![{\displaystyle \phi (4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e5be571730352f6cc7d44ea313ad8706f8704ae)
=12
除了
=
外,对其他的
,都有
另一方面,若设m的一个简化剩余系为
,其中对于任何
有
,而这个简化剩余系的元素有k个,则
费马小定理:对于任意正整数a,及任意质数p,有以下关系式:
其中对任意使(a,p)=1的a,有以下关系式:
欧拉定理:对于任意的
,存在有以下的关系式:
并且
中的数两两不同余
利用简化剩余系证明欧拉定理 设 ![{\displaystyle \{r_{1},r_{2},\dots ,r_{\phi (m)}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/066773bbdb4f558dad5ec226e53bde3e5e734d56) 为模m的简化剩余系
由于 , 也是模m的简化剩余系
![{\displaystyle (ar_{1})(ar_{2})\dots (ar_{\phi (m)})\equiv r_{1}r_{2}\dots r_{\phi (m)}{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a3aa64e6d5e4e5d5ad58180d13d8cf7372f0099)
![{\displaystyle a^{\phi (m)}(r_{1}r_{2}\dots r_{\phi (m)})\equiv r_{1}r_{2}\dots r_{\phi (m)}{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45f6c0f2fa162ad8eb7f690da7ceebe8e609a6e9)
又 ,得
|
卡迈克尔函数
满足
,其中a与n互质。
当n为2、4、奇质数的指数、奇质数的指数的两倍时为欧拉函数,当n为2,4以外的2的指数时为它的一半。
欧拉函数有
由算术基本定理,正整数n可写为质数的积
对于所有n,
是它们的最小公倍数:
证明当a与n互质时, ![{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e475506bcb72caae57599e0ccafa7efe023be9c) 由费马小定理得
由数学归纳法得 成立,这是一般情况。
由数学归纳法得当 时, 成立。
|
威尔逊定理:对于所有质数
,都有
,且若此式成立,p为质数
证明威尔逊定理
如果p不是质数,它的正因数必然包含在 中,因此![{\displaystyle ((p-1)!,p)\neq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f72f57cc5299753da28782adfdf3e73cada38f2)
,与 矛盾。
所以 成立时p一定是质数。
若p是质数, 是模p的剩余系
![{\displaystyle \forall i\in A,\exists j\in A,~s.t.~ij\equiv 1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10f4494f944fed876be3e614d949fa8d890789a2)
当 时,![{\displaystyle i^{2}\ \equiv \ 1{\pmod {p}}\Rightarrow i\equiv \pm 1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b5c577b9b01722c33338ae15f05b8da51c4b6e5)
其余 两两配对
|
除式:
余式:
n=0时为除式,用数学归纳法证明余式。
由组合数为整数可得。
![](//upload.wikimedia.org/wikipedia/commons/thumb/9/91/Book_important2.svg/45px-Book_important2.svg.png) |
此读本或页面内容似未齐全,宜加改进。 当内容获充分扩展后,请移除本模板。如需要协助,请至互助客栈。
|