当前位置:首页 >> 数学 >> 清北学堂 2012年五一数学精品班(集训七)数论导学(同余问题 高斯函数 不定方程)

清北学堂 2012年五一数学精品班(集训七)数论导学(同余问题 高斯函数 不定方程)


北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

数论导学? 一、 同余问题与高斯函数?
知识点: 一、同余问题
1.定义 定义: 设 m 是大于 1 的正整数,a,b 是整数,如果 m | a ? b ,则称 a,b 关于

| 模 m 同余,记作 a ≡ b(mod m) ,读作 a 同余 b 模 m。当 m / a ? b ,则称 a,b 关于
模 m 不同余,记作 a ≡ b(mod m) 。 / 显然,有如下事实: (1)若 a ≡ 0(mod m) ,则 m | a . (2) a ≡ b(mod m) ? a, b 分别用 m 除,余数相同。 2.性质 定理 1 设 a,b,c,m(m>1)是整数,则有 (1)反身性: a ≡ a(mod m) ; (2)对称性:若 a ≡ b(mod m) ,则 b ≡ a(mod m) ; (3)传递性:若 a ≡ b , b ≡ c(mod m) ,则 a ≡ c(mod m) . 定理 2 设 a1 ≡ b1 (mod m), a 2 ≡ b2 (mod m) ,则

(1). a1 ± a 2 ≡ b1 ± b2 (mod m) (2) a1a2 ≡ b1b2 (mod m) 推论 1
n

若 ak ≡ bk (mod m), k = 1, 2,
n

, n, 则 ak ≡ bk (mod m), k = 1,2,

,n

(1) ∑ a k ≡ ∑ bk (mod m) ,
k =1 n k =1 n

(2) ∏ a k ≡ ∏ bk (mod m) .
k =1 k =1

推论 2

若 a ≡ b(mod m) ,则 a n ≡ bn (mod m) .
1?

?

北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

定理 3 推论

若 a1 a 2 ≡ b1b2 (mod m), a 2 ≡ b2 (mod m) ,且 (a 2 , m) = 1 ,则 a1 ≡ b1 (mod m) . 若 ac ≡ bc(mod m) ,且 (m, c) = 1 ,则

a ≡ b(mod m) .
注 条 件 (m, c) = 1 是 不 可 缺 少 的 , 当 (m, c) ≠ 1 时 , 此 性 质 不 成 立 。 例 如

2×4≡4×6(mod 12),但 2 ≡ 4(mod12) . / 定理 4 若 a ≡ b(mod m) ,且 (a, b) = d , d | m ,则

a b? m? ≡ ? mod ? . d d? d?

定理 5



a ≡ b(mod m1 ) , a ≡ b(mod m 2 ) ,

…………

a ≡ b(mod mn ) ,


M = [m1 , m2 ,
a ≡ b(mod M )

, mn ] ,则

二、高斯函数 1.定义 则 函数 y = [x] 设 x ∈ R, [ x] 表示不超过 x 的最大整数, y = [x] 称为高斯函数。 的定义域为 R,值域为 Z。 x ∈ R 由定义知,[ x] ≤ x ,故 x ? [ x] ≥ 0. 称 [x] 为 x 整数部分,称 x ? [x] 为 x 的小数 部分,记作{x}. 例如, [3.2] = 3,{3.2} = 0.2; [?2.3] = ?3,{?2.3} = 0.7. 2.性质 [x]的应用范围很广,很多竞赛题都要应用[x]的性质。 性质 1 性质 2 性质 3 对任意 x ∈ R ,都有 x = [ x] + {x} ,且 0 ≤ {x} < 1 . 对任意 x ∈ R ,都有 x ? 1 < [ x] ≤ x < [ x] + 1 对任意 x1 , x2 ∈ R ,且 x1 ≤ x2 ;有
2? ?

[ x1 ] ≤ [ x2 ]

北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

性质 4 性质 5 性质 6 性质 7

对任意 n ∈ Z 和 x ∈ R ,都有

[n + x] = n + [ x] .

对任意的 x, y ∈ R ,都有 [ x] + [ y ] ≤ [ x + y ],{x} + { y} ≥ {x + y}. 若 x ≥ 0, y ≥ 0 ,则 [ xy] ≥ [ x][ y ].
? x ? ?[ x] ? 对任意正整数 n 和任意实数 x,有 ? ? = ? ? 。 ?n? ? n ?

