文档介绍：欧拉定理
在数论中,欧拉定理(也称费马-欧拉定理或欧拉函数定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互素,gcd(a,n) = 1,则
其中为欧拉函数,为同余关系。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。
欧拉定理实际上是费马小定理的推广。
例子
首先看一个基本的例子。令a = 3,n = 5,这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4,所以。计算:,而。说明定理成立。
这个定理可以用来简化幂的模运算。比如计算7222的个位数,实际是求7222被10除的余数。7和10互素,且。由欧拉定理知。所以。
一般地,在简化幂的模运算的时候,(当a和n互素) 我们要对a的指数取模:
当,则。
证明
一般的证明中会用到“所有与n互素的同余类构成一个群”的性质,也就是说,设是比n 小的正整数中所有与n 互素的数对应的同余类组成的集合(这个集合也称为模n 的简化剩余系)。这些同余类构成一个群,称为整数模n乘法群。所以当对这些数进行变换的时候(a是和n互素的一个数,从而也属于某个同余类),变换所得的同余类集合仍然是原来的。即是说,集合和相同。因此,。从而
当n是素数的时候,,所以欧拉定理变为:
或
这就是费马小定理。
威尔逊定理:p为素数时:
证明: 充分性
如果“p”不是素数,那么它的正因数必然包含在整数1, 2, 3, 4, …, p − 1 中,因此gcd((p − 1)!, p) > 1,所以我们不可能得到(p − 1)! ≡ −1 (mod p)。
必要性
若p是素数,取集合; 则A 构成模p乘法的缩系,即任意i∈A ,存在j∈A,使得:
那么A中的元素是不是恰好两两配对呢? 不一定,但只需考虑这种情况
;
解得:或
其余两两配对;故而
若p不是素数则易知有d = gcd[p,(p − 1)!] = p,故而
一次不定方程
一次不定方程是形式如a1x1 + a2x2 + ... + anxn = c的方程,一次不定方程有整数解的充要条件为: gcd(a1,...,an)须是c的因子,其中gcd(a1,...,an)表示a1,...,an的最大公因子。
若有二元一次不定方程ax + by = c,且(a,b) | c,则其必有一组整数解x1,y1,并且还有以下关系式:
x = x1 + [b / (a,b)]t
y = y1 −[a / (a,b)]t
t为任意整数,故此一次不定方程有无限多解。
辗转相除法计算过程
辗转相除法是一种递归算法,每一步计算的输出值就是下一步计算时的输入值。[21]设k表示步骤数(从0开始计数),算法的计算过程如下。
每一步的输入是都是前两次计算的余数rk−1和rk−2。因为每一步计算出的余数都在不断减小,所以,rk−1小于rk−2。在第k步中,算法计算出满足以下等式的商qk和余数 rk:
rk−2 = qk rk−1 + rk
其中rk < rk−1。也就是rk−2要不断减去rk−1直到比rk−1小。
在第一步计算时(k = 0),设r−2和r−1分别等于a和b,第2步(此时k = 1)时计算r−1(即b)和r0(第一步计算产生的余数)相除产生的商和余数,以此类推。整个算法可以用如下等式表示:
a = q0 b