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

竞赛专题--欧拉定理、费马小定理、孙子定理


欧拉定理、费马小定理、孙子定理

1、设 m ? 0,则模 m 有 m 个剩余类 M i ? {i ? km | k ? Z }, i ? 0 ,1, 2 , ? , m ? 1 如果 i 与 m 互质,那么 M i中每一个数均与 m 互质,这样的同余类共 函数; 有 ? ( m )个 ,

? ( m ) 是 1,, , m 中与 m 互

质的个数,称为欧拉 2 ?
2、欧拉定理:设 m ? 1, , m ) ? 1, 则 a (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 ); ( 3 )、若 ( a , m ) ? 1, 且 x 是通过模 m 的缩系,则 4、费马小定理:若 p 为素数,则
? ?

ax 也是通过模

m 的缩系;

a

p

? a (mod p );
?

5、若 n 的标准分解为:

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

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

1 p1

)(1 ?

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 ? b1 (mod m 1 ) x ? b 2 (mod m 2 ) ?? x ? b k (mod m k ) 有唯一解 x ? M 1 M 1 b1 ? M 2 M 2 b 2 ? ? ? M k M k b k (mod m )
' ' '

其中 M i M

'

i

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

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

?a
i ?1

n

i

?

?i?
i ?1

n

?

n 2

(mod n )

同理有: ?

?b
i ?1

n

?

n 2

(mod n )

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

? (a
i ?1

n

i

? b i ) ? n (mod n ) ? 0 (mod n ) 则有:

又 ? 另一方面 ( a i ? b i ) 也是一组完全剩余系,

? (a
i ?1

n

i

? bi ) ? n 2

n 2

(mod n )

?2|n? 0?

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

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

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

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

{ 2 ? 3}中已有 k 项是两两互素的,记为
? ( u 1u 2 ? u k ) ? 1

?3 理有:

其中 ? ( 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 ? 3}中一定有一个任意两项
n

互素的无穷子数列

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

?

p 互质,并求

?

? ( p ), p 为素数。 ?(p )
? ?1 ?

?

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

p 互质,并求

选 自 《数 学 竞 赛 研究 教 程》上册 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 不可能成立;

例 4、证明当素数

p ? 7时, p

4

? 1能被 240 整除;

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

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

2

? 1)

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

且 p ? 1, p ? 1, p p
4

? 1均为偶数,
2

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

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

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

又 ? 费马小定理有: ( 3 , p ) ? 1, ( 5 , p ) ? 1 ?3| p
2

?1

5| p

4

?1
4

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

16 ? 3 ? 5 | p
4

?1

? 240 | p

?1

【练习】证明: 2730 | n

13

? n, (n ? N )

2

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

意自然数 k , k ? 1与 m 和 11 k ? 1与 n 具有相同 11 l ,使 m ? 11 n 。
l

在某个整数

证:设 m ? 11 p , n ? 11 p , 其中 i , j 为非负整数,且 为证明存在某个整数 假设 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

11 | p ,11 | q p ? q

l ,使 m ? 11 n ,只需证明
l

整数 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 个连续整数,使得每一

个都含有二重的素因子

,即能被

某个素数平方所整除。

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

? (4) ?
1 4
?

1 4

n 不可能成立;

n 成立,则 4 | n
?

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

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

? (n) ?
即: 2
? ?2

1 4

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

?

?

?

?

?

?

?

?

p1 ? 1 p1

)(

p2 ? 1 p2

)? (

pk ? 1 pk

)

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

p2 2

? ?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 不可能成立 左边是一个奇数, ? 上式不成立, ? 假设不成立

3

【练习】证明: 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 ? 1)( n ? 1)
6 6

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

? n ( n ? 1)( n ? 1)( n ? n ? 1)( n ? n ? 1)( n ? 1)
2 2 6 7 5 3 2

选 自 《中 国 华 罗 庚学 校 数 学 课本 》 P218

故 f 1 ( n ) ? n ? n , f 2 ( n ) ? n ? n , f 3 ( n ) ? n ? n , f 4 ( n ) ? n ? n , 都是 f ( 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

【练习】是否存在

1000000 个连续整数,使得每一

个都含有二重的素因子

,即能被

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

定理,下列同余式组

x ? ? 2 (mod p 2 )
2

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

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

则 s 个连续整数

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

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

的 1000000 个连续整数;

4


相关文章:
竞赛专题--欧拉定理、费马小定理、孙子定理
竞赛专题--欧拉定理费马小定理孙子定理_学科竞赛_高中教育_教育专区。欧拉定理费马小定理孙子定理 1、设m ? 0,则模m有m个剩余类M i ? {i ? k m...
竞赛专题--欧拉定理、费马小定理、孙子定理
竞赛专题--欧拉定理费马小定理孙子定理 隐藏>> 欧拉定理费马小定理孙子定理 1、设 m ? 0,则模 m 有 m 个剩余类 M i ? {i ? km | k ? Z...
竞赛专题--欧拉定理、费马小定理、孙子定理
竞赛专题--欧拉定理费马小定理孙子定理_理学_高等教育_教育专区。高中,数学,竞赛,专题,解析欧拉定理费马小定理欧拉定理费马小定理孙子定理 1、设m ...
2013高中数学奥数培训资料之欧拉定理、费马小定理、孙子定理
2013高中数学奥数培训资料之欧拉定理费马小定理孙子定理_学科竞赛_高中教育_教育专区。2012年最新高中奥数辅导资料专题,数学联赛获奖不是梦,报送大学不再是幻想兰州...
个人精心整理!高中数学联赛竞赛平面几何四大定理~及考纲
个人精心整理!高中数学联赛竞赛平面几何四大定理~及考纲_学科竞赛_高中教育_教育专区...非负最小完全剩余类,高斯函数,费马小定理,欧拉函数,孙子定理,格点及 其性质...
竞赛考纲
高中数学联赛考纲 一试全国高中数学联赛的一试竞赛大纲,完全按照全日制中学《数学...非负最小完全剩余类,高斯函数,费马小定理,欧拉函数,孙子定理,格 点及其性质。...
数学竞赛
数学竞赛_学科竞赛_初中教育_教育专区。考试范围 一试 全国高中数学联赛的一试竞赛...非负最小完全剩余类,高斯函数,费马小定理,欧拉函数,孙子定理,格点 及其性质。...
数学竞赛
几个重要定理:梅涅劳斯定理、塞瓦定理、托勒密定理、西姆松定理。 几个重要的极值...非负最小完全剩余类,高斯函数[x],费马小定理,欧拉函数*,孙子定理*, 格点...
中国剩余定理 威尔逊定理 费马小定理 欧拉定理
之前求得 x=12,所以 y=20) 孙子定理 定义中国古代求解一次同余式组(见同余...2页 免费 竞赛专题--欧拉定理、费... 5页 免费喜欢此文档的还喜欢 ...
奥林匹克竞赛
几个重要定理:梅涅劳斯定理、塞瓦定理、托勒密定理、西姆松 定理。 几个重要的...非负最小完全剩余类,高斯函数 [x],费马小定理,欧拉函数*,孙子定理*,格点...
更多相关标签:
费马小定理 | 费马小定理证明 | 费马小定理求逆元 | 费马小定理的应用 | 费马小定理的证明 | 费马小定理应用 | 费马小定理 逆元 | 费马小定理 判断素数 |