性质 8 性质 9

?? [ x], [? x] = ? ?? [ x] ? 1,

x ∈ Z, x?Z

x 为正实数,n 为正整数,则不超过 x 的所有正实数中,是 n 的倍数的

?x? 数共有 ? ? 个. ?n?

性质 10

在 n!的质因数分解中,质数 p 的指数是 ? n ? + ? m ? ( p m ≤ n < p m +1 ) ?p ?

?n? ? n ? ? n ? ? p ? + ? p 2 ? + ? p3 ? + ? ? ? ? ? ?

模拟真题:
题 1:求使 2 n ? 1 为 7 的倍数的所有正整数 n. 分析: 易知 2 3 ? 1 = 7 ,即 7|23-1,从而知 n=3 为所求的最小正整数。经验证

n=4,5 不满足条件,当 n=6 时,满足题所要求的条件,于是猜测,满足条件的 n
是 3 的倍数,下面证明这个猜测是正确的。 解析:(1)n=3m 时,有 2 3 ≡ 1(mod 7) ,故 2 3m ≡ 1(mod 7) , 即

2 3m ? 1 ≡ 0(mod 7) ,
n

所以,当 n=3m 时,2 -1 是 7 的倍数。 (2)当 n=3m+1 时,

2 3m+1 ≡ 2 3m ? 2 ≡ 1 ? 2 ≡ 2(mod 7) ,


23m+1 ? 1 ≡ 2 ? 1 ≡ 1(mod 7) ,

所以,当 n=3m+1 时,2n-1 不是 7 的倍数。 (3)当 n=3m+2 时,

2 3m+ 2 ≡ 2 3m ? 2 2 ≡ 1 ? 4 ≡ 4(mod 7) ,

?

2 3m+1 ? 1 ≡ 4 ? 1 ≡ 3(mod 7) ,
3?

北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

所以,当 n=3m+2 时, 2n ? 1 不是 7 的倍数。 因此,满足条件的 n 是所有 3 的倍数的正整数。 题 2: 设三角形的三边长分别是整数 l , m, n , l > m > n. 已知, 且 其中 {x} = x ? [ x] , 而[x]表示不超过 x 的最大整数,求这种三角形周长的最小值。

? 3l ? ? 3 m ? ? 3 n ? 解 由于 ? 4 ? = ? 4 ? = ? 4 ? ,所以 3l ≡ 3m ≡ 3n (mod10 4 ) ,于是 ?10 ? ?10 ? ?10 ?

3l ≡ 3m ≡ 3n (mod 2 4 ) , 3l ≡ 3m ≡ 3n (mod 5 4 ) ,
由于(3,2)=(3,5)=1,由①可知, 3l ?n ≡ 3m?n ≡ 1(mod 2 4 ).

① ②

则对任意的满足 3v ≡ 1(mod 24 ) 现在设 u 是满足 3u ≡ 1(mod 2 4 ) 的最小正整数, 的正整数 v 有 u|v。 事实上,若 v 不能被 u 整除,则由带余除法可知,存在非负整数 a 和 b 使得 v = au + b ,其中 0 < b ≤ u ? 1 ,从而可推得,

3b ≡ 3b+ au ≡ 3v ≡ 1(mod 24 ) ,
显然,这与 u 的定义矛盾,所以 u|v. 经计算可得, 34 ≡ 1(mod 2 4 ) ,从而可设 m ? n = 4k ,其中 k 为正整数。 同理,由②推得 3m?n ≡ 1(mod 5 4 ) ,故 34 k ≡ 1(mod 5 4 ). 现在求满足 34 k ≡ 1(mod 5 4 ) 的正整数 k. 因为 3 4 = 5 × 2 4 + 1 ,所以 34 k ? 1 = (5 × 2 4 + 1) k ? 1 ≡ 0(mod 5 4 ), 即
k ( k ? 1)( k ? 2) 3 12 k ( k ? 1) 2 ×5 ×2 + × 5 × 2 8 + 5k × 2 4 6 2 k ( k ? 1)(k ? 2) 3 11 ≡ × 5 × 2 + 5 2 k [(k ? 1) × 2 7 + 3] + 5k 3

