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

2012江苏省数学竞赛《提优教程》第36讲


第 17 讲





同余是数论中的重要概念,同余理论是研究整数问题的重要工具之一。 设 m 是一个给定的正整数,如果两个整数 a 与 b 用 m 除所得的余数相同,则称 a 与 b 对模同 余,记作 a ? b(modm) ,否则,就说 a 与 b 对模 m 不 同余,记作 a ? b(modm) , 显然, a

? b(modm) ? a ? km ? b, (k ? Z ) ? m | (a ? b) ; 1、 同余是一种等价关系,即有自反性、对称性、传递性 1).反身性: a ? a(modm) ; 2).对称性: a ? b(modm) ? b ? a(modm) ; 3). 传递性 :若 a ? b(modm) , b ? c(modm) 则 a ? c(modm) ; 2、加、减、乘、乘方运算 若 a ? b (mod m) c ? d (mod m)

c b d ? 则 a ? c ? b ? d (mod m) ,a
3、除法

(mod m) , a ? b (mod m)
n n

设 ac ? bd (mod m)则 a ? b (mod

m ) 。 ( c, m)

A 类例题
例 1.证明: 一个数的各位数字的和被 9 除的余数等于这个数被 9 除的余数。 分析 20≡2(mod9),500≡5(mod9),7000≡7(mod9),??,由于 10n-1=9M,则 10n ≡1(mod9), 故 an×10n≡an (mod9)。 可以考虑把此数变为多项式表示 an×10n+ an-1×10n-1+? + a1×10+a0 后处理。 证明 设 a= anan?1

a1a0 =an×10n+ an-1×10n-1+?+ a1×10+a0,

∵10≡1(mod9),∴10n≡1(mod9), ∴an×10n+ an-1×10n-1+?+ a1×10+a0≡an+ an-1+?+ a1+a0。 说明 要熟练记忆并应用常见的数据模的特征。 例 2.A,B 两人玩一种 32 张扑克牌的取牌游戏,A 先取,以后 轮流进行,每次只 能从剩下的牌中取 1 张,或者质数张牌,谁取到最后一张牌获胜,问:谁有必胜策略? 分析 原有 32 张牌,如果 A 总取奇数张牌,B 只要取 1 张牌,使 A 面临偶数张牌就可 以了,此时 A 总不能取完偶数张牌。但 2 是质数,A 可以取两张牌。注意到 32 是 4 的倍数,

A 只能取奇数张牌或 2 张牌,B 的应对方案稍作调整,可以有必胜的策略。 解 B 有必胜策略。由于 32≡0(mod 4) , 而 A 取的牌不能是 4 及其倍数,从而 A 取后,剩下的牌张数 x≡3(mod 4) ,或 x ≡2(mod 4) ,或 x≡1(mod 4) , 于是 B 可以通过取 1,2 或 3 张牌,使得剩下的牌的张数 y≡0(mod 4) , 所以,B 依次此策略,在 A 取后,剩下的牌张数不同余于 0(mod 4) ,总是有牌, 而 B 取后剩下的牌的张数 y≡0(mod 4) ,从而 B 能取到最后一张牌。 例 3 在已知数列 1,4,8,10,16,19,21,25,30,43 中,相邻若干数之和,能被 11 整除的数组共有多少组。 分析 相邻若干数之和可通过 Sk ? a1 ? a2 ? 现。 解 记数列各对应项为 ai , i ? 1,2, 并记 Sk ? a1 ? a2 ? 10,

? ak , k ? 1, 2,

, n 中 sm ? st (m ? t ) 来实

? ak ? S1, S2 ,

, S10 依次

为 1、5、13、23、39、58、79、104、134、177 它们被 11 除的余数依次为 1、5、2、1、6、 3、2、5、2、1。由此可得

S1 ? S4 (mod11) ? S10 (mod11), S2 ? S8 (mod11), S3 ? S7 (mod11) ? S9 (mod11)

[来源:学§科§网 Z§X§X§K]

由于 Sk ? S j 是数列 {ai } 相邻项之和,且当 Sk ? S j (mod11) 时 11| Sk ? S j ,则满足条件的数 组有:3+1+3=7 组。 说明 在解题的适当时候取模的运算会使运算量减少,并使过程变得简洁。

