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

第三讲 同余


初等代数选讲-----第三讲

第三讲

同余

同余的性质应用非常广泛,在处理某些整除性、进位制、对整数分类、解不定方程等方 面的问题中有着不可替代的功能, 与之密切相关的的数论定理有欧拉定理、 费尔马定理和中 国剩余定理。 对于任何正整数均有定义的函数,称为数论函数。在初等数论中,所能用到的无非也就 三个, 分别为:

高斯(Gauss)取整函数[x]及其性质, 除数函数 d(n)和欧拉(Euler)函数 ? ( x) 以及它们的计算公式。 1. 高斯(Gauss)取整函数[ x ] 设 x 是实数, 不大于 x 的最大整数称为 x 的整数部分, 记为[ x ];x ? [ x] 称为 x 的小数部分, 记为{ x } 。例如: [0.5]=0, [ 50] ? 7,[?3] ? ?3,[?? ] ? ?4,{? } ? 0.1415 ?,{?0.3} ? 0.7 等等。 由 [ x],{x} 的定义可得如下性质: 性质 1. 0 ? {x} ? 1 ; 性质 2. x ? 1 ? [ x] ? x ? [ x] ? 1 ; 性质 3.设 a ? Z ,则 [a ? x] ? a ? [ x] ; 性质 4. [ x ? y] ? [ x] ? [ y] ; {x ? y} ? {x} ? { y} ; 性质 5. [? x] ? ?

? ? [ x] ?? [ x] ? 1

x?Z x?Z



性质 6.对于任意的正整数 n ,都有如下的厄米特恒等式成立:

1 2 n ?1 [ x] ? [ x ? ] ? [ x ? ] ? ? ? [ x ? ] ? [nx ] ; n n n

1

初等代数选讲-----第三讲

2. 除数函数 d( a ) 由整数唯一分解定理:任何大于 1 的整数 a 的标准分解式为:
a2 a ? p1a1 p2 ak pk , i ? 1, 2,

,k

(1)

其中 pi 为质数, pi ? p j (i ? j ) ,正整数 a 的正因数的个数称为除数函数,记为 d( a ). 推论 1. 若 a 的标准分解式是(1)式,则 d 是 a 的正因数的充要条件是:
?2 d ? p1?1 p2 ?k pk ,0 ? ?i ? ai , i ? 1, 2,,

,k

(2)

说明: (2)式不能称为整数 d 的标准分解式,由于其中的某些 ? i 可能取零值( d 如果不含 某个素因数 pi ,则 ? i ? 0 ). 除数函数计算公式如下:

d( a )= (?1 ? 1)(?2 ? 1)

(?k ? 1) , ?1 , ? 2 ,

, ? k 为 a 的标准分解式中的指数.

推论 2. 设 a ? bc ,且 (b, c) ? 1 ,若 a 是整数的 k 次方,则 b, c 也是整数的 k 次方。 特别地,若 a 是整数的平方,则 b, c 也是整数的平方。 3. 欧拉(Euler)函数 ? (n)

n 个整数 0,1,……, n ? 1 中与 n 互素的数的个数,称之为 n 的欧拉函数,记为 ? (n) .
欧拉函数的计算公式如下: 若 n 的标准分解式是 n ? p1 1 p2 2
a a ak pk , i ? 1, 2 ,

, k ,则 ? (n) 的计算公式是:

2

初等代数选讲-----第三讲

a ?1 ? (n) ? p1a ?1 p2
1 2

ak ?1 pk ( p1 ? 1)( p2 ? 1)

( pk ? 1)=n ?

P|n P为质数

. ?(1- P )

1

例如: ? (2000) ? ? (2453 ) ? 2352 (2 ?1)(5 ?1) ? 800 ;

?( 2 0 0 1 ?)? ?( 3 ? 2 3 ? 2 9? )
下面我们学习同余的内容:

( 3? 1 ) ( 2 ? 3 ?1 ) ( 2 .9 1 )

