当前位置:首页 >> 学科竞赛 >>

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


第五节
基础知识

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

定义(欧拉 (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) 。

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

定理 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 必有解,且解可以写为:

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(mod4) n为偶数时 ?0(mod3) 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 关于 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

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

( 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


相关文章:
第五节初等数论中的几个重要定理
第五节初等数论中的几个重要定理_学科竞赛_高中教育_教育专区。第五节基础知识 初等数论中的几个重要定理 定义(欧拉 (Euler)函数)一组数 x1 , x2 ,?, xs ...
第五节初等数论中的几个重要定理
第五节基础知识 初等数论中的几个重要定理 定义(欧拉(Euler)函数)一组数 x1 , x 2 ,L , x s 称为是模 m 的既约剩余系,如果对任意的 定义 1 ≤ j ...
第五节初等数论中的几个重要定理
数论数论隐藏>> 第五节基础知识 初等数论中的几个重要定理 定义(欧拉(Euler)函数)一组数 x1 , x 2 ,L , x s 称为是模 m 的既约剩余系,如果对任意的...
初等数论中的几个重要定理
初等数论中的几个重要定理 基础知识 定义(欧拉(Euler)函数)一组数 的模, 的剩余, 即 且对于任意的 。 并定义 称为是模 ,若 的既约剩余系,如果对任意 是...
初等数论中的几个重要定理
初​等​数​论​中​的​几​个​重​要​定​理初等数论中的几个重要定理 基础知识 定义 (欧拉(Euler)函数) 一组数 且对于任意的 。并...
初等数论中的几个重要定理
初等数论中的几个重要定理 6页 2财富值 第五节初等数论中的几个重... 13页...初等数论中的几个重要定理基础知识 定义(欧拉(Euler)函数)一组数 定义 意的 ...
初等数论中的几个重要定理(竞赛必备)
初等数论中的几个重要定理 基础知识 定义(欧拉(Euler)函数)一组数 的, 的...第五节初等数论中的几个... 13页 5下载券 (精品)初等数论中的几个... ...
初等数论中的几个重要定理
第五节初等数论中的几个重... 6页 2财富值 (精品)初等数论中的几个重.....初等数论中的几个重要定理初等数论中的几个重要定理隐藏>> 初等数论中的几个重要...
初等数论中的几个重要定理
初等数论中的几个重要定理 6页 2财富值 第五节初等数论中的几个重... 13页...有关初等数论中的几个定理,费马小定理,剩余定理等等。有关初等数论中的几个定理...
初等数论练习题答案
事实,由?(8)=4,?(3)=2,?(5)=4 以及欧拉定理立得结论。 初等数论练习题三一、单项选择题 1、若 n>1,?(n)=n-1 是 n 为质数的( A.必要但非...
更多相关标签:
初等数论四大定理 | 初等数论 之孙子定理 | 初等数论 | 初等数论 pdf | 初等数论第三版答案 | 初等数论 潘承洞 | 初等数论及其应用 | 初等数论难题集 |