数论 > 初等数论 > 初等数论/同余


同余的定义在第一章已经说明了,即a 当m|a-b时,数论中很多定理和证明用一般带余数除法的表示法也能做得出来,但是这些定理和证明若用同余式表示往往更加地简便明了

同余的性质 编辑

由同余的定义和基本的算术运算法则,可推出:

  •   ,则有 ,和 ,但是反过来时不一定成立
  •   ,则 
  •  则存在整数C,使得 

同余类与剩余系 编辑

同余类:对于模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,:  = ,即 函数为一积性函数

例子: =  =12

除了 = 外,对其他的 ,都有 

另一方面,若设m的一个简化剩余系为 ,其中对于任何  ,而这个简化剩余系的元素有k个,则 

费马小定理 编辑

费马小定理:对于任意正整数a,及任意质数p,有以下关系式:

 

其中对任意使(a,p)=1的a,有以下关系式:

 

欧拉定理 编辑

欧拉定理:对于任意的 ,存在有以下的关系式:

 

并且 中的数两两不同余

利用简化剩余系证明欧拉定理
 为模m的简化剩余系

由于  也是模m的简化剩余系
 
 
 ,得 

卡迈克尔函数 编辑

卡迈克尔函数 满足 ,其中a与n互质。

当n为2、4、奇质数的指数、奇质数的指数的两倍时为欧拉函数,当n为2,4以外的2的指数时为它的一半。  

欧拉函数有 

由算术基本定理,正整数n可写为质数的积 

对于所有n, 是它们的最小公倍数:

 

证明当a与n互质时, 
由费马小定理得 

 

 

由数学归纳法得 成立,这是一般情况。

 

 

 

 

由数学归纳法得当 时, 成立。

威尔逊定理 编辑

威尔逊定理:对于所有质数 ,都有 ,且若此式成立,p为质数

证明威尔逊定理

如果p不是质数,它的正因数必然包含在 中,因此 
 ,与 矛盾。
所以 成立时p一定是质数。

若p是质数, 是模p的剩余系
 
 时, 
其余 两两配对
 

费马小定理余式推广 编辑

 

除式: 

余式: 

n=0时为除式,用数学归纳法证明余式。

阶乘幂 编辑

 

由组合数为整数可得。

习题 编辑

第一部分─基础题 编辑

第二部分─进阶题 编辑