1232

定义 1. 设 m 是正整数, 若用 m 去除整数 a , b , 所得的余数相同, 则称 a 与 b 关于模 m 同余,记作 a ? b(modm) ,否则称 a 与 b 关于模 m 不同余,记作 a

b(modm) .例如:

34 ? 4(mod 15) , 1000? ?1(mod7) , 9

8(mod 2) 等等。

当 0 ? b ? m 时, a ? b(modm) ,则称 b 是 a 对模 m 的最小非负剩余。 对于固定的模 m ,通常有下面的性质: 性质 1. a ? b(modm) 的充要条件是 a ? mt ? b, t ? Z 也即 m | (a ? b) 。 性质 2.同余关系满足以下规律: (1) (反身性) a ? a(modm) ; (2) (对称性)若 a ? b(modm) ,则 b ? a(modm) ; (3) (传递性)若 a ? b(modm) , b ? c(modm) ,则 a ? c(modm) ; (4) (同余式相加)若 a ? b(modm) , c ? d (modm) ,则 a ? c ? b ? d (modm) ; (5) (同余式相乘)若 a ? b(modm) , c ? d (modm) ,则 ac ? bd(modm) ; 注意: ① 反复利用(4) (5) ,可以对多于两个的(模相同的)同余式建立加、减和乘法的运 算公式 ; ② 特 别 地 , 由 ( 5 ) 易 推 出 : 若 a ? b(modm) , k , c 为 整 数 且 k ? 0 , 则

a k c ? b k c(modm) ;
③ 同余式的消去律一般并不成立,即从 ac ? bc(modm) 未必能推出 a ? b(modm) , 可是我们却有以下结果:若 ac ? bc(modm) ,则 a ? b? ? mod

? ?

m ? ?. (m, c) ? ?

3

初等代数选讲-----第三讲

由此可以推出: (6)若 (c, m) ? 1, ac ? bc(modm) ,则有 a ? b(modm) ,即在 c 与 m 互素时,可以在原 同余式两边约去 c 而不改变模. (7)若 a ? b(modm) , d | m ,则 a ? b(modd ) ; (8)若 a ? b(modm) , d ? 0 ,则 da ? db(moddm) ; (9)若 a ? b(mod mi )(i ?1,2,

, k) ,则 a ? b(mod [m1, m2 ,

, mk ] ) ,特别地,若
? mk ) ;
m) ;? ai ? ? bi (mod m) ;
i ?1 i ?1 k k

m1 , m2 ,

