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

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


欧拉定理、费马小定理、孙子定理
1、设m ? 0,则模m有m个剩余类M i ? {i ? k m | 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 ? ( m) ? 1(mod m); (a

3、缩系的几种性质: (1)、模m的一组缩系含有? ( m)个数; (2)、若a1、a 2、 a m 是? ( m)个与m互质的整数,则a1、a 2、 a?(m) ? ? 是模m的一组缩系 的充要条件是a i ? a i (mod m), (i ? i ); (3)、若( a, m) ? 1, 且x是通过模m的缩系,则ax也是通过模m的缩系; 4、费马小定理:若p为素数,则a p ? a (mod p );
? ? ? 5、若n的标准分解为:n ? p1 1 p 2 2 ? p k k ,则:

? (n) ? n(1 ?

1 1 1 )(1 ? ) ? (1 ? ) p1 p2 pk

6、孙子定理:设m1、m 2、 m k 是k个两两互质的正整数,设m ? m1 m 2 ? m k , m ? mi M i , ? (i ? 1,2, ? , k ), M i ? m1 m 2 ? mi ?1 mi ?1 ? m k , 则同余方程组 x ? b1 (mod m1 ) x ? b2 (mod m 2 ) ?? x ? bk (mod m k )
' 有唯一解x ? M 1' M 1b1 ? M 2 M 2 b2 ? ? ? M k' M k bk (mod m)

其中M i' M i ? 1(mod mi ), i ? 1,2, ? , k

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

? ai ? ? i ?
i ?1 i ?1 n i ?1

n

n

n(n ? 1) n ? (mod n) 2 2 n (mod n) 2

同理有: ? bi ?
n

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

? ? (ai ? bi ) ? n(mod n) ? 0(mod n)
i ?1

又 ? 另一方面(ai ? bi )也是一组完全剩余系,则有:

? (a
i ?1

n

i

? bi ) ?

n (mod n) 2

?2 | n ? 0 ?

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

例2、证明:数列{2 n ? 3}中有一个无穷子数列,其中任意两项互素; 证明:设数列{2 n ? 3}中已有k项是两两互素的,记为u1 , u 2 , ?, u k , 作u k ?1 ? 2? (u1u2 ?uk ) ?1 ? 3 其中? ( x)是欧拉函数,由欧拉定理有:
? 2? ( u1u2 ?uk ) =2? ( u1)? ( u2) ? (uk ) ? 1(mod u i ),1 ? i ? k

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

? 2? (u1u2 ?uk ) ?1 ? 3 ? ?1(mod u i ),1 ? i ? k ? 数列u1 , u 2 , ?, u k 、u k ?1是k ? 1项两两互素的子数列,依此方法一直下去 数列{2 n ? 3}中一定有一个任意两项互素的无穷子数列 u i } {
例3、在1,2, ? p ? 中有多少个数是与p ? 互质,并求? ( p ? ), p为素数。 解 ? p为素数 ?问题即为:2, ? p ? 中有多少个数是与p互质,并求? ( p ? ) 1, 又 ? 在1,2, ? p ? 中是p的倍数有: p,2 ? p,3 ? p, ,p ? ?1 ? p 1? ? 其他的数均与p互质 ? ? ( p ? ) ? p ? ? p ? ?1 ? p ? (1 ? 1 ) p
选 自 《数 学 竞 赛 研究 教 程》上册 P154

共有p ? ?1个

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

1 n不可能成立; 4
选自 《世界数学奥林匹 克解题大辞典》 数论卷 P343

例4、证明当素数p ? 7时,p 4 ? 1能被240 整除; 证: 素数p ? 7,? p是奇数 ? 又 ? p 4 ? 1 ? ( p ? 1)( p ? 1)( p 2 ? 1) p 4 ? 1 ? ( p ? 1)( p ? 1)( p 2 ? 1)能被2 ? 2 ? 4= 整除 16 又 ? 费马小定理有:, p) ? 1, (5, p ) ? 1 (3 ?3 | p2 ?1 5 | p4 ?1 又 ?16, 5两两互素,则 ? 3 ? 5 | p 4 ? 1 3与 16 ? 240 | p 4 ? 1

且p ? 1, p ? 1, p 2 ? 1均为偶数,p ? 1和p ? 1是相邻的偶数,则:

【练习】证明: | n13 ? n, (n ? N ) 2730

2

例5、设m和n是自然数,满足:对任意自然数k, k ? 1与m和11k ? 1与n具有相同 11 的最大公约数,证明存在某个整数l,使m ? 11l n。 证:设m ? 11i p, n ? 11 j p, 其中i, j为非负整数,且11 | p,11 | q 为证明存在某个整数l,使m ? 11l n,只需证明p ? q 假设p ? q, ? ( p,11) ? 1,?由孙子定理有:存在正整数a, 使得:a ? 0(mod p ) a ? ?1(mod 11) ? a ? 11k ? 1, (k ? N ), 且11 | a 又 ? (11k ? 1, m) ? (a,11i p ) ? p (11k ? 1, n) ? (a,11 j q ) ? q ? p 另一方面: k ? 1, m)= (11k ? 1, n) (11 ? 产生矛盾,假设不成立, 同理p ? q也不成立 ? p=q 即:m ? 11i ? j n, l ? i ? j
选自 《世界数学奥林匹 克解题大辞典》 数论卷 P368

【练习】是否存在 1000000 个连续整数,使得每一个都含有二重的素因子,即能被 某个素数平方所整除。

3

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

1 n不可能成立; 4

1 n成立,则4 | n 4 ? ? ? 设n ? 2? p1 1 p 2 2 ? p k k , (? ? 2), p1 , p 2 , ? p k 为奇质数,则:

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

? ( n) ?

p ?1 p ?1 p ?1 1 ? ?1 ? 2 ? ? ? ? 2 p1 p 2 ? p k k ? 2? p1 1 p 2 2 ? p k k ( 1 )( 2 ) ? ( k ) 4 p1 p2 pk

? ? ? ? ? ? 即:? ? 2 p1 1 p 2 2 ? p k k ? 2? p1 1 ?1 p 2 2 ?1 ? p k k ?1 ( p1 ? 1)( p 2 ? 1) ? ( p k ? 1) 2

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

【练习】证明: | n13 ? n, (n ? N ) 2730 证明: 2730=2 ? 3 ? 5 ? 7 ? 13,若记f (n) ? n13 ? n, (n ? N ), 则由费马小定理, ? 可知13 | f (n), 由于n ? n ? n(n ? 1)( n ? 1)
13 6 6

? n(n 3 ? 1)( n 3 ? 1)( n 6 ? 1) ? n(n ? 1)( n ? 1)( n 2 ? n ? 1)( n 2 ? n ? 1)( n 6 ? 1) 由费马小定理可知:| f1 (n),5 | f 2 (n),3 | f 3 (n), 2 | f 4 (n) 7 即2,5,13均整除f (n), 且2,5,13两两互素,故2730 | f (n) 3, 7, 3, 7,

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

故f1 (n) ? n 7 ? n, f 2 (n) ? n 5 ? n, f 3 (n) ? n 3 ? n, f 4 (n) ? n 2 ? n, 都是f (n)的因式

【练习】是否存在 1000000 个连续整数,使得每一个都含有二重的素因子,即能被 某个素数平方所整除。 证明:令p1 , p 2 , ? p s 是s个相异的素数,由孙子定理,下列同余式组 x ? ?1(mod p12 )
2 x ? ?2(mod p 2 )

?? x ? ? s (mod p s2 ) 存在一解,设此解为n

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

则s个连续整数n ? 1, n ? 2, ? , n ? s每个都有一个二重素因子,即有p i2 | n ? i 取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 ],费马小定理,格点及其性质,无穷递降法, 欧拉定理 ?...,孙子定理 ? . 根据已出现的试题统计,中学数学竞赛中的数论问题的主要有 8 ...
数学竞赛
几个重要定理:梅涅劳斯定理、塞瓦定理、托勒密定理、西姆松定理。 几个重要的极值...非负最小完全剩余类,高斯函数[x],费马小定理,欧拉函数*,孙子定理*, 格点...
中国剩余定理 威尔逊定理 费马小定理 欧拉定理
之前求得 x=12,所以 y=20) 孙子定理 定义中国古代求解一次同余式组(见同余...2页 免费 竞赛专题--欧拉定理、费... 5页 免费喜欢此文档的还喜欢 ...
更多相关标签:
费马小定理 | 费马小定理证明 | 费马小定理求逆元 | 费马小定理的应用 | 费马小定理的证明 | 费马小定理应用 | 费马小定理 逆元 | 费马小定理 c |