情景再现
1.能否把 1,2,??,1980 这 1980 个数分成四组,令每组数之和为 S1,S 2,S 3,S 4 , 且满足 S 2 ? S1,= 10,S3 ? S 2= 10,S 4 ? S3= 10 。 2.两人做一种游戏:轮流报数,报出的数只能是 1,2,3,4,5,6,7,8,9,10,把 两人报出的数连加起来,如果得数是 2003,最后报数的人就获胜.现在甲、乙两人已经依次 报过 3,5,7,5,6,乙再接着报下一个数,那么乙经过动脑筋,发现应该报某一号就有赢 的把握.试问乙应该报哪一号?以后各次报数时乙应如何报数才能保证赢? 3. (前南斯拉夫数学竞赛,1988 年)有 27 个国家参加的一次国际会议,每个国家有两名 代表.求证:不可能将 54 位代表安排在一张圆桌的周围就坐,使得任一国家的两位代表之间 都夹有 9 个人.

B 类例题

[来源:学 +科+网 Z+X+X+K]

例 4.共 1998 个小朋友围坐一圈,从某人开始逆时针方向报数,从 1 报到 64,一直报 下去,直到每人报过 10 次为止. ⑴ 有没有报过 5,又报过 10 的人? ⑵ 有没有报过 5,又报过 11 的人? 分析 报过 5(10)的人的编号模 64 的同余特征是本题的突破口。 解 把这些学生依次编为 1——1998 号. ⑴设既报过 5 又报过 10 的人原编为 x 号,则有 x+1998k≡5 (mod 64) x+1998l≡10(mod 64) ∴ 1998(l-k)≡5(mod 64),即 1998(l-k)=5+64n,这不可能. ⑵ 既报 5 又报 11 的人原来编为 x 号. x+1998k≡5 (mod 64) x+1998l≡11(mod 64) ∴ 1998(l-k)≡6(mod 64),即 14(l-k)=6+64n,?7(l-k)=3+32n,取 n=1,得 l-k=5, 即第 k 圈报 5 的人,第 k+5 圈后报 11, ∵ 1998×5=64×156+6, 这说明前 5 圈报 5 的人共 157 个, 即共有 157 人既报 5 又报 11. 说明 本题是同余在解不定方程(组)上的一个简单应用。 例 5 (1992 年友谊杯国际数学竞赛)求最大的正整数 x ,使得对任意 y∈N ,有 x| ( 7 ? 12y ? 1) 。
y

分析

y y x 最 大 不 超 过 7 ? 12y ? 1 的 最 小 值 18 , 7 ? 12y ? 1 ? 0 ( mod18 )

。 ? 7 y ? 12y ? 1 ? 0 (mod2), 7 y ? 12y ? 1 ? 0 (mod9) 解 由条件, x( | 7+12-1) , x |18, 故 x?18。 下证: 对任意 y∈N, 有 18| ( 7 ? 12y ? 1) 。
y y 事实上, 首先 7 ? 1 是偶数, 所以 2| ( 7 ? 12y ? 1) ; 其次, 当 y=3k (k∈N*) 时, 7 y ? 12y ? 1
y

≡ (7 ) ? 1 ≡ 1 -1≡0(mod 9) ,当 y=3k+1(k∈N*)时, 7 ? 12y ? 1≡ 7 ? (7 ) ? 3 ? 1
3 k
k

y

3 k

≡7+3-1≡0 (mod 9) , 当 y=3k+2 时,7 y ? 12y ? 1≡ 7 2 ? (7 3 ) k ? 3 ? 1≡49-4≡0 (mod 9) 。 故对任意 y∈N*,有 9| 7 y ? 12y ? 1。∵(2,9)=1 所求的 x 为 18 说明 本题中将 7 y ? 12y ? 1模 18 分解为模 2 与模 9 来处理充分观察到 7 模 9 的特征。
n

∴18| 7 y ? 12y ? 1

例 6 试求出一切可使 n ? 2 ? 1 被 3 整除的自然数 n 。
n

分析 3|n ? 2n ? 1 ,则n ? 2n ? 2(mod3) 。对 n 按 6 的同余类分类处理。

解:若3|n ? 2 n ? 1,则n ? 2 n ? 2(mod 3) 考虑到n及2n,则 当n ? 6k ? 1时, ( k ? 0、 1、、 2 ) n ? 2 n ? (6k ? 1) ? 26 k ?1 ? (12k ? 2) ? (3 ? 1) k ? 2(mod 3) 当n ? 6k ? 2时, ( k ? 0、 1、、 2 ) n ? 2 n ? (6k ? 2) ? 26 k ?2 ? (24k ? 8) ? (3 ? 1) k ? 2(mod 3)
当n ? 6k ? 3时, (k ? 0、 1、、 2 ) n ? 2 n ? (6k ? 3) ? 26 k ?3 ? 0(mod 3) 当n ? 6k ? 4时, ( k ? 0、 1、、 2 ) n ? 2 n ? (6k ? 4) ? 26 k ? 4 ? (96k ? 64) ? (3 ? 1) k ? 1(mod 3)

