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

PAGE

PAGE1

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

1、设m?0，则模m有m个剩余类M

i

?{i?km|k?Z},i?0,1,2,?,m?1

如果i与m互质，那么M中每一个数均与m互质，这样的同余类共有?(m)个,

i

?(m)是1，2，?，m中与m互质的个数，称为欧拉函数；

2、欧拉定理：设m?1，(a,m)?1,则a?(m)?1(modm);

3、缩系的几种性质：

、模m的一组缩系含有?(m)个数；

、若a、a、?a是?(m)个与m互质的整数，则a、a、?a? 是模m的一组缩系

1 2 m 1 2 （m）

的充要条件是a ?a(modm),(i?i);

i i

、若(a,m)?1,且x是通过模m的缩系，则ax也是通过模m的缩系；

4、费马小定理：若p为素数，则ap?a(modp);

15、若n的标准分解为：n?p?p?2?p?k，则：

1

1 2 k

?(n)?n(1?1

p

1

)(1?

1) (1? 1)

?p p

?

?2 k

?

?6、孙子定理：设m、m、m

?

1 2 k

是k个两两互质的正整数，设m?mm m

1 2 k

,m?mM,

i i

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

?

i

?mm

1 2

?mi?1

m m

?i?1 k

?

,则同余方程组

x?b

1

x?b

(modm)

1

(modm)

2 2

??

x?b(modm)

k k

有唯一解x?MMb

1 11

MMb

2 22

?MMb

?k k k

?

(modm)

其中MM

i i

?1(modm

i

),i?1,2,?,k

例1、设a、a

、?a

和b、b

、?b

分别是n的一组完全剩余系，且2|n，

求证：a

1 2

b、a

n 1 2

b、?a ?b

n

不是n的一组完全剩余系。

?1 1 2 2 n n

?

?证：a、a

?

1

、a是n的一组完全剩余系，则：

2 n

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

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

??n

n(n?1)

i? ?

n(modn)

i

i?1 i?1

同理有：?nb

i

i?1

2 2

?n(modn)2

??n(a

i

i?1

b)?n(modn)?0(modn)

i

?又 另一方面(a

?

i

b)也是一组完全剩余系，则有：

i

?n(a

i

i?1

?b)?

i

n(modn)2

?2|n?0?n?n,?上式不成立，?原命题成立；

?

2

例2、证明：数列{2n?3}中有一个无穷子数列，其中任意两项互素；

证明：设数列{2n?3}中已有k项是两两互素的，记为u,u

1 2

, ,u,

?k

?

作u ?2?(uu?u)?1?3

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

选自《奥林匹克数学》高

三分册P

63

12 k

其中?(x)是欧拉函数，由欧拉定理有：

2?(uu?u

)＝2?(u）?(u）??(u)

?1(modu

),1?i?k

12 k

1 2 k

i

12?2?(uu?u

1

2

k

)?1?3??1(modu),1?i?k

i

?数列u,u

1 2

,?,u

、u 是k?1项两两互素的子数列，依此方法一直下去

k k?1

数列{2n?3}中一定有一个任意两项互素的无穷子数列{u}

选自《数学竞赛研究教

选自《数学

竞赛研究教

程》上册P

154

例3、在1,2,?p?中有多少个数是与p?互质，并求?(p?),p为素数。解?p为素数

?问题即为：1,2,?p?中有多少个数是与p互质，并求?(p?)又?在1,2,?p?中是p的倍数有：1?p，2?p，3?p，?，p??1?p其他的数均与p互质

共有p??1个

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

p

【练习】证明：?(4)?1n不可能成立；

4

选自《世界数学奥林匹克解题大辞典》数论卷P343例4、证明当素数p?7时，p4?1能被240整除；证：?素数p?7,?

选自《世界数学奥林匹

克解题大辞典》数论卷

P

343

又?p4?1?(p?1)(p