nbhkdz.com冰点文库

高中数学竞赛——数论


高中数学竞赛

数论

剩余类与剩余系
1.剩余类的定义与性质 (1)定义 1 设 m 为正整数,把全体整数按对模 m 的余数分成 m 类,相应 m 个集合记为:K0,K1,?,Km-1,其中 Kr={qm+r|q∈Z,0?余数 r?m-1}称为模 m 的一 个剩余类(也叫同余类)。K0,K1,?,Km-1 为模 m 的全部剩余类

. (2)性质(ⅰ) Z ? ? K i 且 Ki∩Kj=φ (i≠j).
0 ?i ? m ?1

(ⅱ)每一整数仅在 K0,K1,?,Km-1 一个里. (ⅲ)对任意 a、b∈Z,则 a、b∈Kr ? a≡b(modm). 2.剩余系的定义与性质 (1)定义 2 设 K0,K1,?,Km-1 为模 m 的全部剩余类, 从每个 Kr 里任取一个 ar, 得 m 个数 a0,a1,?,am-1 组成的数组,叫做模 m 的一个完全剩余系,简称完系. 特别地,0,1,2,?,m-1 叫做模 m 的最小非负完全剩余系.下述数组叫做模 m 的绝对 最小完全剩余系:当 m 为奇数时, ? 时, ?
m ?1 m ?1 m ?1 ,? ? 1,?,?1,0,1,?, ;当 m 为偶数 2 2 2

m m m m m ,? ? 1, ?,?1,0,1, ?, ? 1 或 ? ? 1,?,?1,0,1,?, . 2 2 2 2 2

(2)性质(ⅰ)m 个整数构成模 m 的一完全剩余系 ? 两两对模 m 不同余. (ⅱ)若(a,m)=1,则 x 与 ax+b 同时遍历模 m 的完全剩余系. 证明:即证 a0,a1,?,am-1 与 aa0+b, aa1+b,?,aam-1+b 同为模 m 的完全剩余系, 因 a0,a1,?,am-1 为模 m 的完系时,若 aai+b≡aaj+b(modm),则 ai≡aj(modm), 矛盾!反之,当 aa0+b, aa1+b,?,aam-1+b 为模 m 的完系时,若 ai≡aj(modm),则有 aai+b≡aaj+b(modm),也矛盾!
1

(ⅲ)设 m1,m2 是两个互质的正整数,而 x,y 分别遍历模 m1,m2 的完系,则 m2x+m1y 历遍模 m1m2 的完系. 证明:因 x,y 分别历遍 m1,m2 个整数,所以,m2x+m1y 历遍 m1m2 个整数. 假定 m2x/+m1y/≡m2x//+m1y//(modm1m2),其中 x/,x//是 x 经历的完系中的数,而 y/,y//是 y 经历的完系中的数.因(m1,m2)=1,所以,m2x/≡m2x//(modm1),m1y/≡m1y// (modm2),从而 x/≡x//(modm1),y/≡y//(modm2),矛盾! 3.既约剩余系的定义与性质 (1)定义 3 如果剩余类 Kr 里的每一个数都与 m 互质,则 Kr 叫与 m 互质的剩 余类.在与模 m 互质的全部剩余类中,从每一类中任取一个数所做成的数组,叫 做模 m 的一个既约(简化)剩余系.如:模 5 的简系 1,2,3,4;模 12 的简系 1,5,7,11. (2)性质(ⅰ)Kr 与模 m 互质 ? Kr 中有一个数与 m 互质; 证明:设 a∈Kr,(m,a)=1,则对任意 b∈Kr,因 a≡b≡r(modm),所以,(m,a)=(m,r)= (m,b)=1,即 Kr 与模 m 互质. (ⅱ)与模 m 互质的剩余类的个数等于 ?(m) ,即模 m 的一个既约剩余系 由 ?(m) 个整数组成( ?(m) 为欧拉函数); (ⅲ)若(a,m)=1,则 x 与 ax 同时遍历模 m 的既约剩余系. 证明:因(a,m)=1,(x,m)=1,所以,(ax,m)=1.若 ax1≡ax2(modm),则有 x1≡x2(modm),矛盾! (ⅳ)若 a1,a2,?,aφ(m)是 ?(m) 个与 m 互质的整数,并且两两对模 m 不同余, 则 a1,a2,…,aφ(m)是模 m 的一个既约剩余系. 证明:因 a1,a2,?,aφ(m)是 ?(m) 个与 m 互质的整数,并且两两对模 m 不同余, 所以,a1,a2,?,aφ(m)属于 ?(m) 个剩余类,且每个剩余类都与 m 互质,故 a1,a2,?,aφ(m)
2

