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

2013高中数学奥数培训资料之欧拉定理、费马小定理、孙子定理


兰州成功私立中学高中奥数辅导资料 (内部资料)
欧拉定理、费马小定理、孙子定理
1、设 m ? 0,则模 m 有 m 个剩余类 如果 i 与 m 互质,那么 M
i

? { i ? km | k ? Z }, i ? 0 ,1, 2 , ? , m ? 1 m 互质,这样的同余类共 函数; 有 ? ( m )个 ,
<

br />M i 中每一个数均与

? ( m ) 是 1,, , m 中与 m 互质的个数,称为欧拉 2 ?
2、欧拉定理:设 m ? 1,a , m ) ? 1, 则 a (
? (m )

? 1(mod m );

3、缩系的几种性质: (1 )、模 m 的一组缩系含有

? ( m ) 个数;
a 1、 a 2 、 a ? ( m )是模 m 的一组缩系 ?

( 2 )、若 a 1、 a 2 、 a m 是 ? ( m ) 个与 m 互质的整数,则 ? 的充要条件是 a i ? a i (mod m ), ( i ? i ); m 的缩系,则 a
?2
p

( 3 )、若 ( a , m ) ? 1, 且 x 是通过模 4 、费马小定理:若 5、若 n 的标准分解为: p 为素数,则
?1

ax 也是通过模

m 的缩系;

? a (mod p );
?

n ? p 1 p 2 ? p k k ,则: )( 1 ? 1 p2 ) ? (1 ? 1 pk 设 m ? m1m 2 ? m k , m ? m i M i , )

