tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

第四讲-几个定理


初等代数选讲-----第四讲

第四讲
定义(欧拉(Euler)函数)

初等数论中的几个重要定理

一组数 x1 , x2 ,?, xs 称为是模 m 的既约剩余系, 如果对任意的 1 ? j ? s ,( x j , m) ? 1且 对 于 任 意 的 a ? Z , 若 (a, m) = 1 , 则 有

且 仅 有 一 个 x j 是 a 对 模 m 的 剩 余 , 即

a ? x j (modm) 。并定义 ? (m) ? s ? {1,2,?, m} 中和 m 互质的数的个数, ? (m) 称为欧拉
(Euler)函数。 这是数论中的非常重要的一个函数, 显然 ? (1) ? 1 , 而对于 m ? 1 ,? ( m) 就是 1,2, ?,

m ? 1 中与 m 互素的数的个数,比如说 p 是素数,则有 ? ( p) ? p ? 1 。
引理: ? (m) ? m ? ;可用容斥定理来证(证明略) 。 ?(1- P )

1

P|m P为质数

定理 1: (欧拉(Euler)定理)设 (a, m) =1,则 a? ( m) ? 1(modm) 。 证明: 取模 m 的一个既约剩余系 b1 , b2 ,?, bs , (s ? ? (m)) , 考虑 ab1 , ab2 ,?, abs , 由于 a 与

m 互质,故 abj (1 ? j ? s) 仍与 m 互质,且有 abi

abj (?1 ? i ? j ? s) ,于是对每个

1 ? j ? s 都能找到唯一的一个 1 ? ? ( j ) ? s , 使得 abj ? b? ( j ) (modm) , 这种对应关系 ? 是
一一的,从而

? (abj ) ? ? b? ( j ) (modm) ? ? b j (modm) ,? a s (? b j ) ? (? b j )(modm) 。
j ?1 j ?1 j ?1 j ?1 j ?1

s

s

s

s

s

? (m, ? b j ) ? 1,? a s ? 1(modm) ,故 a? ( m) ? 1(modm) 。证毕。
j ?1

s

分析与解答:要证 a

? ( m)

? 1(modm) ,我们得设法找出 ? ( m) 个 n 相乘,由 ? ( m) 个数我们

想 到 1,2,? , m 中 与 m 互 质 的 ? ( m) 的 个 数 : a1 , a2 ,?, a? ( m) , 由 于 (a, m) = 1 , 从 而

aa1 , aa2 ,?, aa? (m) 也 是 与 m 互 质 的 ? (m) 个 数 , 且 两 两 余 数 不 一 样 , 故
a1 ? a2 ??? a? ( m) ? aa1 , aa2 ,?, aa? (m) ? a ? ( m ) a1 ? a2 ??? a? ( m) ( mod m ), 而
( a1 ? a2 ? ?? a? ( m) m )=1,故 a
? ( m)

? 1(modm) 。

这是数论证明题中常用的一种方法, 使用一组剩余系, 然后乘一个数组组成另外一组剩 余系来解决问题。
1

初等代数选讲-----第四讲

定理 2: (费尔马(Fermat)小定理)对于质数 p 及任意整数 a 有 a p ? a(mod p) 。 设 p 为质数, 若 a 是 p 的倍数, 则 a p ? 0 ? a(mod p) 。 若 a 不是 p 的倍数, 则 (a, p) ? 1 由引理及欧拉定理得 ? ( p) ? p ? 1, a? ( p) ? 1(mod p) ,? a p?1 ? 1(mod p), a p ? a(mod p) ,由此即得。 定理 2 推论:设 p 为质数, a 是与 p 互质的任一整数,则? a p ?1 ? 1(mod p) 。 定理 3: (威尔逊(Wilson)定理)设 p 为质数,则 ( p ? 1)!? ?1(mod p) 。 分析与解答:受欧拉定理的影响,我们也找 p ? 1 个数,然后来对应乘法。 证明:对于 ( x, p) ? 1 ,在 x,2 x,?, ( p ? 1) x 中,必然有一个数除以 p 余 1 ,这是因为