是模 m 的一个既约剩余系. (ⅴ)设 m1,m2 是两个互质的正整数,而 x,y 分别历遍模 m1,m2 的既约剩余 系,则 m2x+m1y 历遍模 m1m2 的既约剩余系. 证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因 x,y 分别 历遍模 m1,m2 的完系时,m2x+m1y 历遍模 m1m2 的完系.由(m1,x)=(m2,y)=1, (m1,m2)=1 得(m2x,m1)=(m1y,m2)=1,所以,(m2x+m1y,m1)=1,(m2x+m1y,m2)=1,故 (m2x+m1y, m1m2)=1.反之若(m2x+m1y, m1m2)=1,则(m2x+m1y,m1)=(m2x+m1y,m2) =1,所以,(m2x,m1)=(m1y,m2)=1,因(m1,m2)=1,所以,(m1,x)=(m2,y)=1.证毕. 推论 1 若 m1,m2 是两个互质的正整数,则 ? (m1m2 ) ? ? (m1 )? (m2 ) . 证明:因当 x,y 分别历遍模 m1,m2 的既约剩余系时,m2x+m1y 也历遍模 m1m2 的既约剩余系,即 m2x+m1y 取遍 ? (m1m2 ) 个整数,又 x 取遍 ? (m1 ) 个整数,y 取遍

? (m2 ) 个整数,所以, m2x+m1y 取遍 ? (m1 )? (m2 ) 个整数,故 ? (m1m2 ) ? ? (m1 )? (m2 ) .
推论 2 设整数 n 的标准分解式为 n ? p1 1 p2 2 ? pk
?1 ,?,? k ? N * ),则有 ? (n) ? n(1 ?
1 1 1 )(1 ? ) ?(1 ? ) . p1 p2 pk
? ? ?

?

?

?k