≡ 0(mod 5 4 ),

k ( k ? 1)( k ? 2) 2 × 5 × 211 + 5k [( k ? 1) × 2 7 + 3] + k ≡ 0(mod 5 3 ), 3 即有 k = 5t ,并代入该式得

5t[(5t ? 1) × 2 7 + 3] + t ≡ 0(mod 5 2 )t ≡ 0(mod 5 2 ).
由此可得

t ≡ 0(mod 5 2 ) ,即 t = 25s ,其中 s 为正整数.
4?

?

北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

于是 故 同理可证 由于

k = 5t = 125s ,s 为正整数. m ? n = 500 s ,s 为正整数. 1 ? n = 500 r ,r 为正整数. 1 > m > n ,所以 r > s.

这样,三角形的三边为 500r + n,500 s + n和n. 由于两边之差小于第三边,故

n > 500(r ? s) ,因此,当 s = 1, r = 2, n = 501 时三角形的周长最小。其值为

(1000 + 501) + (500 + 501) + 501 = 3003.
题 3: 44444444 的十进位数的数字和是 A,A 的数字和是 B,B 的数字和是多少? 解析: 设 B 的数字和是 C,显然, 4444 4444 < 10000 4444 ,所以 44444444 的位数不 超过 4444 × 4 + 1 < 20000 . 因为每一个数字都不大于 9,所以, A < 9 × 20000 = 180000 < 199999 ,而 199999 的数字和总比小于 199999 的数的数字和大。则 A 的数字和 B < 46 。 于是,B 的数字和 C≤12,这是因为 12 是小于 46 的正整数中最大的数字和 (39 的数字和是 12)。 由于一个正整数与其数字和关于模 9 同余,于是

44444444 ≡ A ≡ B ≡ C (mod 9) 4,
所以

C ≡ 44444444 ≡ (?2) 4444 ≡ 2 ? (2 3 )1481 ≡ 2 ? (?1)1481 ≡ ?2 ≡ 7(mod 9) .

因为在 C≤12 的正整数中,只有 7 本身才能与 7 模 9 同余。所以 C=7,这就 是说 B 的数字和是 7。 4444 评 注 本题首先对 4444 和 A,B,C 关于模 9 的余数估计,然后利用

44444444 ≡ C (mod 9) 计算 C 的值,即采取了“先估后算”的解题方法。
题 4:x 为实数,n 为正整数,求证: [ x] [2 x] [nx ] ≥ + + 1 2
[ nx ] . n

+

证明: 用数学归纳法来证。显然对 n=1 有 [ x] ≥ [ x] 成立。 设
Ak = [ x ] + [2 x ] + 2 + [ kx ] ; k

A1 ≤ [ x], A2 ≤ [2 x],
下面来证明 An ≤ [nx]. 由

, An ?1 ≤ [(n ? 1) x].

nAn ? nAn?1 = [nx],
5? ?

北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

(n ? 1) An?1 ? (n ? 1) An ?2 = [(n ? 1) x],
…………
2 A2 ? 2 A1 = [ 2 x], A1 = [ x],

知,这 n 个等式的和为

nAn ? ( A1 + A2 +


+ An ?1 ) = [ x] + [2 x] + + [nx] + A1 + A2 + + [nx] + [ x] + [2 x] +

+ [nx],

nAn = [ x] + [2 x] +
由归纳假设知

+ An ?1 . + [(n ? 1) x]
+ [(n ? 1) x] + [ x] + [nx],

nAn ≤ [ x] + [2 x] +

= [ x] + [(n ? 1) x] + [2 x] + [(n ? 2) x] + 由性质 4 知

nAn ≤ [ x + (n ? 1) x] + [2 + (n ? 2) x] +
= [nx] + [nx] + 故有 An ≤ [nx].

+ [(n ? 1) x + x] + [nx]

+ [nx] + [nx] = n[nx],

二、不定方程?
知识点:
1.一次不定方程 整系数方程 ax+by=c(a>0,b≠0)通常称为二元一次不定方程。 对于二元一次不定方程,已经解决是否有解及如何求解的问题。 定理 1 二元一次不定方程 ax+by=c(a,b,c∈Z,a>0,b≠0) ① 有整数解的充分必要条件是(a,b)|c。 显然,若(a,b)=1,方程①有解。 定理 2 若 x0,y0 是①的一组解(通常称为①的一组特解) ,则方程①的全部解 (通常称为通解)为
b ? ? x = x 0 + ( a , b) t ? ? a ? y = y0 ? t ? ( a, b ) ? t∈Z 。