x,2 x,?, ( p ? 1) x 则好是 p 的一个剩余系去 0。
从而对 ?x ? {1,2,? p ? 1}, ?y ? {1,2,?, p ? 1} ,使得 xy ? 1(mod p) ; 若 xy1 ? xy2 (mod p) , ( x, p) ? 1 ,则 x( y1 ? y 2 ) ? 0(modp) , p | ( y1 ? y 2 ) ,故 对于 y1 , y 2 ?{1,2,?, p ? 1} ,有 xy1

xy2 (mod p) 。即对于不同的 x 对应于不同的 y ,即

1,2,?, p ? 1中数可两两配对,其积除以 p 余 1,然后有 x ,使 x 2 ? 1(mod p) ,即与它自
2 己配对,这时 x ? 1 ? 0(modp) , ( x ? 1)(x ? 1) ? 0(mod p) , x ? ?1 或 x ? 1(mod p) ,

x ? p ? 1 或 x ? 1。
除 x ? 1, p ? 1 外, 别的数可两两配对, 积除以 p 余 1。 故 ( p ? 1)!? ( p ? 1) ? 1 ? ?1(mod p) 。 定 义 : 设 f j ( x) 为 整 系 数 多 项 式 ( 1 ? j ? k ) ,我们把含有 x 的一组同余式 ,当 f i ( x) 均为 x 的一次整系数 f j ( x) ? 0(modm j ) ( 1 ? j ? k )称为同余方组程。特别地, 多项式时,该同余方程组称为一次同余方程组.若整数 c 同时满足: f j (c) ? 0(modm j )

1 ? j ? k ,则剩余类 M c ? {x | x ? Z , x ? c(modm)} (其中 m ? [m1 , m2 ,?, mk ] )称为同
余方程组的一个解,写作 x ? c(modm) 定理 4 : (中国剩余定理)设 m1 , m2 ,?, mk 是两两互素的正整数,那么对于任意整数

a1 , a2 ,?, ak ,一次同余方程组 x ? a j (modm j ) , 1 ? j ? k 必有解,且解可以写为:

2

初等代数选讲-----第四讲

x ? M1 N1a1 ? M 2 N2 a2 ??? M k Nk ak (modm)
这里 m ? m1m2 ?mk , M i ?

m (1 ? i ? k ) ,以及 N j 满足 M j N j ? 1(modm j ) ,1 ? j ? k mi

(即 N j 为 M j 对模 m j 的逆) 。 中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解,而对于解的 形式并不重要。 定理 5: (拉格郎日定理)设 p 是质数, n 是非负整数,多项式 f ( x) ? an x n ? ? ? a1 x ? a0 是一个模 p 为 n 次的整系数多项式(即 p an ) ,则同余方程 f ( x) ? 0(mod p) 至多有 n 个 解(在模 p 有意义的情况下) 。 定理 6:若 l 为 a 对模 m 的阶, s 为某一正整数,满足 a s ? 1(modm) ,则 s 必为 l 的倍数。 以上介绍的只是一些系统的知识、方法,经常在解决数论问题中起着突破难点的作用。另外 还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用,有时也会起到

1(mod8) n为奇数时 0(mod9) 3整除n时 意想不到的作用,如: n 2 ? ? , n2 ? ? 。 ? ? 0 (mod 4 ) 0 (mod 3 ) n 为偶数时 3 不整除 n 时 ? ?

典例分析
1.设 (91, ab) ? 1,求证: 91| (a ? b ) 。
12 12