当n ? 6k ? 5时, (k ? 0、 1、、 2 ) n ? 2 n ? (6k ? 5) ? 26 k ?5 ? (6 ? 32k ? 160) ? (3 ? 1) k ? 1(mod 3) 当n ? 6k ? 6时, (k ? 0、 1、、 2 ) n ? 2 n ? (6k ? 6) ? 26 k ?6 ? 0(mod 3) 由上可知当且仅当n ? 6k ? 1, 6k ? 2时,n ? 2 n 能被3整除;
说明 要体会模 6 的选取。 n ? 2 中对 n 按模 3 分类,对 2 按模 2 分类可以分别确定结果,
n
n

所以选择按模 6 分类。

情景再现
4.设 a 为小于 100 的自然数,且 a3+23 能被 24 整除,这样的 a 有多少个? 5.求 10
10 n

除以 13 的余数。

6. 有三堆棋子的个数分别为 19,8,9.现进行如下操作:每次从三堆中的任意两堆中分 别取出 1 个棋子,然后把这 2 个棋子都加到另一堆上去.试问:能否经过若干次这样的操作 使得(1)三堆的棋子数目分别为 2,12,22; (2)三堆棋子的数目均为 12.

C 类例题
例 7(第 20 届 IMO 试题)数 1978n 与 1978m 的最末三位数相等,试求正整数 m 和 n,使 得 n+m 取最小值,这里 n ? m ? 1. 分析 数 1978n 与 1978m 的最末三位数相等等价于 1978n-m≡1(mod1000) ,寻找最小的 n-m 及 m。
n 解 由已知 1978 ? 1078m (mod1000 ),而 1000=8×125,所以

1978n ? 1078m (mod8) 1978n ? 1078m (mod125)

① ②

因 n ? m ? 1 ,且(1978m,125)=1,则由②式知 1978n-m≡1(mod125)③ 又直接验证知,1978 的各次方幂的个位数字是以 8、4、2、6 循环出现的,所以只有 n -m 为 4 的倍数时,③式才能成立,因而可令 n-m=4k.由于. n+m=( n-m)+2m=4k+2m, 因而只需确定出 k 和 m 的最小值. 4 先确定 k 的最小值: 因为 19784= (79×25+3) ≡34≡1 (mod5) , 19784≡34≡6 (mod25) . 4 n-m 4k k 故可令 1978 =5t+1 ,而 5 不整除 t ,从而 0 ≡ 1978 - 1=1978 - 1= ( 5k+1 ) - 1 ≡

k ( k ? 1) ? (5t ) 2 + k ? 5t (mod125) ,显然,使上式成立的 k 的最小值为 25. 2
再确定 m 的最小值:因 1978≡2(mod8) ,则由①式知, 2 n ? 2 m (mod8) 由于 n ? m ? 1, ④式显然对 m=1,2 不成立,从而 m 的最小值为 3. 故合于题设条件的 n+m 的最小值为 106. 说明 此例中我们用了这样一个结论:1978 的各次方幂的个位数字是以 8,4,2,6 循环 出现,即,当 r=1,2,3,4 时, 1978 ? 1978
p 4q?r



? 8,4,2,6(mod10). 这种现象在数学

上称为“模同期现象”.一般地,我们有如下定义: 整数列 ?xn ? 各项除以 m(m?2,m∈N*)后的余数 an 组成数列 ?an ? .若 ?an ? 是一个周期 数列,则称 ?xn ? 是关于模 m 的周期数列,简称模 m 周期数列.满足 an?T ? an (或 an?T ? xn (modm) )的最小正整数 T 称为它的周期. 例 8 (第 29 届 IMO 预选题)设 a 是方程 x ? 3x ? 1 ? 0 的最大正根,求证:17 可以
3 2

整除[a1788]与[a1988].其中[x]表示不超过 x 的最大整数.
n 分析 探求 ? ?a ? ? 是本题的关键,而 a 的值无法准确计算得到。所以本题通过韦达定理寻 n 求了 ? ?a ? ? 的递推形式。

证明 根据如下符号表可知,若设三根依次为 ? ? ? ? a ,

则 ?1 ? ? ? ?

1 1 , ? ? ? 1, 2 2
1 2 1 2
+

x f(x)符号
[来源:Z*xx*k.Com]

-1 -



1 -

2 3
网]