( p1 ,?, pk 为互异素数,

证明:由推论 1 得 ?(n) ? ?( p1 1 )?( p2 2 )??( pk k ) ,而 ? ( p? ) ? p? ? p? ?1 , (即从 1 到 p ? 这 p ? 个数中,减去能被 p 整除的数的个数),所以,

?(n) ? ( p1? ? p1? ?1 )( p2? ? p2? ?1 )?( pk ? ? pk ? ?1 )
1 1 2 2 k k

? n(1 ?

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

4.欧拉(Euler)与费尔马(Fermat)定理 欧拉(Euler)定理 设 m 是大于 1 的整数,(a,m)=1,则 a
? ( m)

? 1(modm) .

证明:设 r1,r2,?,r ? (m) 是模 m 的既约剩余系,则由性质 3 知 ar1,ar2,?,ar ? (m) 也是
3

模 m 的既约剩余系,所以, ar1ar2?ar ? (m) ≡r1r2?r ? (m) (modm),即 a

? ( m)

r1r2 ?r? ( m) ?

r1r2 ?r? ( m) ,因( r1r2 ?r? ( m) ,m)=1,所以, a? ( m) ? 1(modm) .
p 推论(Fermat 定理) 设 p 为素数,则对任意整数 a 都有 a ? a(mod p) .

证明:若(a, p)=1,由 ? ( p) ? p ? 1及 Euler 定理得 a

p?1

? 1(mod p) 即

a p ? a(mod p) ;若(a, p)≠1,则 p|a,显然有 a p ? a(mod p) .
例 1 设 m>0,证明必有一个仅由 0 或 1 构成的自然数 a 是 m 的倍数. 证明:考虑数字全为 1 的数:因 1,11,111,1111,?中必有两个在 modm 的同一剩 余类中,它们的差即为所求的 a. 例 2 证明从任意 m 个整数 a1,a2,?,am 中,必可选出若干个数,它们的和 (包括只一个加数)能被 m 整除. 证明:考虑 m 个数 a1,a1+a2,a1+a2+a3,?,a1+a2+?+am,如果其中有一个数能被 m 整除,则结论成立,否则,必有两个数属于 modm 的同一剩余类,这两个数的差即 满足要求. 例 3 设 f(x)=5x+2=f1(x), fn+1(x)=f[fn(x)].求证:对任意正整数 n,存在正整数 m, 使得 2011|fn(m). 证明:因 f2(x)=f[f(x)]=5(5x+2)+2=52x+5×2+2, f3(x)=f[f2(x)]=53x+52×2+5×2+2,?, fn(x)=5nx+5n-1×2+5n-2×2+?+2, 因(5n,2011)=1,所以,x 与 fn(x)同时历遍 mod2011 的完系,1?x?2011, 所以,存在正整数 m(1?m?2011)使得 fn(m)≡0(mod2011),即 2011|fn(m). 例 4 设 a1, a2 , a3 ,?是整数序列,其中有无穷多项为正整数,也有无穷多项为 负整数.假设对每个正整数 n ,数 a1, a2 , a3 ,?, an 被 n 除的余数都各不相同.证明:在 数列 a1, a2 , a3 ,?中,每个整数都刚好出现一次.
4

证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设 a1=0. 此时对每个正整数 k 必有∣ak∣<k:若∣ak∣?k,则取 n=∣ak∣, 则 a1≡ak≡0(mod n),矛盾. 现在对 k 归纳证明 a1,a2,…,ak 适当重排后是绝对值小于 k 的 k 个相邻整数.k=1 显然.设 a1,a2,…,ak 适当重排后为-(k-1-i),…,0,…,i (0?i?k-1),由于 a1,a2,…,ak,ak+1 是(mod k+1)的一个完全剩余系,故必 ak+1≡i+1(mod k+1), 但 ∣ak+1∣<k+1,因此 ak+1 只能是 i+1 或-(k-i),从而 a1,a2,…,ak,ak+1 适当重排后是绝对 值小于 k+1 的 k+1 个相邻整数. 由此得到:1).任一整数在数列中最多出现一次;2).若整数 u 和 v (u<v) 都出现在 数列中,则 u 与 v 之间的所有整数也出现在数列中. 最后由正负项均无穷多个(即数列含有任意大的正整数及任意小的负整数) 就得到:每个整数在数列中出现且只出现一次. 例 5 偶数个人围着一张圆桌讨论,休息后,他们依不同次序重新围着圆桌 坐下,证明至少有两个人,他们中间的人数在休息前与休息后是相等的。 证明:将座号依顺时针次序记为 1,2,?,2n,每个人休息前后的座号记为 (i,j),则 i 与 j 历遍完全剩余系 mod2n。如果两个人(i1,j1),(i2,j2)休息前后在 他们中间的人数不相等,则有 j2-j1?i2-i1mod2n,即 j2-i2?j1-i1(mod2n),因此, j-i 也历遍完全剩余系 mod2n,所以,j-i 的和= ? j ? ?i ≡0(mod2n), 而任一完全剩 余系 mod2n 的和≡1+2+?+2n-1≡n(2n-1)?0(mod2n),矛盾!故结论成立. 例 6 数列{an}定义为: a0=a(a∈N*), an+1=an+ 40n! (n∈N).数列{an}中存在无穷 多项可被 2011 整除.
). 证明:因(40,2011)=1,所以, 40? ( 2011) ? 1(mod2011
5

) 时, ? (2011 ) | n! ,所以,数列{an(mod2011)}构成模 2011 的完系, 因当 n ? ? (2011

且是周期数列,所以, 数列{an}中存在无穷多项可被 2011 整除. 例 7 证明:存在无穷多个正整数 n,使得 n2+1?n!. 证明:引理 1 对素数 p>2, p ? 1(mod4) ? 存在 x(1?x?p-1)使 x 2 ? ?1(mod p) . 证:充分性:因对 1?x?p-1,( p,x)=1,所以, x
(?1)
p ?1 2

p ?1

? (x )
2

p ?1 2

? 1(mod p) , ( x )
2

p ?1 2

?

? 1(mod p) ,所以,

p ?1 为偶数,即 p ? 1(mod4). 2

必要性:因 1?x?p-1 时,x,2x,?,(p-1)x 构成 modp 的既约剩余系,所以,存在 1?a?p-1,使得 ax≡-1(mod p),若不存在 a(1?a?p-1), a=x,使 ax≡-1(mod p),
p ?1 p ?1 p ?1 则这样的 a,x 共配成 对,则有 (?1) 2 ? ( p ? 1)!? ?1(mod p) ,即 为奇数,与 2 2

p ? 4k ? 1 矛盾!所以,必存在 x(1?x?p-1)使 x 2 ? ?1(mod p) .

引理 2 形如 4k+1(k∈Z)的素数有无限多个. 证:假设形如 4k+1 的素数只有 n 个:p1,p2,?,pn,则 p1,p2,?,pn 都不是 a=4(p1p2?pk)2+1 的素因数. 设 q 是 a 的一个素因数,则有(2p1 p2?pk)2≡-1(modq),因存在 1?x?q-1 使 2p1 p2?pk≡x(mod q),即 x2≡-1(modq),所以,由引理 1 知 q ? 4k ? 1 ,矛盾! 所以,形如 4k+1 的素数有无限多个. 回到原题:由引理 1,2 知,存在无穷多个素数 p,使得存在 x(1?x?p-1)使
x 2 ? ?1(mod p) .即 p|x2+1,因 p>x,所以, p?x!, x2+1?x!,因这样的素数 p 无穷多,所以,

相应的 x 也无穷多. 例 8 设 f(x)是周期函数,T 和 1 是 f(x)的周期且 0<T<1.证明: (1)若 T 为有理数,则存在素数 p,使得
1 是 f(x)的周期; p
6

(2)若 T 为无理数,则存在各项均为无理数的数列{an}满足 0<an+1<an<1 (n=1,2, …),且每个 an 都是 f(x)的周期. 证明: (1)设 T=
m (正整数 m,n 互质,且 n?2),因(m,n)=1,所以,m,2m,…,nm 构成 n

modn 的完系,故存在 k∈N*使得 km≡1(modn),即存在 t∈N*使得 km=nt+1,因 f(x)=f(x+kT)=f(x+
km 1 1 1 )=f(x+t+ )=f(x+ ),所以 是周期. n n n n

设 n=kp,其中 k∈N*, p 为素数,则

1 1 1 ? k ? 是周期.故存在素数 p,使 是周期. p n p

(2)当 T 为无理数时,取 a1=T,则 T 为无理数, 0<T<1.设 k≤n 时存在无理数 ak,使得 0<ak<ak-1<1,且 ak 是周期.对 k+1,总存在存在 u,v∈N*,使得 0<uak-v<ak<1, 取 ak+1=uak-v,则 ak+1 是无理数且是 f(x)的周期,且 0<ak+1<ak<1,递推知存在各 项均为无理数的数列{an}满足 0<an+1<an<1(n=1,2,…),且每个 an 都是 f(x)的周期. 例 9 设正整数 n?2.求所有包含 n 个整数的集合 A,使得 A 的任意非空子集 中所有元素的和不能被 n+1 整除. 解:设 A={a1,a2,?,an}是满足条件的集合. S k ? ? ai (k ? 1,2,?, n) ,依题意知,对
i ?1 k

任意 k=1,2,?,n 都有 n+1?Sk,且任意 Sk, Sj(k≠j)都有 Sk?Sj(modn+1),所以,{Sk}包 含了 modn+1 的所有非零剩余,因对 1?i≤n,整数 ai,S2,S3,?,Sn 也包含了 mod(n+1) 的所有非零剩余,所以, a1=S1≡ai(modn+1),即 A 中任意 ai≡a1(modn+1).所以,对任 意 1?k?n, a1+a2+?+ak≡ka1(modn+1).且 ka1?0(modn+1),从而(a1,n+1)=1. 取 a1=a 得集合 A={a+ki(n+1)|ki∈Z, 1?i≤n,a∈Z,且(a,n+1)=1}为所求. 例 10 对任意正整数 n,用 S(n)表示集合{1,2,?,n}中所有与 n 互质的元素之和. 证明: 2S(n)不是完全平方数;
7

例 11 求所有的奇质数 p,使得 p | ? k p ?1 .
k ?1

2011

2 2 2 p?1 2 例 12 求所有质数 p,使得 p3 | (C1 p ) ? (C p ) ? ? ? (C p ) .

例 13 设 n 为大于 1 的奇数,k1,k2,?,kn 是 n 个给定的整数,对 1,2,?,n 的每一 个排列 a=(a1,a2,?,an),记 S(a)= ? k i a i .证明:存在两个 1,2,?,n 的排列 b 和 c(b
i ?1 n

≠c),使得 n!|S(b)-S(c). 证明:如果对 1,2,?,n 的任意两个不同排列 b 和 c(b≠c),都有 n!?S(b)-S(c),那么当 a 取遍所有排列时(共 n!个),S(a)遍历模 n!的一个完系, 因此,有 ? S (a) ≡1+2+?+n!≡
a
n n

n!(n!?1) n! ? (modn!) ①, 另一方面,我们有 2 2
n n

? S (a) = ?? ki ai ? ?? ki ai ? ? ki [(n ? 1)!? j] ?
a
a i ?1 i ?1 a i ?1 j ?1

n!(n ? 1) n ki ? 0(modn!) ②. ? 2 i ?1

由① ? S (a) ≡ (modn!)与② ? S (a) ≡0(modn!)(因 n 为奇数)矛盾!故原命题成立.
a

n! 2

a

例 14 已知 m,n 为正整数,且 m 为奇数,(m,2 -1)=1.证明:m| ? k n .
n
k ?1

m

证明:因 1,2,?,m 构成 modm 的完系,(m,2)=1,所以 2,4,?,2m 也构成
modm 的完系,所以 ? (2k ) n ? ? k n (modm) 即 (2 n ? 1)? k n ? 0(modm) .
k ?1 k ?1 k ?1 m m m

因(m,2n-1)=1,所以 m | ? k n .得证.
k ?1

m

例 15 已知 x∈(0,1),设 y∈(0,1)且对任意正整数 n, y 的小数点后第 n 位数字 是 x 的小数点后第 2n 位数字.证明:若 x 是有理数,则 y 也是有理数. 例 16 设 A={a1,a2,…,aφ(n)}是模 n 的一个既约剩余系.如果方程 x2≡1(modn) 在 A 中解的个数为 N,求证: a1a2…aφ(n)≡ (?1) (modn).
8
N 2

同余方程与同余方程组
1.同余方程(组)及其解的概念 定义 1 给定正整数 m 及 n 次整系数多项式 f ( x) ? an x n ? an?1 x n?1 ? ? ? a1 x ? a0 , 则同余式 f(x)≡0(modm)①叫做模 m 的同余方程,若 an 0(modm),则 n 叫做方程 ①的次数. 若 x=a 是使 f(a)≡0(modm)成立的一个整数,则 x≡a(modm)叫做方程①的一个 解,即把剩余类 a(modm)叫做①的一个解. 若 a1(modm),a2(modm)均为方程①的解,且 a1,a2 对模 m 不同余,就称它们是方 程①的不同解.由此可见,只需在模 m 的任一组完系中解方程①即可. 例 1 解方程 2x2+x-1≡0(mod7). 解:取 mod7 的完系:-3, -2,-1,0,1,2,3,直接验算知 x≡-3(modm)是解. 例 2 求方程 4x2+27x-12≡0(mod15). 解:取 mod15 的完系:-7, -6,?,-1,0,1,?,7,直接验算知 x≡-6,3(modm)是解. 2.一次同余方程 设 m?a,则 ax≡b(modm),叫模 m 的一次同余方程. 定理 1 当(a,m)=1 时,方程 ax≡b(modm)必有解,且解数为 1. 证明:因当(a,m)=1 时,x 与 ax 同时遍历模 m 的完系,所以,有且仅有一个 x 使得 ax≡b(modm).即 x≡a-1b(modm). 定理 2 方程 ax≡b(modm)有解 ? (a,m)|b,且有解时其解数为(a,m),及若 x0 是一 个特解,则它的(a,m)个解是 x ? x0 ?
m t (modm),t ? 0,1,?, (a, m) ? 1 . (a, m)
9

例 3 解方程 6x≡10(mod8). 解:因(6,8)=2,且-1 是一个特解,所以,方程 6x≡10(mod8)的解为:
x ? ?1 ? 4t (mod8),t ? 0,1 即 x ? ?1,3(mod8) .

例 4 解方程 12x≡6(mod9). 因(12,9)=3,且-1 是一个特解,所以,方程 12x≡6(mod9)的解为:
x ? ?1 ? 3t (mod8),t ? 0,1,2 即 x ? ?1,2, ,5(mod8) .

3.同余方程组 定义 3 给定正整数 m1,m2,?,mk 和整系数多项式 f1(x),f2(x),?,fk(x),则同余式组
? f 1 ( x) ? 0(modm1 ) ? f ( x) ? 0(modm ) ? 2 2 ②,叫做同余方程组.若 x=a 是使 fj(a)≡0(modmj)(1?j?k) ? ? ? ? ? ? ? f k ( x) ? 0(modmk )

成立的一个整数,则 x≡a(modm)叫做方程组②的一个解,即把剩余类 a(modm)叫 做②的一个解.其中 m=[m1,m2,?,mk]. 例 5 解方程组 ?
? x ? 3(mod7) . ?6 x ? 10(mod8)

解:由例 3 知 6x≡10(mod8)的解是 x ? ?1,3(mod8) .所以,原解方程组 ?
? x ? 3(mod7) ? x ? 3(mod7) ? x ? 31(mod7) ?? 或? 或 x ? 3(mod56) ? x ? 31,3(mod56) . ? x ? ? 1 (mod 8 ) x ? 3 (mod 8 ) x ? 31 (mod 8 ) ? ? ?

中国剩余定理:设 K?2,而 m1,m2,?,mk 是 K 个两两互质的正整数,令 M=m1m2?mk=m1M1=m2M2=?=mkMk,则对任意整数 a1,a2,?,ak 下列同余式组:
? x ? a1 (modm1 ) ? x ? a (modm ) ? 2 2 ? ③的正整数解是 x≡a1M1M1-1+a2M2M2-1+?+akMkMk-1(modM). ? ? ? ? ? x ? a k (modm k )

其中 Mj-1 满足 MjMj-1≡1(modmj)(1?j?k),即 Mj 对模 mj 的逆.
10

证明:(1)对 1?j?k,因 mj|Mi(i≠j) ,mj|M,所以 x≡ajMjMj-1≡aj(modmj). (2)设 x,y 都是同余式组的解,即 x≡aj(modmj),y≡aj(modmj)(1?j?k), 则 x≡y(modmj),即 mj|x-y,因 m1,m2,?,mk 两两互质,所以 M| x-y 即 x≡y(modM). 注:(1)存在无穷多个整数 x 满足同余方程组③,这些 x 属于同一模 m 的剩余类; (2)同余方程组③仅有一个解 x≡a1M1M1-1+a2M2M2-1+?+akMkMk-1(modM). (3)当(a,mi)=1(=1,2,?,n)时,同余方程组
? x ? a ?1a1 (modm1 ) ?ax ? a1 (modm1 ) ? ?ax ? a (modm ) ?1 ? ? x ? a a2 (modm2 ) 2 2 ?? ? 仍然具有定理结论. ? ? ? ? ?? ? ? ?1 ? ?ax ? ak (modmk ) ? ? x ? a ak (modmk )

这在数论解题中具有重要应用. 例 6“今有物不知其数,三三数之余二,五五数之余三,七七数之余二,问 物几何”.
? x ? 2(mod3) ? 解:设物数 x,则有 ? x ? 3(mod5) ,这里 m1=3,m2=5,m3=7,M=3×5×7=105,所以, ? x ? 2(mod7) ?

35×35-1≡2×35-1≡1(mod3) ? 35-1≡2(mod3), 21×21-1≡21-1≡1(mod5) ? 21-1≡1(mod3), 15×15-1≡15-1≡1(mod7) ? 15-1≡1(mod3),所以,同余方程组的解为:
x ? 2 ? 35? 2 ? 3 ? 21? 1 ? 2 ? 15? 1 ? 233 ? 23(mod105) ,即 x=105k+23(k∈N).

例 7 有兵一队,若分别列 5,6,7,11 行纵队,则末行人数分别为 1,5,4,10.求兵数.
? x ? 1(mod5) ? x ? 5(mod6) 解:设兵数 x,则 ? ,其中 m1=5,m2=6,m3=7,m4=11,M=2310, ? x ? 4 (mod 7 ) ? ? ? x ? 10(mod11)

462×462-1≡2×462-1≡1(mod5) ? 462-1≡3(mod5),
11

385×385-1≡385-1≡1(mod6) ? 385-1≡1(mod6), 330×330-1≡330-1≡1(mod7) ? 330-1≡1(mod7), 210×210-1≡210-1≡1(mod11) ? 210-1≡1(mod11),所以,同余方程组的解为:
x ? 462? 3 ? 5 ? 385? 4 ? 330? 10? 210 ? 6371? 2111 (mod2310 ),

即 x=2310k+2111(k∈N). 例 8 证明:对任意 n 个两两互质的正整数:m1,m2,?,mn,总存在 n 个连续的自然 数 k+1,k+2,?,k+n 使得 mi|k+i(i=1,2,?,n).
?k ? ?1(modm1 ) ?k ? ?2(modm ) ? 2 证明:由剩余定理知,总存在整数 k 使得 ? ,即存在连续的自然数 ? ?? ? ?k ? ? n(modm n )

k+1,k+2,?,k+n 使得 mi|k+i(i=1,2,?,n). 例 9 证明:对任意 n∈N*,存在 n 个连续正整数它们中每一个数都不是素数的 幂(当然也不是素数). 证明:因都不是素数的幂时,只能是素数之积.对任意 n∈N*,取两组不同的素 数 p1,p2,?,pn 与 q1,q2,?,qn,则由剩余定理知存在 m∈N*,使得
?m ? ?1(mod p1 q1 ) ?m ? ?2(mod p q ) ? 2 2 同时成立.于是,n 个连续正整数 m+1, m+2,?,m+n 中,每一个数都 ? ? ? ? ? ?m ? ?n(mod p n q n )

有两个不同的素因子.故结论成立. 例 10 证明:存在一个含有 N(?2)个正整数的集合 A,使得 A 中任意两个数都 互质,且 A 中任意 k(k?2)个数的和都是合数. 例 11 证明:存在一个由正整数组成的递增数列{an},使得对任意 k∈N*,数列 {k+an}中都至多有有限项为素数.
12

证明:用 p1,p2,p3,?表示所有素数从小到大的排列.令 a1=2,a2 为适合
? x ? 0(mod p1 ) ? x ? 0(mod p1 ) ? 且大于 a1 的最小正整数 a2=8,取 a3 适合 ? x ? ?1(mod p 2 ) 且大于 a2 的 ? ? x ? ?1(mod p 2 ) ? x ? ?2(mod p ) 3 ?

? x ? 0(mod p1 ) ? x ? ?1(mod p ) ? 2 最小正整数 a2=38.假定 a1,a2,?,an 都已确定,则取 an+1 适合 ? 且大 ??? ? ? x ? ?n(mod p n ?1 )

于 an 的最小正整数,由剩余定理知满足条件的 an+1 存在.则上述递推关系定义的 数列{an}满足题意:因对任意 k∈N*,当 n?k+1 时,都有 k+an≡0(modpk+1), 由{an}递增可知{k+an}从第 k+2 项起每一项都是 pk+1 的倍数,且都大于 pk+1,所以, 数列{k+an}中至多有 k+1 项为素数. 例 12 是否存在一个由正整数组成的数列,使得每个正整数都恰在该数列中 出现一次,且对任意正整数 k,该数列的前 k 项之和是 k 的倍数? 解:取 a1=1,假设 a1,a2,?,am 都已确定,令 t 为不在 a1,a2,?,am 中出现的最小正 整数, S=a1+a2+?+am.由剩余定理知存在无穷多个 r∈N*,使得
?a ? r ? 0(mod 2) ?S ? r ? 0(modm ? 1) 成立.(如 a1=1,取 t=2,适合 ? 1 且 r>1,2 得 r=3). ? ?a1 ? r ? t ? 0(mod 3) ?S ? r ? t ? 0(modm ? 2)

a1 , a2 ,?, am } ,令 am+1=r, am+2=t,则这样得到的数列 取这样的 r,使得 r>t 且 r> max{

{an}满足要求. 例 13 证明:存在一个 n∈N*,使得对任意整数 k,整数 k2+k+n 没有小于 2011 的 质因数. 例 14 证明:存在 k∈N*, 使得对任意 n∈N*,数 2nk+1 都是合数. 例 15 设 m∈N*,n∈Z,证明:数 2n 可以表为两个与 m 互素的整数之和.

13


高中数学竞赛资料-数论部分

高中数学竞赛资料-数论部分_数学_高中教育_教育专区。初等数论简介绪言:在各种数学竞赛中大量出现数论题,题目的内容几乎涉及到初等数论的所有专题。 1. 请看下面的例...

高中数学竞赛——数论

高中数学竞赛——数论_学科竞赛_高中教育_教育专区。高中数学竞赛——数论知识点及习题讲解 高中数学竞赛 数论 剩余类与剩余系 1.剩余类的定义与性质 (1)定义 1...

近五年全国高中数学联赛选编——数论

近五年全国高中数学联赛选编——数论_学科竞赛_高中教育_教育专区。2015高中数学联赛备考经典 近五年全国高中数学联赛选编——数论 2015.8.16 1 (l ) 1.(2010 ...

高中数学联赛数论题目汇编

高中数学联赛数论题目汇编_学科竞赛_高中教育_教育专区。联赛数论题目汇编 1.(81 年)组装甲、乙、丙三种产品,需用 A、B、C 三种零件。每件甲需用 A、B 各 2...

初等数论中的几个重要定理 高中数学竞赛

初等数论中的几个重要定理 高中数学竞赛_学科竞赛_高中教育_教育专区。初等数论中的几个重要定理基础知识 定义(欧拉(Euler)函数)一组数 的, 的剩余,即 且对于任...

20002012全国高中数学联赛分类汇编(初等数论)

20002012全国高中数学联赛分类汇编(初等数论)_学科竞赛_高中教育_教育专区。道客巴巴 http://www.doc88.com/ 2000-2012 全国高中数学联赛分类汇编(初等数论) 1、...

高中数学竞赛专题讲座---竞赛中的数论问题

高中数学竞赛专题讲座---竞赛中的数论问题_学科竞赛_高中教育_教育专区。竞赛中的数论问题的思考方法一. 条件的增设 对于一道数论命题,我们往往要首先排除字母取零值...

数学高中竞赛之初等数论1

数学高中竞赛之初等数论1_高一数学_数学_高中教育_教育专区。数学高中竞赛之初等数论1初等数论一、整除性理论 1、整除的部分性质: ①若 c | b,b | a,则 c ...

数学竞赛中的数论问题

简单的一次不定方程. 在高中竞赛大纲中,数论的内容列有:同余,欧几里得除法,裴蜀定理,完全剩余类, 二次剩余,不定方程和方程组,高斯函数[ x ],费马小定理,格点...

高中数学竞赛资料收集

高中数学竞赛资料收集_学科竞赛_高中教育_教育专区。收集了许多人介绍推荐的高中...《基础数论典型题解 300 例》 (王元等) *《计数》 *《组合数学理论与题解...