, a) ? 1 ,从而 (7, a) ? 1, (13, a) ? 1 ,但是 证明:因为 91 ? 7 ? 13 ,故由 (91, ab) ? 1 知 (91

? (7) ? 6,? (13) ? 12 ,故由欧拉定理得: a12 ? (a 6 ) 2 ? 12 ? 1(mod7) , a12 ? 1(mod13) ,
从而 a
12

? 1(mod91) ;同理, b12 ? 1(mod91) 。
12

于是, a

? b12 ? 1 ? 1 ? 0(mod91) ,即 91| (a12 ? b12 ) 。
n

注明:现考虑整数 a 的幂 a 所成的数列: a, a ,?, a ,?若有正整数 k 使 a ? 1(modm) ,
2 n k

则有 a ? a (modm) ,其中 n ? kq ? r ,0 ? r ? k ;
n r 2 n 2 k 2 k 因而关于 mod(m) , 数列 a, a ,?, a ,?的项依次同余于 a, a ,?, a , a, a ,?, a , a , ? 这

个数列相继的 k 项成一段,各段是完全相同的,因而是周期数列。如下例: 2.试求不大于 100,且使 11| (3 ? 7 ? 4) 成立的自然数 n 的和。
n n

3

初等代数选讲-----第四讲

解:通过逐次计算,可求出 3 关于 mod 11 的最小非负剩余(即为被 11 除所得的余数)为:

n

3 ? 3(mod11),32 ? 9(mod11),33 ? 5(mod11), 34 ? 5 ? 3 ? 4(mod11),35 ? 4 ? 3 ? 1(mod11)
因而通项为 3 的数列的项的最小非负剩余构成周期为 5 的周期数列: 3,9,5,4,1,3,9,5,4,1,??? 类似地,经过计算可得 7 的数列的项的最小非负剩余构成周期为 10 的周期数列: 7,5,2,3,10,4,6,9,8,1,??? 于是由上两式可知通项为 3 ? 7 ? 4 的数列的项的最小非负剩余,构成周期为 10(即上两
n n n n

式周期的最小公倍数)的周期数列: 3,7,0,0,4,0,8,7,5,6,??? 这就表明, 当 1 ? n ? 10 时, 当且仅当 n ? 3,4,6 时, 即 11| (3n ? 7 n ? 4) ; 3 ? 7 ? 4 ? 0(mod11) ,
n n

又由于数列的周期性,故当 10k ? 1 ? n ? 10(k ? 1) 时,满足要求的 n 只有三个,即

n ? 10k ? 3,10k ? 4,10k ? 6
从而当1 ? n ? 100 时,满足要求的 n 的和为:

? (10k ? 3) ? (10k ? 4) ? (10k ? 6) ? ?30k ? 13 ? 30? k ? 10?13 ? 30? 45 ? 130 ? 1480.
k ?0 k ?0 k ?0

9

9

9

下面我们着重对 Fetmat 小定理及其应用来举例:

1 5 1 3 7 x ? x ? x 是一个整数。 5 3 15 1 5 1 3 7 x ,则只需证 15 f ( x) ? 3x 5 ? 5x 3 ? 7 x 是 15 的倍数即可。 证明:令 f ( x) ? x ? x ? 5 3 15
3.求证:对于任意整数 x , 由 3,5 是素数及 Fetmat 小定理得 x ? x(mod5) , x ? x(mod3) ,则
5 3

3x5 ? 5x3 ? 7 x ? 3x ? 7 x ? 0(mod5) ; 3x5 ? 5x3 ? 7 x ? 2x ? x ? 0(mod3)
而(3,5)=1,故 3x ? 5x ? 7 x ? 0(mod15) ,即 15 f ( x) 是 15 的倍数。所以 f ( x) 是整数。
5 3

4.求证: 2730| n ? n ( n 为任意整数) 。
13

证明:令 f (n) ? n

13

? n ,则 f (n) ? n(n ?1)(n ? 1)(n 2 ? n ? 1)(n 2 ? n ? 1)(n6 ? 1) ;

7 5 3 2 所以 f ( n) 含有因式 n ? n, n ? n, n ? n, n ? n

由 Fetmat 小定理,知 13| n ? n, 7| n ? n,5 | n ? n,3 | n ? n,2 | n ? n
13 7 5 3 2

又 13,7,5,3,2 两两互素,所以 2730= 13 ? 7 ? 5 ? 3 ? 2 能整除 n
4

13

?n。

初等代数选讲-----第四讲

5.设 a, b, c 是直角三角形的三边长。如果 a, b, c 是整数,求证: abc 可以被 30 整除。 证明:不妨设 c 是直角三角形的斜边长,则 c ? a ? b 。
2 2 2

若2

a ,2 b ,2 c,则 c 2 ? a 2 ? b 2 ? 1 ? 1 ? 0(mod2) ,又因为 c 2 ? 1(mod2) 矛盾!

所以 2| abc . 若 3

a ,3

b ,3

c ,因为 (3k ? 1) 2 ? 1(mod3) ,则 a 2 ? b 2 ? 1 ? 1 ? 2(mod 3) ,又

c 2 ? 1(mod 3) ,矛盾!从而 3| abc .
若 5

a ,5 b ,5 c,因为 (5k ? 1) 2 ? 1(mod5) , (5k ? 2) 2 ? ?1(mod5) ,
2 2

所以 a ? b ? ?2 或 0(mod5)与 c 2 ? ?1(mod5) 矛盾! 从而 5| abc . 又(2,3,5)=1,所以 30| abc . 下面讲述中国剩余定理的应用 6.证明:对于任意给定的正整数 n ,均有连续 n 个正整数,其中每一个都有大于 1 的平方 因子。 证明:由于素数有无穷多个,故我们可以取 n 个互不相同的素数 p1 , p2 ,?, pn ,而考虑同余 组 x ? ?i(modp 2 ),i ? 1,2,?, n
2 2 2



因为 p1 , p2 ,?, pn 显然是两两互素的,故由中国剩余定理知,上述同余组有正整数解。 于是,连续 n 个数 x ? 1, x ? 2,?, x ? n 分别被平方数 p1 , p2 ,?, pn 整除。 注: (1)本题的解法体现了中国剩余定理的一个基本功效,它常常能将“找连续 n 个正整数 具有某种性质”的问题转化为“找 n 个两两互素的数具有某种性质” ,而后者往往是比较容 易解决的。 (2)本题若不直接使用素数,也中以采用下面的变异方法:由费尔马数
2 2 2

Fk ? 22 ? 1(k ? 0) 两两互素,故将①中的 pi2 转化为 Fi 2 (i ? 1,2,?, n) 后,相应的同余式也
有解,同样可以导出证明。 7.证明:对于任意给定的正整数 n ,均有连续 n 个正整数,其中每一个都不是幂数。 分析:我们来证明,存在连续 n 个正整数,其中每一个数都至少有一个素因子,在这个数的 标准分解中仅出现一次,从而这个数不是幂数。 证明:取 n 个互不相同的素数 p1 , p2 ,?, pn ,考虑同余组 x ? ?i(modp ),i ? 1,2,?, n
2

k

因为 p1 , p2 ,?, pn 显然是两两互素的,故由中国剩余定理知,上述同余组有正整数解。
2 对于 1 ? i ? n 因为 x ? i ? pi (modpi ) ,故 pi2 | ( x ? i) ,但由①式可知 pi2 ( x ? i) ,即 pi 在

2

2

2

5

初等代数选讲-----第四讲

( x ? i) 的标准分解中恰好出现一次,故 x ? 1, x ? 2,?, x ? n 都不是幂数。
8. 设 n, k 是给定的偶数, n ? 0 且 k (n ? 1) 是偶数。 证明:存在整数 x, y 使得 ( x, n) ? ( y, n) ? 1 ,且 x ? y ? k (modn) 。 证明:我们先证明,当 n 为素数幂 p ? 时结论成立。实际上,能够证明,存在 x, y 使

p xy 且 x ? y ? k :
若 p ? 2 ,则条件表明 k 为偶数,此时可取 x ? 1, y ? k ? 1 ; 若 p ? 2 ,则 x ? 1, y ? k ? 1 与 x ? 2, y ? k ? 2 中有一对满足要求。 一般情形下,设 n ? p1 1 p2 2 ? pr r , i ? 1,2, ,?, r 是 n 的一个标准分解,上面已经证明,对每
a a a

个 pi 存在整数 xi , yi 使得 pi xi yi 且 xi ? yi ? k (i ? 1,2,?r ) ,而由中国剩余定理, 同余式 x ? xi (modpi i )(i ? 1,2,?, r ) 同余式 y ? yi (modpi i )(i ? 1,2,?, r )
?

?

①有解 x , ②有解 y 。

现不难验证解 x, y 符合问题中的要求:因 pi xi yi ,故 pi xy (i ? 1,2,?r ) , 于是 ( xy, n) ? 1 ,又由①②知 x ? y ? xi ? yi (modpi i )(i ? 1,2,?, r ) , 故 x ? y ? k (modn) 。 注:此题的论证表现了中国剩余定理最为基本的作用:将一个关于任意正整数 n 的问题,化 为 n 为素数幂的问题,而后者往往是比较好处理的。
?

【练习】
n 1.设 p 是给定的素数,证明:数列 {2 ? n}(n ? 1) 中有无穷多项被 p 整除。

2.求证: f ( x) =

1 5 1 4 1 3 1 x ? x ? x ? x 为整值多项式。 5 2 3 30

3.数列:1,31,331,3331,???中有无穷多个合数。 4.设 n 为任意给定的正整数,证明:存在连续 n 个正整数,其中每一个都不是素数的幂。 5.设 m, n 为正整数,具有性质:等式 (11k ? 1, m) ? (11k ? 1, n) 对所有的正整数 k 成立。 证明: m ? 11 n ,其中 r 是某个整数。
r

6


推荐相关:

第四讲-几个定理

第四讲-几个定理_学科竞赛_高中教育_教育专区。高中竞赛初等数论选讲,共6讲初等代数选讲---第四讲 第四讲定义(欧拉(Euler)函数) 初等数论中的几个重要定理 ...


平面图形第四讲燕尾定理word版

平面图形第四讲燕尾定理word版_数学_小升初_小学教育_教育专区。小升初 名校 ...形,如图所示,三个三角形的面积 分 别是 3,7,7,则阴影四边形的面积是多少?...


第四讲 数字特征与极限定理文档

数字特征与极限定理文档数字特征与极限定理文档隐藏>> 第四讲 数字特征与极限定理...(1 人 1 券)到期到银行领取本息的概率为 0.4.问银行于 该日应准备多少...


第四讲 数字特征与极限定理文档

第四讲 数字特征与极限定理文档 概率论与数理统计概率论与数理统计隐藏>> 考试吧(Exam8.com)-第一个极力推崇人性化服务的综合考试网站! 声明:本资料由 考试吧(...


谢仲铖 第四讲 三角形与勾股定理

谢仲铖 第四讲 三角形与勾股定理_物理_自然科学_专业资料。三角形与勾股定理小巨人教育 少年强则中国强 谢仲铖 第四讲 三角形与勾股定理※课堂小问号 1、什么是...


第四讲-医学图像重建算法

第四讲-医学图像重建算法_临床医学_医药卫生_专业资料。一、断层成像的基本原理...图 2.3 二维成像的中心切片定理 如果探测器绕物体旋转至少 180°,物体的二维...


新高一分班考试.数学.第四讲.平面几何之三角形五星及圆幂定理

新高一分班考试.数学.第四讲.平面几何之三角形五星及圆幂定理_数学_高中教育_...几个特殊的巧合点. 一、重心定义:三角形的三条中线相交于一点(可由塞瓦定理...


高考物理复习讲坛之第四讲:牛顿运动定律的应用04

高考物理复习讲坛之第 高考物理复习讲坛之第四讲:...第二定律解题应特别注意研究对象的选取, 当几个物体...由动能定理有: 1 1 P '(t2 ? t '? t1 ) ...


第四讲 图形描绘 曲率

, 3 1 第三章 微分中值定理与导数的应用 第四讲 (2)将点 x ? ? ,,1 由小到大排列,依次把定义域( ? ?,?? )划分成下列 四个部分区间: ( ? ?,...


第四讲 约数与倍数

第​四​讲​ ​约​数​与​倍​数 暂无评价|0人阅读|0次...例 4、 、 〖方法总结〗 方法总结〗 这几个题目是【定理 1】和【定理 2】...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com