初等数论论文

的理论体系，理解数学思想方法的内涵，开阔思维视野，健全认知结构.

为了使用方便,我们将数论中的一些概念和结论摘录如下:

我们用(a1,a2,...,an)表示整数a1,a2,?,an的最大公约数.用[a1,a2,?,an]表示

a1,a2,?,an的

最小公倍数.对于实数x,用[x]表示不超过x的最大整数,用{x}=x-[x]表示x的小数部分.对于整数a,b,若m|(a?b),m?1,则称a,b关于模m同余,记为a?b(modm).对于正整数m,用?(m)表示{1,2,?,m}中与m互质的整数的个数,并称?(m)为欧拉函数.对于正整数m,若整数r1,r2,...,rm中任何两个数对模m均不同余,则称{r1,r2,...,rm}为模m的一个完全剩余系；若整数r1,r2,...,r?(m)中每一个数都与m互质,且其中任何两个数关于模m不同余,则称{r1,r2,...,r?(m)}为模m的简化剩余系.

定理1 设a,b的最大公约数为d,则存在整数x,y,使得d?xa?yb. 定理

nii1n2(1)若ai?bi(modm),i?1,2,?,n,x1?x2(modm),则

i2?ax??bxi；

i?1i?1abm?(mod)； dddab(3)若a?b,d?(a,b),且(d,m)?1,则?(modm)；

dd(2)若a?b(modm),d?(a,b),d|m,则

(4)若a?b(modmi),i?1,2,...,n,M=[m1,m2,...,mn],则a?b(modM). 定理3(1)x?1?[x]?x?[x]?1； (2)[x?y]?[x]?[y]；

(3)设p为素数,则在n!质因数分解中,p的指数为

?k?1n. kp定理4 (1)若{r1,r2,...,rm}是模m的完全剩余系,(a,m)?1,则{ar1?b,ar2?b,...,arm?b}也是模m的完全剩余系；

(2)若{r1,r2,...,r?(m)}是模m的简化剩余系,(a,m)?1,则{ar1,ar2...,ar?(m)}是模m的简化剩余系.

定理5(1)若(m,n)?1,则?(mn)??(m)?(n).

?2...pkk,其中?1,?2,.?..k为正整(2)若n的标准分解式为n?p11p2??数,p1,p2,...pk为互不相同的素数,则?(n)?n(1?111)(1?)...(1?). p1p2pk对于以上结论的证明,有兴趣的读者可查阅初等数论教材.

例1 设正整数a,b,c的最大公约数为1,并且全平方数.

证:设(a,b)?d,a?a1d,b?b1d,其中(a1,b1)?1.由于(a,b,c)?1,故有

ab?c (1),证明:(a?b)是一个完a?b(d,c)?1.由(1)得

a1b1d?a1c?b1c (2)

由(2)知,a1|b1c,又(a1,b1)?1,∴ a1|c.同理可证b1|c,从而有a1b1|c,设

c?a1b1k(3)

,

k为正整数,代入(2)得

d?k(a1?b1)

由(3)知k|d,又k|c,?k|(d,c)?1,?k?1. ∴d?a1?b1.∴

a?b?d(a1?b1)?d2.故成立.

例2 设n为大于1的奇数,k1,k2,?,kn为给定的整数.对于{1,2,...,n}的排列

P?(a1,a2,...,an),

记s(P)??ka,试证存在{1,2,...,n}的两个不同的排列B、C,使得n!|s(B)?s(C).

iii?1n证:假设对于任意两个不同的排列B、C,均有n!不整除s(B)?S(C).令X为{1,2,...,n}的所有排列构

成的集合,则{s(P)|P?X}为模n!的一个完全剩余系,从而有

P?X?s(P)??i??1in!(1?nn!)!(mno (1) d!)2 又(2)

?P?X?s(P)??(?ka)iiP?Xi?1n=

n!(n?1)nki ?2i?1(1?n!)n!n!(n?1)n而n为大于1的奇数,所以由(1),(2)得?ki?0(modn!). ?22i?1又(1?n!,n!)?1,所以

n!?0(modn!),矛盾.故,存在B、C?X,B?C,使得2n!|s(B)?s(C).

例3求三个素数,使得它们的积为和的5倍.

解:易知a,b,c中必有一个为5,不妨设c?5,则有ab?a?b?5,从而有

(a?1)(b?1)?6.

因为a?1与b?1均为正整数,不妨设a?b,则有??a?1?1?a?1?2或?,从而知

b?1?6b?1?3??a?2,b?7.故所求的三个素数为2,5,7.

例4 设k为正奇数,证明:1?2?3?...?n整除1?2?...?n. 分析 因为1?2?3?...?n?kkkkkn(n?1)kkk.故需证n(n?1)|2(1?2?...?n),注意到2kkk当k为奇数时,x?y可因式分解,因此可将2(1?2?...?n)中的2n个数两两配对. 证

?2(1k?2k?...?nk)=[1k?(n?1)k]?[2k?(n?2)k]?...?[(n?1)k?1k]?2nk,

而当(1)

又?21?2?...?n ∴(2)

由(1)(2)知,n(n?1)|2(1?2?...?n),故结论成立.

例5 (1990年高中联赛试题)设E?{1,2,...,200},G?{a1,a2,...,a100}?E,且G具有下列性质:

kkkk为奇数时,

a?b|ak?bk,从而知n|21k?2k?...?nk

???kkk?=[1k?nk]?[2k?(n?1)k]?...?[nk?1k],

(n?1)|2(1k?2k?...?nk)

(1)对任何1?i?j?100,ai?aj?201；(2)

?ai?1100i?10080.

试证:G中的奇数的个数是4的倍数,且G中所有数的平方和是一定数.

证:对于1?i?100,令?i?2i?1,?i?201??i.Ei?{?i,?i},则G中恰含Ei中的一

,js,这里个元素.设G中有k个奇数?i1,?i2,?,?ik,有s个偶数?j1,?j2,...?{i1,i2,...ik,,j1,j2,...j,s}知

,10080=

=

sk{1,2,...,100}s.由

k题

k设

??t?1kit???jr??(201??it)???jrr?1t?1r?1=

?201?2??t?1t?1it+

s?k????it???jr?

r?1?t?1? =201k?2

??t?1kit+(2?4?6?...?200)=201k?2??t?1kit?10100.

∴201k?2??t?1kit??20 (1)

k由于?it为偶数,所以4|2100i?1ks??t?1it,又4|20,所以4|201k,?4|k,即k是4的倍数.

kskk?ak2it2i??????t?12itr?12jr=

?(201??t?1it)???2r?12jr=

?201t?12?2?201??it+

t?1(?????j2r)

t?1r?12s=201k?2?201k??t?1tkit+(2?4?6?...?200)

2222=201(201k?2??i)+4?t?1100i?1100(100?1)(200?1) (2)

6100?101?201=1349380.

6将(1)代入(2)得

?ai2?201?(?20)?4?例6 令an表示前n个质数之和,即a1?2,a2?2?3?5,a3?2?3?5?10,?,证