函数(又称欧拉函数)是指小于等于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时为除式,用数学归纳法证明余式。
由组合数为整数可得。