, mk 两两互素时,则有 a ? b(mod m1 ? m2 ?

性质 3.若 ai ? bi (modm),i ? 1,2,?, k , 则

? a ? ? b (mod
i ?1 i i ?1 i

k

k

性质 4.设 f ( x) 是系数全为整数的多项式,若 a ? b(modm) ,则 f (a) ? f (b)(modm) 。 这一性质在计算时特别有用:在计算大数字的式子时,可以改变成与它同余的小数字,使计 算大大地简化。 整数集合可以按模 m 来分类,确切地说,若 a 和 b 模 m 同余,则 a 和 b 属同一类,否 则不属于同一类,每一个这样的类为模 m 的一个同余类。由带余除法,任一整数必恰与 0,1,……, m ? 1 中的一个模 m 同余,而 0,1,……, m ? 1 这 m 个数彼此模 m 不同余,因此模

m 共有 m 个不同的同余类, 例如,模 2 的同余类共有两个,即通常说的偶数类与奇数类,
这两类中的数分别具有形式 2 k 和 2k ? 1 ( k 为任意整数). 定义 2 (剩余类)设 m 是正整数,把全体整数按对模 m 的余数分成 m 类,相应的 m 个集 合记为:K 0 , K1 ,?, K m?1 , 其中每一个 Kr ? {x | x ? qm ? r , q ? Z} 称为模 m 的一个剩余类 (也称同余类) , r ? 0,1, 定义 3.(完全剩余系) 设 K 0 , K1 ,?, K m?1 为 模 m 的 全 部 剩 余 类 , 从 每 个 K r 中 任 取 一 个 ar , 得 m 个 数

, m ? 1.

a0 , a1 ,?, am?1 组成的数组,叫做模 m 的一个完全剩余系.
例如关于模 7,下面的每一组数都是一个完全剩余系: 0,1,2,3,4,5,6;

4

初等代数选讲-----第三讲

-7,8,16,3,-10,40,20; -3,-2,-1,0,1,2,3。 最常用的完全剩余系是最小非负完全剩余系和绝对值最小完全剩余系. 模 m 的最小非负完全剩余系是:0,1,2,………, m ? 1 ; 当 m 为奇数时,绝对值最小的完全剩余系是: ?

m ?1 m ?1 ,?,?1,0,1,?, ; 2 2

当 m 为偶数时,绝对值最小的完全剩余系有两个:

m m ? 1,?,?1,0,1,?, ; 2 2 m m ? ,?,?1,0,1,?, ? 1 。 2 2 ?
定义 4.(简化剩余系) 在模 m 的完全剩余系中,所有与模 m 互素的数叫做模 m 的简化剩余系,也称既约剩余 系. 注意:简化剩余系不是完全剩余系,只是完全剩余系的一部分,且简化剩余系中数的个数为

? (m).
例如:0、1、2、3、4、5、6、7、8、9 是模 10 的一个完全剩余系,1、3、7、9 是模 10 的 一个简化剩余系,且满足 ? (10)=4 . 几条常用的性质: (1) Z ?

0?i ? m?1

?K

i

,其中 Ki

K j ? ?,(?i ? j,i, j ? 0,1,

, m ? 1) ;

(2)每一个整数只包含于 K 0 , K1 ,?, K m?1 中的一个里; (3)对于任意 a, b ? Z ,则 a, b ? K r 的充要条件是 a ? b(modm) . (4) m 个整数构成模 m 的一个完全剩余系 ? 两两对模 m 不同余; (5)若 x1 , x2 ,

, xm 是模 m 的一个完全剩余系,且 (a, m) ? 1,b ? Z ,则

ax1 ? b, ax2 ? b, , axm ? b 也是模 m 的一个完全剩余系;
(6)若 x1, x2 ,

, x?? m? 是模 m 的一个简化剩余系,且 (a, m) ? 1, 则 ax1 , ax2 ,

, ax? ? m? 也是

模 m 的一个简化剩余系(其中 ? ? m ? 是欧拉函数).

5

初等代数选讲-----第三讲

【练习】
1.试解方程: ?

? 5 ? 6 x ? 15x ? 7 . ? 5 ? 8 ? ?
15x ? 7 ? 5 ? 6 x ? ? 5 ? 6 x 15x ? 7 ? ? ? ? ?? ?0 ? 5 ? 5 ? 8 ? ? 8 ? ?

解:因为左边是整数,因而右边的分式也应该是整数,所以

于是 ? 由于

81 ? 90 x ? 81? 90x ? ? 1 ,故 0 ? 81 ? 90 x ? 40 。 ? 0 ,从而 0 ? ? 40 ? 40 ?

15 x ? 7 是整数,故 15 x ? 5t ? 7 , t ? Z ,代入前面的不等式,得 5 7 4 0 ? 39 ? 30t ? 40, t ? Z ,直接观察即知 t ? 0,1 ,于是 x ? 或 。 15 5

2.试求 (25733 ? 46) 26 被 50 除所得的余数。 解:由于 ( x 33 ? 46) 26 是关于 x 的整系数多项式,而 257 ? 7(mod50) ,于是知

(25733 ? 46) 26 ? (733 ? 46) 26 (mod50) 。
又注意到 7 =49 ? ?1(mod50) ,故 (257 ? 46) ? (7 ? 46)
2

33

26

33

26

? ((7 2 )16 ? 7 ? 46) 26

? ((?1)16 ? 7 ? 46) 26 ? (7 ? 46) 26 ? 5326 ? 326 (mod50)


35 ? 243 ? ?7(mod50) ,

2 2 33 26 5 5 5 所以 (257 ? 46) ? (3 ) ? 3 ? (?7) ? 3 ? ? ? ?(7 ) ? 7 ? 3? ? ? ?21 ? 29(mod 50)

注意到 0 ? 29 ? 50 ,因而 29 就是所求的余数. 说明:在上述过程中,我们已经看到 7 ? 49 ? ?1(mod50) 的作用。一般而言,知道一个整
2

数的多少次幂关于模同余于 ? 1 是非常有用的。 事实上, 若 a ? 1(modm) , 则对大的指数 n
k

利用带余除法定理, 可得 n ? kq ? r ,0 ? r ? k , 于是有 a ? a
n
n

kq?r

? (a k ) q a r ? a r (modm) ,

这里余数 r 是一个比 n 小得多的数,这样一来,计算 a 的问题,就转化成了计算余数 r 次 幂 a 的问题,从而使计算简单化。 3.设 a ? 10
1010
r

,若今天是星期一,计算第 a 天后是星期几?
6

初等代数选讲-----第三讲

解; 星期几的问题是被 7 除求余数的问题。 由于 10 ? 3(mod7) , 于是 102 ? 32 ? 2(mod7) ,

103 ? 33 ? 2 ? 3 ? 6 ? ?1(mod7) ,因而 106 ? 1(mod7) 。
为了把指数 a 的指数 10 写成 6q ? r 的形式,还需取 6 为模来计算 10 。
10 10

为此我们有: 10 ? 4(mod6) ,进而有: 102 ? 42 ? 4(mod6) , 103 ? 43 ? 4(mod6) ,依 次类推有: 1010 ? 4(mod6) ,所以 1010 ? 6q ? 4 .

从而 a ? 106q?4 ? (106 ) q ?104 ? 1q ?104 ? 34 ? 4(mod7) 所以,星期一后的第 a 天将是星期五。 4.数列 {an } 满足: a0 ? 1, an?1 ? (1)对任意 n ? N , an 为正整数;
2 7an ? 45an ? 36

2

, n ? N . 证明:

(2)对任意 n ? N , an an?1 ? 1 为完全平方数。

证明: (1)由题设得 a1 ? 5, 且 {an } 严格单调递增.将条件式变形得:
2 2 2 2a n ?1 ? 7a n ? 45a n ? 36 , 两边平方整理得 an ① ?1 ? 7an an?1 ? an ? 9 ? 0

2 2 ? an ? 7an?1an ? an ?1 ? 9 ? 0



①-②得 (an?1 ? an?1 )(an?1 ? an?1 ? 7an ) ? 0,

an?1 ? an ,?an ?1 ? an ?1 ? 7an ? 0 ?


an?1 ? 7an ? an?1.
由③式及 a0 ? 1, a1 ? 5 可知,对任意 n ? N , an 为正整数. (2)将①两边配方,得 (an ?1 ? an ) ? 9(an an ?1 ? 1),? an an ?1 ? 1 ? (
2

an ?1 ? an 2 ). ④ 3

由③式 an?1 ? an ? 9an ? (an?1 ? an ) ≡ ?(an ? an?1 ) ? mod3? ∴ an?1 ? an ≡ (?1)
n

? a1 ? a0 ? ≡0(mod3)∴

an ?1 ? an 为正整数,④式符合题意. 3

? an an?1 ? 1 是完全平方数.
2 2 5.求所有的素数 p ,使得 4 p ? 1 与 6 p ? 1 也是素数。

分析:要使几个数同为质数,一般是利用某一质数的余数来确定,如 p, p ? 2, p ? 4 均为质 数,由于这是 p 的一次式,故三个数就用模 3 的余数来确定,而二次式对三个数就模 5,四
2 2 个数一般就模 7 了。要使 p , 4 p ? 1 与 6 p ? 1 都是素数,须对 p 除以素数 q ? 5 的余数

7

初等代数选讲-----第三讲

进行分类讨论,最后确定 p 只能是这个素数。 解:设 u ? 4 p 2 ? 1 , v ? 6 p 2 ? 1 ,且 p ? 5k ? r , k ? Z , r ?{0,1, 2,3, 4} 若 r ? 1 或 4 时, p 2 ? 1(mod5) , u ? 4 p 2 ? 1 ? 4 ? 1 ? 0(mod5) ; 若 r ? 2 或 3 时, p 2 ? 4(mod5) , v ? 6 p 2 ? 1 ? 24 ? 1 ? 0(mod5) ; 即 r ? 0 时, u , v 为 5 的倍数且比 5 大,不为质数。故 r ? 0 ,此时 p ? 5 ,

u ? 5 2 ? 4 ? 1 ? 101; v ? 5 2 ? 6 ? 1 ? 151都是素数。
即本题有唯一解 p ? 5 。

8


相关文章:
第三讲 同余
初等代数选讲---第三讲 第三讲 同余 同余的性质应用非常广泛,在处理某些整除性、进位制、对整数分类、解不定方程等方 面的问题中有着不可替代的功能, 与之密切...
第三讲同余的概念和性质
龙岗学校高中数学联赛提高班讲义 和斌涛 2013 年 12 月 10 日 第3讲一、知识要点 同余的概念和性质 1.设 m 是一个给定的正整数,如果两个整数 a 与 b ...
第三讲 同余系列竞赛
Http://www.fhedu.c 【高中数学奥赛金牌之路精华教案】数学奥赛辅导 第三讲 同余 知识、方法、技能同余是数论中的重要概念,同余理论是研究整数问题的重要工作之一....
高中数学奥赛辅导 第三讲 同余
高中数学奥赛辅导 第三讲 同余_学科竞赛_高中教育_教育专区。数学奥赛辅导 第三讲 同余知识、方法、技能同余是数论中的重要概念, 同余理论是研究整数问题的重要工作之...
第三讲 同余理论
第三讲 同余理论_理学_高等教育_教育专区。教学资料第二章 同余理论 2.1 同余的概念和基本性质 2.1.1 叫做模 同余, 【定义 2.1.1】给定一个正整数 m,两...
第3讲同余
第三讲 第三讲 同余一、基础知识与典型例题 1.同余的定义 知识点 1.同余的定义 设 m 是一个给定的正整数, 如果两个整数 a, b 用 m 除所得的余数相同, ...
数学奥赛辅导 第三讲 同余
欢迎光临《 欢迎光临《中学数学信息网》 信息网》 zxsx127@163.com 数学奥赛辅导 第三讲 同余知识,方法,技能同余是数论中的重要概念, 同余理论是研究整数问题的...
第三讲:初等数论3——同余的性质和应用
第三讲:初等数论3——同余的性质和应用_农林牧渔_专业资料。第三讲:初等数论3——同余的性质和应用五年级第一学期讲义 第三讲:初等数论 3——同余的性质和应用 ...
3第三讲 唯一分解与模算数 学生版
3第三讲 唯一分解与模算数 学生版_数学_高中教育_教育专区。第三讲 唯一分解和模算数 本讲概述本讲先详细讲一下唯一分解定理相关的内容并继续同余的运算 (1)...
同余问题(含答案)
同余问题(含答案)_五年级数学_数学_小学教育_教育专区。小五奥数今日...同余问题 14页 免费 同余问题 7页 免费 第三讲 同余理论 14页 免费 应用同余...
更多相关标签:
第三讲 同余 一 | 同余定理 | 同余方程 | 线性同余法 | 同余问题 | 同余式 | 线性同余法产生随机数 | 线性同余发生器 |