特别地,若(a,b)=1,则方程①的通解为

6? ?

北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

? x = x 0 + bt ? ? y = y 0 ? at

t∈Z 。

定理 3

k 元一次不定方程
a1 x1 + a 2 x 2 + + ak xk = c (c, a i ∈ Z , i = 1,2, , k , k ≥ 3, a1 a 2 a k ≠ 0)

② 有整数解的充分必要条件是 (a1 , a 2 ,
, ak ) | c 。

2.一次不定方程组 一次不定方程组主要手段是通过消元的方法来求解。 3.勾股数 对于不定方程
x2 + y2 = z2



如果(x,y)=d,则 d2|z2,即 d|z,这样方程两边可约去 d。所以在讨论③ 的解时,仅需在(x,y)=1 时讨论。此时 x,y,z 是两两互素的。这样两两互 素的解(x,y,z)称为方程③的本原解。 定理 4 不定方程③满足 (x,y)=1,x>0,y>0,z>0,2|y ④ 的全部解可表示成
?x = a 2 ? b 2 ? ? y = 2ab ?z = a 2 + b 2 ?



其中 a,b 是满足 a>b>0,a,b 一奇一偶,且(a,b)=1 的任意整数。 4.沛尔方程 形如
x 2 ? dy 2 = 1

⑥ ⑦

或 x 2 ? dy 2 = ?1

的二元二次不定方程称为佩尔方程。其中 d∈Z,d>0 且非平方数。 定义 设正整数 x1 和 y1 是方程⑥的所有正整数解中使 x1 + d y1 最小的一组解,

称 ( x1 , y1 ) 是方程⑥或⑦的基本解。 定理 5 设 ( x1 , y1 ) 是方程⑥或⑦的基本解, 则对于⑥或⑦的任意一组正整数解 x, (

y) ,必有
定理 6

x1≤x, y1≤y. 方程⑥有无穷多组正整数解,且全部正整数解由下式给出:

7? ?

北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

1 ? n n , ? x = ( x + d y1 ) + ( x1 ? d y1 ) ? n 2 1 ? 1 ( x1 + d y1 ) n ? ( x1 ? d y1 ) n 。 ? yn = ? 2 d ?

[

]

[

]



其中 ( x1 , y1 ) 是⑥的基本解,n=1,2,…。 公式⑧也可写成
x n + y n d = ( x1 + y1 d ) n 。

由公式⑧可以推导出 xn,yn 满足线性递推关系:
? x n +1 = 2 x1 x n ? x n ?1 ? ? y n +1 = 2 x1 y n ? y n ?1

, .

定理 7

方程⑦有无穷多组正整数解,且全部正整数解由下式给出:
1 ? 2 n +1 , + ( x1 ? d y1 ) 2 n +1 ? x n = 2 ( x1 + d y1 ) ? ? 1 ( x1 + d y1 ) 2 n +1 ? ( x1 ? d y1 ) 2 n +1 。 ? yn = ? 2 d ?

[

]

[

]



其中 ( x1 , y1 ) 是⑦的基本解,n=1,2,…。 公式⑨也可写成
x n + y n d = ±( x1 + y1 d ) 2 n +1

模拟真题:
题 1:不存在整数 x,y 使方程
x 2 + 3 xy ? 2 y 2 = 122



成立 (第 14 届美国数学邀请赛题)。 证明: 如果有整数 x,y 使方程①成立,则
17 × 29 ? 5 = 488 = 4 x 2 + 12 xy ? 8 y 2 = (2 x + 3 y ) 2 ? 17 y 2 ,

知(2x+3y)2+5 能被 17 整除。 设 2x+3y=17n+a,其中 a 是 0,±1,±2,±3,±4,±5,±6,±7,±8 ,而 中的某个数,但是这时(2x+3y) +5=(17n) +34na+(a +5)=a +5(mod17)
2 2 2 2