? ( n ) ? n (1 ?
6 、孙子定理:设

1 p1

m 1、 m 2 、 m k 是 k 个两两互质的正整数, ?
i

( i ? 1, 2 , ? , k ), M

? m 1 m 2 ? m i ? 1 m i ? 1 ? m k , 则同余方程组

x ? b 1 (mod m 1 ) x ? b 2 (mod m 2 ) ?? x ? b k (mod m k ) 有唯一解 其中 M i M
'

x ? M 1 M 1 b 1 ? M 2 M 2 b 2 ? ? ? M k M k b k (mod m )
' ' ' i

? 1 (mod m i ), i ? 1, 2 , ? , k

选自《奥林匹 克数学》高三 分册 P61

1

例 1、设 a 1、 a 2 、 a n 和 b 1、 b 2 、 b n 分别是 n 的一组完全剩余系,且 ? ? 求证: a 1 ? b 1、 a 2 ? b 2 、 a n ? b n 不是 n 的一组完全剩余系。 ? 证: a 1、 a 2 、 a n 是 n 的一组完全剩余系,则 ? ? :

2 | n,

?
i ?1

n

ai ?

?i?
i ?1

n

n ( n ? 1) 2
i

?

n 2

(mod n )

同理有:

?b
i ?1

n

?

n 2

(mod n )

?

? (a
i ?1 n

n

i

? b i ) ? n (mod n ) ? 0 (mod n ) ( a i ? b i ) 也是一组完全剩余系, n 2 (mod n ) 则有:

又 ? 另一方面

? (a
i ?1

i

? bi ) ? n 2

? 2|n ? 0 ?

? n ,? 上式不成立, ? 原命题成立;
n

例 2 、证明:数列 证明:设数列 作 u k ?1 ? 2
? ( u 1u 2 ? u k )

{2
n

? 3}中有一个无穷子数列,

其中任意两项互素; u1 , u 2 ,? , u k ,

{2

? 3}中已有 k 项是两两互素的,记为 ?3 理有:

? ( u 1u 2 ? u k ) ? 1

其中 ? ( x ) 是欧拉函数,由欧拉定 2 =2
? ( u 1) ? ( u 2) ? ( u k ) ?

? 1 (mod u i ), 1 ? i ? k

选自 《奥林匹克数学》 高 三分册 P63

?2

? ( u 1u 2 ? u k ) ? 1

? 3 ? ? 1 (mod u i ), 1 ? i ? k 依此方法一直下去 {u i }
?

? 数列 u 1 , u 2 , ? , u k 、 u k ? 1 是 k ? 1项两两互素的子数列, 数列 { 2
n

? 3}中一定有一个任意两项
? ?

互素的无穷子数列

例 3、在 1, 2 , ? p 中有多少个数是与 解 ? p 为素数

p 互质,并求

? ( p ), p 为素数。
?

? 问题即为: 1, 2 , ? p 中有多少个数是与
?

?

p 互质,并求

?(p )
? ?1

选 自 《数 学 竞 赛 研究 教 程》上册 P154
共有 p
? ?1

又 ? 在 1, 2 , ? p 中是 p 的倍数有: 1 ? p , 2 ? p , 3 ? p , , p ? 其他的数均与 ??(p ) ? p
? ?

? p



p 互质 ? p
? ?1

? p (1 ?
1 4

?

1 p

)

【练习】证明:

? (4) ?

n 不可能成立;

2

例 4 、证明当素数

p ? 7 时, p

4

? 1能被 240 整除;

证: 素数 p ? 7 , ? p 是奇数 ? 又 ? p 且 p ? 1, p
4 4

选自 《世界数学奥林匹 克解题大辞典》 数论卷 P343

? 1 ? ( p ? 1 )( p ? 1 )( p p ? 1, p
2

2

? 1) p ? 1和 p ? 1是相邻的偶数,则:

? 1均为偶数,
2

? 1 ? ( p ? 1 )( p ? 1 )( p

? 1 )能被 2 ? 2 ? 4= 16 整除

又 ? 费马小定理有:

( 3 , p ) ? 1, ( 5 , p ) ? 1
2

?3| p

?1

5| p

4

?1
4

又 ? 16 ,与 5 两两互素,则 3

16 ? 3 ? 5 | p
4

?1

? 240 | p

?1

【练习】证明:

2730 | n

13

? n, (n ? N )

例 5、设 m 和 n 是自然数,满足:对任 的最大公约数,证明存 证:设 m ? 11 p , n ? 11
i j

意自然数

k , k ? 1与 m 和 11 k ? 1与 n 具有相同 11
l

在某个整数

l ,使 m ? 11 n 。 11 | p ,11 | q p ? q

p , 其中 i , j 为非负整数,且 l ,使 m ? 11 n ,只需证明
l

为证明存在某个整数 假设 p ? q ,

? ( p ,11 ) ? 1,? 由孙子定理有:存在正 使得: a ? 0 (mod p ) a ? ? 1 (mod 11 ) ? a ? 11 k ? 1, ( k ? N ), 且 11 | a 又 ? (11 k ? 1, m ) ? ( a ,11 p ) ? p
i

整数 a ,

(11 k ? 1, n ) ? ( a ,11 q ) ? q ? p
j

选自 《世界数学奥林匹 克解题大辞典》 数论卷 P368

另一方面: (11 k ? 1, m )= (11 k ? 1, n ) ? 产生矛盾,假设不成立 同理 p ? q 也不成立 ? p= q 即: m ? 11
i? j



n, l ? i ? j

【练习】是否存在

1000000 个连续整数,使得每一

个都含有二重的素因子

,即能被

某个素数平方所整除。

3

【练习】证明: 证:若 ? ( 4 ) ? 设n ? 2
? ?

? (4) ?
1 4
?

1 4

n 不可能成立; 4|n

n 成立,则
?

选 自 《数 学 竞 赛 研究 教 程》上册 P155

p 1 1 p 2 2 ? p k k , (? ? 2 ), p 1 , p 2 , ? p k 为奇质数,则: 2
? ?

? (n) ?
即: 2
? ?2

1 4

p1 1 p 2 2 ? p k k ? 2
? ? ?

?

?

?

?

p1 1 p 2 2 ? p k k ( p2 2
? ?1

?

?

?

p1 ? 1 p1

)(

p2 ? 1 p2

)? (

pk ? 1 pk

)

p1 1 p 2 2 ? p k k ? 2

p1 1

? ?1

? pk k

? ?1

( p 1 ? 1 )( p 2 ? 1 ) ? ( p k ? 1 )

即: p 1 p 2 ? p k ? 4 ( p 1 ? 1 )( p 2 ? 1 ) ? ( p k ? 1 ) 又 ? 上式右边是一个偶数, ? ? (4) ? 1 4 n 不可能成立 左边是一个奇数, ? 上式不成立, ? 假设不成立

【练习】证明:

2730 | n

13

? n, (n ? N )
13

证明: ? 2730 = 2 ? 3 ? 5 ? 7 ? 13 ,若记 f ( n ) ? n 可知 13 | f ( n ), 由于 n
13

? n , ( n ? N ), 则由费马小定理,

? n ? n(n

6

? 1 )( n

6

? 1)
6

? n ( n ? 1 )( n ? 1 )( n
3 3

? 1)
2

? n ( n ? 1 )( n ? 1 )( n 故 f1 (n ) ? n
7

2

? n ? 1 )( n

? n ? 1 )( n
3

6

? 1)
2

选 自 《中 国 华 罗 庚学 校 数 学 课本 》 P218
? n , 都是 f ( n )的因式

? n, f 2 (n) ? n

5

? n, f 3 (n) ? n ? n, f 4 (n) ? n

由费马小定理可知:

7 | f 1 ( n ), 5 | f 2 ( n ), 3 | f 3 ( n ), 2 | f 4 ( n ) 2730 | f ( n )

即 2,,,, 均整除 f ( n ), 且 2,,,, 两两互素,故 3 5 7 13 3 5 7 13

4

【练习】是否存在

1000000 个连续整数,使得每一

个都含有二重的素因子

,即能被

某个素数平方所整除。 证明:令 p 1 , p 2 , ? p s 是 s 个相异的素数,由孙子
2

定理,下列同余式组

x ? ? 1 (mod p 1 ) x ? ? 2 (mod p 2 )
2

?? x ? ? s (mod p s )
2

选自 《世界数学奥林匹 克解题大辞典》 数论卷 P360
存在一解,设此解为 n 子,即有 pi | n ? i
2

则 s 个连续整数

n ? 1, n ? 2 , ? , n ? s 每个都有一个二重素因

取 s ? 1000000 , 则可得到满足条件要求

的 1000000 个连续整数;

5


相关文章:
2013高中数学奥数培训资料之欧拉定理、费马小定理、孙子定理
2013高中数学奥数培训资料之欧拉定理费马小定理孙子定理_学科竞赛_高中教育_教育专区。2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦,报送大学不再是幻想兰州...
竞赛专题--欧拉定理、费马小定理、孙子定理
竞赛专题--欧拉定理费马小定理孙子定理_学科竞赛_高中教育_教育专区。欧拉...2013高中数学奥数培训资... 5页 免费 费马定理欧拉定理、威... 暂无评价 ...
竞赛专题--欧拉定理、费马小定理、孙子定理
2013高中数学奥数培训资料... 5页 免费 费马小定理欧拉定理的应... 5页 ...( n ) ? n (1 ? 6、孙子定理:设 1 p1 )(1 ? m 1、 m 2 、 m...
竞赛专题--欧拉定理、费马小定理、孙子定理
竞赛专题--欧拉定理费马小定理孙子定理_理学_高等教育_教育专区。高中,数学...费马小定理 10页 免费 2013高中数学奥数培训资... 5页 免费 Fermat-Euler定理...
数学奥赛
2011高中数学竞赛培训教材 43页 免费 各种圆定理总结(包括托勒密... 19页 免费...非负最小完全剩余类,高斯函数,费马小定理,欧拉函数,孙子定理,格点及其性 质。...
全国高中数学联赛讲义
全国高中数学联赛试题新规则和考试范围 ──高中数学竞赛大纲(修订稿)在“普及的...非负最小完全剩余类,高斯函数,费马小定理,欧拉函数,孙子定理,格点及 其性质。...
个人精心整理!高中数学联赛竞赛平面几何四大定理~及考纲
非负最小完全剩余类,高斯函数,费马小定理,欧拉函数,孙子定理,格点及 其性质。...2013高中数学奥数培训资... 7页 免费 2013高中数学奥数培训资... 8页 免费 ...
费马定理、欧拉定理、威尔逊定理(讲稿)
?a(mod p), 由孙子定理这样的 n 是存在的,如 n=(a+1)(p-1)+1. 由...2013高中数学奥数培训资... 5页 免费 欧拉定理 3页 2下载券 欧拉与“费马...
数学奥赛辅导_第三讲_同_余
关键词:高中数学竞赛辅导 同系列文档 数学奥赛辅导_...(2)中国剩余定理(即孙子定理) 设 n ? 2 , m ...现在由费马小定理 2 q ?1 ? 1(mod q ) 推出...
更多相关标签:
费马小定理 | 费马小定理证明 | 费马小定理求逆元 | 费马小定理的应用 | 费马小定理的证明 | 费马小定理应用 | 费马小定理 逆元 | 费马小定理 判断素数 |