高中数学竞赛专题讲座专题训练

竞赛试卷 同余的概念与应用 概念与性质 1. 定义: 若整数 a,b 被整数 m(m≥1)除的余数相同,则称 a 同余于 b 模 m,或 a,b 对模 m 同余.记为 a≡b(modm). 余数 r:0≤r<1. 2. 性质:(ⅰ)a≡b(modm) ? m|a-b,即 a=b+mk,k∈Z. (ⅱ)若 a≡b(modm),b≡c(modm),则 a≡c(modm). (ⅲ)若 a1≡b1(modm),a2≡b2(modm),则 a1± a2≡b1± b2(modm),a1a2≡b1b2(modm); n n-1 n (ⅳ)设 f(x)=anx +an-1x +…+a1x+a0,g(x)=bnx +bn-1xn-1+…+b1x+b0 是两个整系数多项式,满足 ai≡ bi(modm)(0≤i≤n).若 a≡b(modm),则 f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm) ? a≡b(mod m ), (c, m ) (ⅵ)若 m≥1,(a,m)=1,则存在整数 c 使得 ac≡1(modm).称 c 为 a 对模 m 的逆或倒数,记为 c=a-1(modm); (ⅶ) ? ?a ? b(modm1 ) 同时成立 ? a ? b (mod[m1,m2]);(ⅷ)若 a≡b(modm1),a≡b(modm2),且(m1,m2)= a ? b (mod m ) 2 ? 1,则 a≡b(modm1m2). 3. 剩余类:设 m 为正整数,把全体整数按对模 m 的余数分成 m 类,相应 m 个集合记为:K0,K1,…,Km-1, 其中 Kr={qm+r|q∈Z,0≤余数 r≤m-1}称为模 m 的一个剩余类。 性质:(ⅰ) Z ? 0 ?i ? m ?1 ? K i 且 Ki∩Kj=φ(i≠j). (ⅱ)每一整数仅在 K0,K1,…,Km-1 一个里. (ⅲ)对任意 a、b∈Z,则 a、b∈Kr ? a≡b(modm). 4. 完全剩余系:设 K0,K1,…,Km-1 为模 m 的全部剩余类,从每个 Kr 里任取一个 ar,得 m 个数 a0,a1,…,am-1 组成的数组,叫做模 m 的一个完全剩余系。0,1,2,…,m-1 叫做模 m 的最小非负完全剩余系。 性质:(ⅰ)m 个整数构成模 m 的一完全剩余系 ? 两两对模 m 不同余。 (ⅱ)若(a,m)=1,则 x 与 ax+b 同时跑遍模 m 的完全剩余系。 5. 既约剩余系:如果 Kr 里的每一个数都与 m 互质,则 Kr 叫与 m 互质的剩余类,在与模 m 互质的全部剩 余类中,从每一类任取一个数所做成的数组,叫做模 m 的一个既约剩余系。 性质:(ⅰ)Kr 与模 m 互质 ? Kr 中有一个数与 m 互质; (ⅱ)与模 m 互质的剩余类的个数等于 ?( m ) ; (ⅲ)若(a,m)=1,则 x 与 ax+b 同时跑遍模 m 的既约剩余系。 (ⅳ)设(a,p)=1,则 d0 是 a 对于模 p 的阶 ? ado≡1(modp),且 1,a,…,ado-1 对模 p 两两不同余.特别地,do= Φ(p) ? 1,a,…,aΦ(p)-1 构成模 p 的一个既约剩余系. 例 1. 设 xi∈{-1,1},i=1,2,…,101,证明:x1+2x2+…+100x101≠0. 证明:∵x1+2x2+…+100x101≡1+2+…+101≡51≡1(mod2)∴成立. 例 2. 设 p 为质数.求证: Cn p ?n? ? ? ?(mod p) . ? p? ? n ? n?i ?? p p ? ? .∴n(n- 证明:∵n≡0,1,2,…,p-1(modp)∴必有某一个 i(0≤i≤p-1)使得 n≡i(modp),从而 ? p 1)…(n-i+1)(n-i-1)…(n-p+1)≡i(i-1)…1(p-1)…(i+1)≡(p-1)!(modp),∴(p-1)! C n =(p-1)!n(n-1)…(n-i+1)(n-i- 竞赛试卷 1)…(n-p+1) n?i ?n? n?i n?i n?i p p ? ? ?(mod p ≡(p-1)! (modp),即(p-1)! C n ≡(p-1)! (modp),因((p-1)!,p)=1∴ Cn ? p! p p p ? p? p n ? n?i ?n? ? ? ?(mod p) . p ? p? 例 3. 设 m>0,证明必有一个仅由 0 或 1 构成的自然数 a 是 m 的倍数. 证明: 考虑数字全为 1 的数:1,11,111,1111,…中必有两个在 modm 的同一剩余类中,它们的差即为所求 的 a. 例 4. 证明从任意 m 个整数 a1,a2,…,am 中,必可选出若干个数,它们的和(包括只一个加数)能被 m 整除. 证明:考虑 m 个数 a1,a1+a2,a1+a2+a3,…,a1+a2+…+am,如果其中有一个数能被 m 整除,则结论成立,否 则,必有两个数属于 modm 的同一剩余类,这两个数的差即满足要求. 例 5. 证明数 11,111,1111,…中无平方数. 证明: 因任意整数 n2≡0 或 1(mod4),而 11≡111≡1111≡…≡3(mod4),所以,数 11,111,1111,…中无平方数. 例 6. 确定 n5=1335+1105+845+275. 解:因 n5≡35+05+45+75≡3+4+7≡4(mod10),所以 n 个位数字为 4,显然 n 的首位数字为 1,进一步估 5 ?5? 5 计:n <2×133 +(84+27) <3×133 < ? ? ? 133 ,所以,n< ? 133 <167,所以 n 可取 134,144,154,164,又 4 ? 4? 5 5 5 5 5 n5≡15+(-1)5≡3(mod3),故 n=144. 注:欧拉猜测 4 个自然数的 5 次方之和不是 5 次方,于 1962 年被

相关文档

高中数学竞赛专题讲座之基本知识
高中数学竞赛专题训练
高中数学竞赛专题讲座
竞赛→高中竞赛→专项训练→高中数学竞赛专题讲座——集合与函数
高中数学竞赛专题讲座---专题训练 (同余部分的例题与习题)
高中数学竞赛专题讲座之 数列
高中数学竞赛专题讲座——数列
高中数学竞赛专题讲座之函数的基本性质
高中数学竞赛专题讲座之 解析几何
高中数学竞赛专题讲座(解析几何)
电脑版