a2+5 被 17 整除得的余数分别是 5,6,9,14,4,13,7,3,1,即在任何情况
下(2x+3y)2+5 都不能被 17 整除,这与它能被 17 整除矛盾。 故不存在整数 x,y 使①成立。 题 2:证明不定方程
x 3 + y 3 + z 3 + t 3 = 1999

有无穷多组整数解。
8? ?

北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

证明: 注意到

10 3 + 10 3 + ( ?1) 3 + 0 3 = 1999 ,

因此,方程有整数解。由上可知,我们可寻找如下形式的整数解: x=10-k,y=10+k,z=-1-m,t=m, k,m∈Z) ( 。 2 代入方程并化简得 m(m+1)=20k ,即有
(2m + 1) 2 ? 80k 2 = 1

这是佩尔方程,易知 m1=4,k1=1 是其基本解,全部正整数解为
1 ? n n ?2m n + 1 = 2 (9 + 80 ) + (9 ? 80 ) , ? ? 1 (9 + 80 ) n + (9 ? 80 ) n . ? kn = ? 2 80 ?

[ [

] ]

(n = 1,2, )

所以原方程有无穷多组整数解。 题 3: 试求所有的正整数 n,使方程
x 3 + y 3 + z 3 = nx 2 y 2 z 2

有正整数解。 解析: 设 x,, 是其正整数解, y z 由对称性, 不妨设 x≤y≤z。 显然有 z 2 | ( x 3 + y 3 ) , 故 z 2 ≤ x 3 + y 3 ,但 x 3 ≤ xz 2 , y 3 ≤ yz 2 ,即 x 3 + y 3 ≤ z 2 ( x + y ) 。 又
z = nx 2 y 2 ? x3 + y3 ≥ nx 2 y 2 ? ( x + y ) , z2

x 3 + y 3 ≥ z 2 ≥ (nx 2 y 2 ? x ? y ) 2 ≥ n 2 x 4 y 4 ? 2nx 2 y 2 ( x + y ) 。

于是

n 2 x 4 y 4 ≤ 2nx 2 y 2 ( x + y ) + x 3 + y 3 ,

?1 1? 1 1 xy ≤ 2? + ? + 3 + 3 。 ? x y ? nx ny ? ? ?1



< 3 ,与①矛盾。 若 x≥2,则 xy≥4,而 2? + ? + 3 + 3 ≤ 2 + ? x y ? nx 4n ny ? ?

1?

1

1

1

故 x=1,则①式转化为
y≤2+ 2 1 1 + + 3 y n ny



若 y≥4,则 2 + 故 y≤3。

2 1 1 2 1 1 5 9 5 9 29 + + 3 ≤2+ + + = + ≤ + = < 4 ,与②矛盾。 y n ny 4 n 8n 2 8n 2 8 8

注意到 z 2 | ( x 3 + y 3 ) ,即 z 2 | (1 + y 3 ) ,故只能是 y=1,z=2,或 y=2,z=3。 (当 y=3 。 时,z=2,与 z≥y 矛盾)
9? ?

北京清北学堂教育科技有限公司? ? ? ? 电话:010‐88400806,010‐88400903? ? ? 网址:www.topschool.org? ?

把 x,y,z 代入原方程可得 n=3 或 1. 题 4: 证明:不存在不同时为 0 的整数 x,y,z 满足等式 x 2 + y 2 = 3z 2 . 证明:假设方程有整数解(x,y,z)≠(0,0,0) ,那么一定有整数解(x0, y0,z0) ,其中(x0,y0)=1。事实上,设(x1,y1,z1)为一个解, x1,y1)=d, ( 2 2 2 2 即 x1=d x0,y1=d y0。则 d |3z1 ,d |z1 ,即 z1=dz0,所以(x0,y0,z0)也是方程 的一个解。于是只需讨论方程:
x 2 + y 2 = 3z 2 , x,y)=1 (



当(x,y)=1 时, x 2 + y 2 ≡ 0(mod 3) 恒不成立。事实上,因(x,y)=1,因此 x ≡0(mod3)和 y≡0(mod3)不能同时成立。故 x≡±1 (mod3)与 y≡±1 (mod3)到 少有一个成立。从而 x 2 + y 2 ≡ 2(mod 3) 或者 x 2 + y 2 ≡ 1(mod 3) ,与①矛盾。故方程 没有 x,y,z 不全为 0 的解.?

10? ?


更多相关文档:
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com