[来源:学§科§

3 +

+



2 2 ? a,由于f (?? ) ? ?2? 3 ? (? 3 ?2? 2 ? 1) ? ?2? 3 ? 0,
于是 ? ? ? ? ,| ? |? ? 。

另一方面,由韦达定理知,

? 2 ? ? 2 ? (? ? ? )2 ? 2?? ? (3 ? a )2 ?

2 2 ? 6a 2 ? a 3 ? 9 ? ?2a ? a ? 1 ? (8 ? a 2 ) ?9? a a a
3 3

? a 2 ? (2 2 ) 2 ? 8,?? 2 ? ? 2 ? 1.
为了估计[ a
1788

]、[ a

1988

],先一般考察[an],为此定义:

un ? ? n ? ? n ? a n .(n ? 0,1,2,?)
直接计算可知:

u0 ? 3, u1 ? 2 ? ? ? a ? 3.u2 ? ? 2 ? ? 2 ? a 2 ? 9,以及un?3 ? 3un?2 ? n(n ? 0).
又因

0 ? ? n ? ? n ? 1(? | ? |? ? ,即? n ? ? n ? 0, 又? ? ? ? 3 ? ? ? 2 ? 2 2 ? 1, 当 n ? 2 时,

? n ? ? n ?| ? |n ?? n ? ? 2 ? ? 2 ? 1), 则an ? un ? (? n ? ? n ) ? un ? 1 ? [1 ? (? n ? ? n )].
?[a n ] ? un ? 1.(n ? 1,2,?)
由此知,命题变为证明: u1788 ? 1和u1988 ? 1能被 17 整除. 现考察 ?u n ? 在模 17 的意义下的情况:

u0 ? 3, u1 ? 3, u2 ? 9, u 3 ? 7, u4 ? 1, u5 ? 11, u6 ? 9,,

u 7 ? 9, u8 ? 16, u9 ? 5, u10 ? 6, u 11 ? 2 u12 ? 1, u13 ? 14, u14 ? 6,u15 ? 0, u16 ? 3, u17 ? 3, u18 ? 9,??
可见,在模 17 意义下, ?u n ? 是 16 为周期的模周期数列,即 u n?16 ? u n (mod 17).由于 1788 ? 12(mod16),1988 ? 4(mod16),

故u1788 ? u12 ? 1(mod17), u1988 ? u4 ? 1(mod17),
故 u1788 ?1 ? 0, u1988 ? 1 ? 0(mod 17). 命题得证. 说明 本题利用导数估计了根的分布,递推式的构造需要仔细体味。

情景再现
7 .设三角形的三边长分别是整数 l , m, n, 且 l ? m ? n. 已知 ?

?x? ? x ? ? x? 而 ? x ? 表示不超 过 x 的最大整数.

? 3l ? ? 3m ? ? 3n ? ? ? 4 ? ? ? 4 ? 其中 4? 10 ? ? ?10 ? ?10 ?

求这种三角形周长的最小值.

习题 17
A
6 k ?1 ? 36 k ?1 ? 56 k ? 1 能被 7 整除; 1.证明对于任何整数 k ? 0 , 2

2.试判断 1971 ? 1972 ? 1973 能被 3 整除吗?
26 27 28

3.求 14+24+34+?+20044 的末位数。 4.试证:对一切正整数 n, an ? 5n ? 2 ? 3n?1 ? 1 能被 8 整除。

B
5.设 p ? p1 p2 ........ pn 是最初的几个质数的乘积,这里 n ? N * , n ? 2 。证明 p-1 和 p+1 都不是完全平方数。 6.设 a,b,c,d 是 4 个整数,证明:差 b-a,c-a,d-a,c-b,d-b,d-c 的积能 被 12 整除。 7.正整数 n 满足:十进制表示下 n 的末三位数为 888,求满足条件的最小的 n 值 。 8.在每张卡片上各写出 11111 到 99999 的五位数,然后把这些卡片按任意顺序排成一列,证 明所得到的 444445 位数不可能是 2 的幂;
3

C

9.在 1,2,3,?1989,?1994 中最多可以取多少个数,使得所取的 数中任意 3 个数之和能被 18 整除。 10.给出一个数 198519841983?654321,它是由大到小依次写出自然数 1985、1984、?、 直到写出 3、2、1 后连接成一个数而成,现从其首位起,把首位数字乘以 2 加上第二位数 字,把结果再乘以 2 后加上第三位数字,再把结果乘以 2 后加上第四位数字,?,这样一 直算下去,直到个位数字为止,于是得到一个新的数,把新的数再按上述方法做一次,又 得第二个数,?这样一直做下去,直到得到一个一位数为止,问得到的一位数是多少? 11.设 a,b,c 是三个互不相等的正整数,求证:a3b-ab3,b3c-bc3,c3a-ca3 三个数中,至 少有一个数能被 10 整除. 12.连结正 n 边形的顶点,得到一个闭的 n 年折线形,证明:当 n 为 偶数,则在连线中有两条平行线。

“情景再现”解答:
1. 依题意可知:T ? S1 ? S2 ? S3 ? S4

=S1 ? S1 ? 10 ? S1 ? 20 ? S1 ? 30
?T ? 4 S1 ? 60 ? 0(mod 4) 1980 ? 1981 ? 990 ? 1981 ? 2(mod 4) 2.解:3+5+7+ 2 ? 产生矛盾, ? 不能这样分组; 又 T ? 1? 2 ? 3? ? 1980 ?
5+6=26, 2003≡1(mod 11),26+x≡1(mod 11)?x=8,即只要报 8. 以后每次甲报 k 时,乙就报 11-k 即可. 3.将 54 个座位按逆时针由 1 开始编号:1,2,3,?? 如果满足要求的排法存在,则不妨设 1 和 11 是同一国的代表,从而 11 和 21 不是同一 国的代表,故 21 和 31 是同一国家代表.进一步可以得出: 20 k ? 1 和 20k ? 11 是同一 国家的代表(若 20 k ? 1 和 20k ? 11 大于 54,则取它们被 54 除的余数为号码的位置, 比如 61 即等同于 7) . 特别地,取 k ? 13 时,261 和 271 是同一国家的代表,然而

261 ? 45 ? mod54? , 271 ? 1? mod54? .
即 1 和 45 是同一国家的代表,与 1 和 11 是同一国家的代表矛盾.命题得证. 4. a3+23=a3-1+24, ∴a3-1≡0 (mod 24), ∴3|a3-1,8|a3-1. 由 a≡0,1,2 (mod 3)得 a3≡0,1,2 (mod 3);

若 a 为偶数,则 a 3≡0 (mod 8),若 a 为奇数,则 a2≡1,故 a3≡a (mod 8). 从而 a≡1 (mod 24); 于是 a=1,25,49,73,97,共有 5 个数. 5. 1001≡0(mod13) 108≡1000≡-1(mod13) 106≡1(mod13) 10≡4(mod13) 102≡16≡10(mod6) 103≡102≡10(mod6) 10n≡10n-1≡?≡10≡4(mod6) 10n=6k+4 ∴ 10
10n

≡106k+4≡(106)k×104≡1k×104≡104≡3(mod13)

6. (1) ?19,8,9? ? ? 21,7,8? ? ? 23,6,7? ? ? 22,5,9?

? ? 24,4,8? ? ? 23,3,10? ? ? 22,2,12? .
(2)不可能完成.由于每次操作后,每堆棋子数目或者减 1,或者加 2,不妨写为

? a, b, c ? ? ? a ?1, b ?1, c ? 2? .
若 a, b, c 被 3 除的余数均不相等,则操作后得到的三个数 a ? 1 , b ? 1 , c ? 2 被 3 除 的余数的变化为 ?1, 2,0? ? ? 0,1, 2? ,? 0, 2,1? ? ? 2,1,0? ,? 0,1, 2? ? ? 2,0,1? . 也就 是说,每次操作后不改变三个数被 3 除的余数互不相等这样一个事实. 由于一开始给的三个数被 3 除的余数各不相等,而所要求达到的结果被 3 除的余数都 为 0,故不能完成. 7. 由题设可知
l

3l ? 3l ? 3m ? 3m ? 3n ? 3n ? ? ? 4 ?? 4?? 4 ?? 4?, 4? 104 ? ? 10 ? 10 ? 10 ? 10 ? 10 ?
m n 4

?3l ? 3m ? 3n (mod 24 ) ? 于是 3 ? 3 ? 3 (mod10 ) ? ? l m n 4 ? ?3 ? 3 ? 3 (mod 5 )
由于(3,2)=(3,5)=1,∴由①可知 3
u 4 l ?n

(1) (2)
v 4

?3

m ?n

(mod 2 ) .

4

现在设 u 是满足 3 ? 1(mod 2 ) 的最小正整数,则对于任意满足 3 ? 1(mod 2 ) 的正整

u v ,即 u 整除 v.事实上,若 u 不整除 v , 则由带余除法可知,存在非负整数 a 及 b , 使得 v ? au ? b ,其中 0 ? b ? u ? 1 。
数 v ,我们有 从而可以推出 3 ? 3 到
b b? au

? 3v ? 1(mod 24 ),而这显然与 u 的定义矛盾, 所以 u v . 注意

3u ? 3(mod 24 ),32 ? 9(mod 24 ),33 ? 27 ? 11(mod 24 ),34 ? 1(mod 24 ) , 从 而 可 以 设
m ? n ? 4k ,其中 k 为正整数.
同理可由推出 3
m? n

? 1(mod54 ) .故 34k ? 1(mod54 ) .

现在我们求满足 3

4k

? 1(mod54 ) 的正整数 k .
4k 4 k 4

4 4 因为 3 ? 1 ? 5 ? 2 ,所以 3 ?1 ? (1 ? 5 ? 2 ) ?1 ? 0(mod5 )

k (k ? 1) 2 8 k (k ? 1)(k ? 2) 3 12 ?5 ?2 ? ?5 ?2 2 6 即 k (k ? 1)(k ? 2) 3 11 ? 5k ? 52 k[3 ? (k ? 1) ? 27 ] ? ? 5 ? 2 ? 0(mod 54 ) 3 k ( k ? 1)( k ? 2) 2 11 k ? 5k[3 ? (k ? 1) ? 27 ] ? ? 5 ? 2 ? 0(mod 53 ) 3 或 5k ? 24 ?
即有 k ? 5t ,并代入该式得 t ? 5t[3 ? (k ?1) ? 2 ] ? 0(mod5 )
7 2

即有 t ? 0(mod5 ) .
2
3 即 k ? 5t ? 5 s ,其中 s 为正整数,

故 m ? n ? 500s ,s 为正整数. 同理可以证得 l ? n ? 500r , r 为正整数. 由于 l ? m ? n. ,所以有 r ? s . 这样一来 , 三角形的三个边为 500r ? n,500s ? n 和 n . 由于两边之差小于第三边 , 故

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

“习题”解答:

A
1. 令M ? 2
6 k ?1

? 36k ?1 ? 56k ? 1

? M ? 2 ? 26k ? 3 ? 36k ? 56k ? 1
k ? 2 ? 64k ? 3 ? 729k ? 15625 ?1

? 2 ? (7 ? 9 ? 1) k ? 3 ? (7 ? 104 ? 1) k ? (7 ? 2232? 1) k ? 1 ? 2 ? 7 ? A ? 2 ? 3? 7 ? B ? 3 ? 7 ?C ?1?1 ? (2 ? 3 ? 1 ? 1)(mod7) ? 0(mod7)

? 对于?k ? 0, 且k ? Z , 2 6 k ?1 ? 36 k ?1 ? 56 k ? 1 都能被 7 整除;
2. 1971 ? 0(mod 3),1972 ? 1(mod 3),1973 ? 2(mod 3)

?197126 ? 197227 ? 197328 ? (026 ? 127 ? 2 28 )(mod 3) 即: 197126 ? 197227 ? 197328 ? (1 ? 2 28 )(mod 3) 又 228 ? 414 ? 1(mod 3),? (1 ? 2 28 ) ? 2(mod 3) ?197126 ? 197227 ? 197328 不能被3整除;
3.解:记 14+24+34+?+20044=N,设 N 的末位数为 a,则 N≡a(mod 10) ∴N4≡a4(mod 10)

∵14≡1(mod 10) 24≡6(mod 10) 34≡1(mod 10) 44≡6(mod 10) 54≡5(mod 10) 64≡6(mod 10) 74≡1(mod 10) 84≡6(mod 10) 94≡1(mod 10) ∴14+24+34+?+20044≡200× (14+24+34+?+104) +14+24+34+44≡14≡4 (mod 10)即末位数为 4
2 4.证明:若 k 为奇数,则 k ? ?1 或±3(mod 8), k ? 1 (mod8)

∴当 k 为奇数 若 n 为正奇数,

k 2 n ? 1 (mod 8),∴ 52m ? 32m ? 1 (mod 8)

a n ? 5 ? 5n?1 ? 2 ? 3n?1 ? 1 ? 5 ? 2 ? 1 ? 0 (mod 8)
若 n 为正偶数, an ? 5n ? 2 ? 3 ? 3n?2 ? 1 ? 1 ? 6 ? 1 ? 0 (mod 8) ∴得证.

B
5.对任意 x ? Z , x ? 0, ?1 (mod 3) 所以 x ? 0 或 1(mod 3)
2

而 3︱p 故 p-1 ? 2 (mod 3) ? p-1 不是完全平方数 又 p2, .....,pn 都是奇数,设 p2 ..... pn =2 k+1. 则 p ? 2(2k ? 1) ? 2 (mod 4) ,而完全平方数 ? 0 或 1(mod 4), p ? 1 ? 3 (mod 4)

? p ? 1 不是完全平方数。
6.考虑这 4 个数模 4 的结果,如果有某两个数对于模 4 同余,则这二数是 4 的倍数,如 果这 4 个数对于模 4 没有两数同余,则这四数必两奇两偶,奇偶相同二数的差能被 2 整 除,于是其积是 4 的倍数,即得。 再考虑这 4 个数模 3 的结果,由于任何整数模 3 后只能与 0,1,2,这三个数同余,则 必有二数对于模 3 同余,这二数的差能被 3 整除。 综上即得。 7.依题意,知 n ? 888 (mod1000)故 n 的末位数字为 2,设 n=10k+2,
3

则分别有 600k ? 120k ? 8 ? 888(mod5 )
2 3

即 15k ? 3k ? 22 ? ?3 (mod25)
2
2 故 25 5k ? k ? 1 ,所以 5 k ? 1 2

设 k ? 5m ? 4 ,则 25 5 ? 4 ? 5m ? 5

即 5 m ? 2 ,所以 m=5r+3. 则 n=500r+192 ∴最小的 n 为 192

11111、 11112、 8. 记由

、 99999排成的数为A,则:

A=a1a2

a88889 , ai ? {11111、 11112、

、 99999} ? a88888 ? 105 ? a88889

? A=a1 ? 10444440 ? a2 ? 10444435 ? a3 ? 10444430 ?

注意到105 ? 1(mod11111) ?105k ? 1(mod11111), k ? Z ? A ? a1 ? a2 ? ? a88888 ? a88889 (mod11111) 又 ? a1 ? a2 ? ? a88888 ? a88889 ? 11111 ? 11112 ? ? 99999 11111 ? 99999 ? 88889 2 即:a1 ? a2 ? ? a88888 ? a88889 ? 11111 ? 5 ? 88889 ? A ? 0(mod11111) ? A不可能是2的幂;

C
9.设 a,b,c,d 是取出来的数中任意四个,由 a+b+c=18n,a+b+d=18m,18|(c -d) ,即取出的数对摸 18 的余数相同,设为 k, 则 a+b+c≡3k(mod18) k=0,6,12。 而 1994=18×110×14 最多有 6,24,42,?1986 或 12,30,48,?1992 共 111 个数满足。

10.解 设所给数为 A,则 A 被 8 除的余数与 321 被 8 除的余数相同,但 321=3×100+2× 10+1≡3×4+2×2+1(mod 8) ,又设 第一次运算 得到的数 为 B , 而 B 被 8 除的 余数与 (3×2+2)×2+1 被 8 除的余数相同(A 的千位以上的数字在运算过程中均乘以 2n , 其中 n?3)。 即 B 被 8 除的余数与 A 被 8 除的余数相同。对 B 的各位数字进行运算的结果记为 C,同理 可知,C 被 8 除的余数与 B 被 8 除的余数相同,?,依此类推,知最后所得的一位数被 8 除的余数与 A 被 8 被的余数相同, 即余 1。 而此一位数由两个自然数相加而得, 故不等于 1, 从而,该一位数为 9。 11.证明 a3b-ab3=ab(a+b)(a-b);b3c-bc3=bc(b+c)(b-c);c3a-ca3=ca(c+a)(c-a). ⑴ 若 a≡0(mod 2)或 b≡0(mod 2),则 ab(a+b)(a-b)≡0(mod 2);

若 a≡1(mod 2)且 b≡1(mod 2),则 a+b≡0(mod 2)且 a-b≡0(mod 2) 于是 ab(a+b)(a-b)≡0(mod 2);总之,a3b-ab3≡0(mod 2), 同理 b3c-bc3≡0(mod 2),c3a-ca3≡0(mod 2). ⑵ 若 a≡0(mod 5),则 ab(a+b)( a-b)≡0(mod 5)且 ca(c+a)(c-a)≡0(mod 5), 故可知,当 a≡0,或 b≡0,或 c≡0(mod 5)时,考察 a3b-ab3,b3c-bc3,c3a-ca3 这三个数中,至少有 2 个能被 5 整除. 当 a ? 0(mod 5)且 b ? 0(mod 5)且 c ? 0(mod 5)时, ①若 a≡b(mod 5),则 a-b≡0(mod 5),于是 ab(a+b)(a-b)≡0(mod 5). 同理若 b≡c(mod 5),则 bc≡0 (b+c)(b-c) (mod 5); 若 c≡a(mod 5),则 ca(c+a)(c-a)≡0(mod 5). ②若 a ? b,b ? c,c ? a,则取 M={1,4},N={2,3}两个集合. 由于 a、b、c 被 5 除的余数互不相等且只能是 1,2,3,4 中的某 3 个,故必存在两个 数,它们被 5 除的的余数或同属于 M,或同属于 N,不妨设 a、b 这两个数被 5 除的余数 属于同一集合,则 a+b≡0(mod 5). 总之,a3b-ab3,b3c-bc3,c3a-ca3 三个数中,至少有 1 个能被 5 整除. 综上可知,a3b -ab3,b3c-bc3,c3a-ca3 三个数中,至少有一个数能被 10 整除. 12.依逆时针顺序将顶点标上 0,1,?n-1,问题中的闭折线可用 n 个数的一个排列 A0,A1,A2,?An-1,An=A0 唯一地表示,且 AiAi+1//AjAj+1

? Ai ?1 A j = A j ?1 Ai ? Ai+Ai+1≡Aj+Aj+1(mod n)
n 为偶数,2 不能整除(n-1) 模 n 的非负最小完全剩余系之和满足 n(n-1) ? / 0(mod n) 0+1+?+(n-1)= 2 另一方面

?(A ? A
i ?0 i

n ?1

i ?1

) =2 ? Ai ≡2×
i?0

n ?1

n(n-1) ≡n(n-1)≡0(mod n) 2

∴Ai+Ai+1(i=0,?,n-1)不能构成 n 的完全剩余后,必有 i≠j,使 Ai+Ai+1≡Aj+Aj+Aj+1 (mod n)得证。

学科网

[来源:Z,xx,k.Com]

w。w-w*k&s%5¥u 学科网 w。w-w*k&s%5¥u


相关文章:
2012江苏省数学竞赛《提优教程》第22讲_三角恒等变换 (1)
2012江苏省数学竞赛《提优教程》第22讲_三角恒等变换 (1)_数学_高中教育_教育专区。三角恒等变换本专题涉及到的知识点是两角和差的正余弦、正切公式;二倍角公式...
2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖
2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖_学科竞赛_高中教育_教育专区...A1A3?sin36 2 A3 A A4 1 2sin18o = 2 = 5?1 5?1 综上可知,μ5 ...
2012江苏省数学竞赛《提优教程》第63讲_极限
极限及其运算 相关知识 1.数列极限的定义: 一般地,如果当项数 n 无限增大时,无穷数列 {an } 的项 an 无限趋近于 某个常数 a (即... ,那么就说数列 {...
2012江苏省数学竞赛《提优教程》教案:第62讲__多项式
2012江苏省数学竞赛《提优教程》教案:第62讲__多项式_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 2012江苏省数学竞赛《提优教程》教案:第...
2012江苏省数学竞赛《提优教程》教案:第35讲_整数性质
2012江苏省数学竞赛《提优教程》教案:第35讲_整数性质_学科竞赛_高中教育_教育...n2- 36 是 13 的倍数,则 13 除 n2+5n+23=n2-36+65k+59±25 的余数...
2012江苏省数学竞赛《提优教程》教案:第30讲__数列的求和
2012江苏省数学竞赛《提优教程》教案:第30讲__数列的求和_学科竞赛_高中教育_教育专区。第 11 讲 数列的求和 本节主要内容有 Sn 与 an 的关系;两个常用方法...
2012江苏省数学竞赛《提优教程》教案:第05讲 子集
2012江苏省数学竞赛《提优教程》教案:第05讲 子集_学科竞赛_高中教育_教育专区。第 5 讲 子集本讲内容有子集、子集的个数、集合的划分及子集的应用。 设 ...
2012江苏省数学竞赛《提优教程》教案:第30讲--数列的求和
2012江苏省数学竞赛《提优教程》教案:第30讲--数列的求和_学科竞赛_高中教育_教育专区。第 11 讲 数列的求和 本节主要内容有 Sn 与 an 的关系;两个常用方法...
2012江苏省数学竞赛《提优教程》第06讲 函数的概念(新)
2012江苏省数学竞赛《提优教程》第06讲 函数的概念(新)_数学_高中教育_教育专区。第 6 讲函数的概念本节主要内容有映射与函数的概念,函数的定义域和值域的求法...
2012江苏省数学竞赛《提优教程》教案:第31讲_数列的递推
2012江苏省数学竞赛《提优教程》教案:第31讲_数列的递推_学科竞赛_初中教育_教育专区。第 12 讲 数列的递推 本节主要内容两个基本递推:an+1=an+d,an=qan...
更多相关标签:
江苏省数学竞赛初赛 | 江苏省化学竞赛初赛 | 江苏省高等数学竞赛 | 江苏省高中数学竞赛 | 江苏省化学竞赛 | 江苏省数学竞赛 | 2017江苏省生物竞赛 | 江苏省生物竞赛 |