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

第二讲 数论与代数初步(上)


第二讲 数论与代数知识初步 (上)

现代密码系统中,消息都是事先转换成数 值进行加密传输。密码过程是一些输入输 出都是数值的数学操作,建立,分析,攻 击这些算法需要数学工具。其中在实践中 应用最为成功的数学理论当然是数论和代 数,特别是同余理论。

本讲提要
? 整数的基本概念

1 整除性

定义1 对于整数 a ? 0, b 。我 们 说 a 整除 b ,如果存在一个整数 记 为 a|b 。 k 使得 b=ka ,我 们 把 a 叫 做 b 的因数, b 叫 做 a 的倍数, 如果 这 个 k 不存在,我 们 说 a 不整除 b , 记 为 a | b 。 ?
b, 。 1|b

性质1 (1) 对于任意 a ? 0, 0, a|a ,对于任意 a| ( 2 ) 如果 a|b , b | c ,则 a | c 。

(3) 如果 a|b , a|c ,则 a | ( sb ? tc ),这里 s 和 t 是任意整数。 证明. (1) 显而易见。 (2) 由定义存在 ( 3) 由定义可写出 即 a|sb ? tc 。 k 和 l ,满足 b ? ka , c ? lb ,所以有 c ? kla 。 b ? k 1 a , c ? k 2 a ,所以 sb ? tc ? ( sk 1 ? tk 2 ) a

1 整除性(续)
定理1 设 a , b 是两个整数,其中 个唯一的整数 q 及 r ,使得 a ? bq ? r ,0 ? r ? b 成立 。 b ? 0,则存在两

2 素数
定义 2 一个大于 1的正整数,如果它的正 它本身,就叫做素数, 否则就叫做合数。 因数只有 1和

定理2 素数的个数是无穷的。 证明. 如果素数的个数是有限 是全体素数。再令 的可令 p 1 ? 2, p 2 ? 3, , p k ?

p ? p 1 p 2 ? p k ? 1,知其必为合数, 然存在 矛盾。

而 p 不可为 p 1, p 2, , p k 之中任意一个整除,必 ? 其它素数,因此,与素 数的个数是有限的假设

定理3

存在无穷多个形如

4 n ? 1的素数。

2 素数(续)
定理4 对于任意给定整数
n n ?1

x 0,不存在整系数多项 ? ? ? a 1 x ? a 0 ( a n ? 0 , n ? 0 ), f ( x ) 都表示素数。

式 f ( x ) ? a n x ? a n ?1 x

使得 x 取所有 ? x 0的整数时,

200以内的素数: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

2 素数(续)
定理5 ( 素数数量定理 ) 如果 ? ( x ) 表示小于 x 的所有素数,则有 x ? ? 时,比率 ? ( x ) / ( x/ ln x ) ? 1。

? (x) ?

x ln x

,也就是说当

在各种密码应用中经常 通过 定理5 我们可以估计

要求使用 300 位左右的十进制素数

,

? (10

300

) ? ? (10

299

)?

10

300 300

?

10

299 299

? 1 . 3 ? 10

297



ln 10 因此,足够使用。

ln 10

3 最大公约数
定义3 设 a 1, a 2, , a n 是 n 个不全为零的整数。若 ? 它们之中每一个的因数 公因数。整数 公因数,记作 整数 d 是 ,那么 d 就叫 a 1, a 2, , a n的一个 ? 叫最大

a 1, a 2, , a n的公因数中最大的一个 ?

( a 1, a 2, , a n ),若 ( a 1, a 2, , a n ) ? 1,就说 ? ?

a 1, a 2, , a n 互素。 ? 定理6 设 a , b , c 是任意三个不全为零的 a ? bq ? c , 其中 q 是整数,则 ( a , b ) ? ( b , c )。 整数,且

3 最大公约数(续)
Euclidean 算法的表述 a ? 0, b ? 0 有 不失一般性假定任意 a ? bq 1 ? r1, ? r1 ? b 0 b ? r1 q 2 ? r2, ? r2 ? r1 0 r1 ? r2 q 3 ? r3, ? r3 ? r2 0 ? ? ? rn ? 3 ? rn ? 2 q n ? 1 ? rn ? 1, ? rn ? 1 ? rn ? 2 0 rn ? 2 ? rn ? 1 q n ? rn, ? rn ? rn ? 1 0 rn ? 1 ? rn q n ? 1 ? rn ? 1, rn ? 1 ? 0。 定理7 任意 a ? 0, b ? 0,则 ( a , b ) 就是上述过程中最后 即 ( a , b ) ? rn。

一个不等于零的余数,

3 最大公约数(续)
定理8 若任给整数 使得 ( a , b ) ? ma ? nb 。
例子1 计算 (1180 , 482 )。 1180 ? 2 ? 482 ? 216 482 ? 2 ? 2 16 ? 5 0 216 ? 4 ? 50 ? 16 50 ? 3 ? 16 ? 2 16 ? 2 ? 8 ? 0。 因此,(1180 , 482) ? 2。 可以看到余数都经历了 :剩余 ? 除数 ? 被除数 ? 忽略的过程。

a ? 0, b ? 0,则存在两个整数

m, n

3 最大公约数(续)
根据 定理7 的证明 , 我们可以得到递推公式 x 1 ? 1, x 2 ? ? q 2, x j ? ? q j x j ? 1 ? x j ? 2 y 1 ? ? q 1, y 2 ? 1 ? q 1 q 2, y j ? ? q j y j ? 1 ? y j ? 2 则 ax n ? by n ? ( a , b )。 因此, x 1 ? 1, x 2 ? ? 2, x 3 ? ? 4 x 2 ? x 1 ? 9, x 4 ? ? 3 x 3 ? x 2 ? ? 29 。 同样有 y 5 ? 71,所以 1180 ? ( ? 29 ) ? 482 ? 71 ? 2 ? (1180 , 482 )。 这一过程被称为扩展 Euclidean 算法。 :

3 最大公约数(续)
定理9 若 a | bc , a , b ) ? 1,则 a | c 。 (

设 n ? 2, a 1 ? 0, a 2 ? 0, , a n ? 0, a 1, a 2 ) ? d 2, d 2, a 3 ) ? d 3, ? ( ( ? ,d n ? 2, a n ? 1 ) ? d n ? 1, d n ? 1, a n ) ? d n,那么有下面的定理。 ( ( 定理10 若 a 1, a 2, , a n ( n ? 2 ) 是 n 个正整数,则 ? ( a 1, a 2, , a n ) ? d n。 ? 定理11 若 a 1, a 2, , a n ( n ? 2 ) 是 n 个正整数,则存在整数 ? x 2, , x n 使得 ? a 1 x 1 ? a 2 x 2 ? ? a n x n ? ( a 1, a 2, , a n )。 ? x1,

4 最小公倍数
定义4 设 a 1, a 2, , a n 是 n ( ? 2 ) 个整数。若 ? 每一个的倍数,那么 m 是这 n 个数中 a 1, m 就叫这 n 个数的一个公倍数。在 整数叫做最小公倍数,

a 2, , a n的一切公倍数中最小的 ? 记作 [ a 1, a 2, , a n ]。 ? 定理12

设 a , b 是任意的两个整数,则 [ a , b ]的所有倍数。

(1) a , b 的所有公倍数就是 (2) [a, b] ? ab (a, b) 。

4 最小公倍数(续)
设 n ? 2, a 1 ? 0, a 2 ? 0, , a n ? 0,a 1, a 2 ] ? m 2,m 2, a 3 ] ? m 3, ? [ [ ? , n ? 2, a n ?1 ] ? m n ?1, n ?1, a n ] ? m n,那么有下面的定理。 [m [m 定理13 若 a 1, a 2, , a n 是 n ( n ? 2 ) 个正整数,则 ? [ a 1, a 2, , a n ] ? m n。 ?

4 整数唯一分解定理
定理14 设 a 是任一大于 正因数 q 是素数,并且当 q ? a。 1的整数,则 a 的除 1以外的最小 a 是合数时,

引理1 若 p 是一素数, a ) ? 1。

a 是任一整数,则有

p | a或 ( p,

引理2 若 p 是素数, p|ab ,则 p | a 或 p | b 。

4 整数唯一分解定理(续)
定理15 ( 整数唯一分解定理 的乘积 , 即对于整数 ) 任何大于 1的正整数都能分解成素 数 a ? 1,有 (1) a ? p 1 p 2 ? p n, p 1 ? p 2 ? ? ? p n , 其中 p 1, p 2, , p n 都是素数 , 并且若 ? a ? q 1 q 2 ? q m, q 1 ? q 2 ? ? ? q m, 其中 q 1, q 2, , q m 都是素数,则 ? (2) m ? n , q i ? p i ( i ? 1,, , n )。 2 ? a ? 2时 (1) 显然成立,假定一 如果为合数 因此

证明: 首先证明 (1) 成立,数学归纳法,当 且小于 a 的正整数都成立,考虑 则必有分解

a 如果为素数显然成立,

a ? bc ,1 ? b ? c ? a , 可知 b 和 c 都能表示为素数乘积, 故 (1) 成立。 (1) 和 ( 2 ) 知 p 1 p 2 ? p n ? q 1 q 2 ? q m ,由引理

a 也能表示为素数乘积, 其次 , 证明唯一性。由

2 可知 p1 ? q1

p 1 | q j, q 1 | p k ,由于 q j, p k 为素数,所以 和 q 1 ? p 1,因此, p 1 ? q 1。进一步,由

p 1 ? q j, q 1 ? p k 。同时有

p 2 ? p n ? q 2 ? q m 可以得 p 2 ? q 2,

以此类推,最后可得,

m ? n , p n ? q m。

4 整数唯一分解定理(续)
算术基本定理说明,任
? ? ?

意大于 1的整数能够唯一写成

a ? p 1 1 p 2 2 ? p k k , ? i ? 0 ( i ? 1, , k ),其中 p i ? p j ( i ? j ) ? 是素数。 因此,对于
? ? ? ?

a ? 0 和 b ? 0,且
? ?

a ? p 1 1 p 2 2 ? p k k , ? i ? 0 ( i ? 1, , k ) ? b ? p 1 1 p 2 2 ? p k k , ? i ? 0 ( i ? 1, , k ) ? ( a , b ) ? p1 [ a , b ] ? p1
min( ? 1 , ? 1 ) min( ? 2 , ? 2 ) min( ? k , ? k ) max( ? k , ? k )

p2 p2

? pk

max( ? 1 , ? 1 )

max( ? 2 , ? 2 )

? pk



由于 x ? y ? max( x , y ) ? min( x , y ), 所以, ab ? [ a , b ]( a , b ),即 [ a , b ] ? ab (a, b) 。

5 一次不定方程
二元一次不定方程是指 a1 x ? a 2 y ? n , 其中 a 1, a 2, n 是给定的整数, 定理16 ( 3) a 1 a 2 ? 0。 件是

方程 ( 3 ) 有整数解的充分必要条 ( a 1, a 2 ) | n 。

定理17 设( a 1, a 2 ) ? 1,则 (3) 的全部解可表示为 x ? x 0 ? a 2 t , y ? y 0 ? a 1t , 其中 x 0, y 0 为 ( 3 )的一组解, t 为任意整数。

5 一次不定方程(续)
定理18 设 s ? 2, s 元一次不定方程 a 1 x 1 ? a 2 x 2 ? ? ? a s x s ? n ,a 1 a 2 ? a s ? 0, 有整数解 x 1, x 2, , x s的充分必要条件是 ? ( a 1, a 2, , a s ) | n 。 ? 定理19 在 n ? a 1 a 2时, a 1 x 1 ? a 2 x 2 ? n , a 1 ? 0, a 2 ? 0 有正整数解 x 1 ? 0, x 2 ? 0,但在 ( a 1, a 2 ) ? 1, 数解 x1 ? 0, x 2 ? 0。 n ? a 1 a 2时,上述方程没有正整

谢谢!


相关文章:
基础数论例讲
第二讲 数论与代数初步(... 暂无评价 18页 2下载券 第二讲 数论与代数初步...d 是圆周的个数;数 2 是在同一个取出的元素个数,使得在同一个圆周上可 ...
第二讲 数论(一)
第二讲 数论(一)_学科竞赛_小学教育_教育专区。上海智康 1 对 1 小学奥数 ...65241 设五位数是 abcde,则奇数位上数字为 a+c+e,偶数位数字为 b+d...
代数初步的认知过程
小六奥数经典数论习题附答... 5页 1财富值如要投诉...其中规定, 在 4-6 年级(即第二学段)“数与代数...首先要帮助学生形成对长度的初步感知。实际上小学生...
第四讲1数论
第四讲 数论与代数初步(... 19页 免费 数论1 4...二.数论综合 数论,行程,图形、计算小升初奥数必考 ...能被 3 整除的特征是各个数位上数字之和能被 3...
[第13讲] 初等数论(2)同余初步(上)
[第13讲] 初等数论(2)同余初步(上)_数学_高中教育_教育专区。5 数论 同余问题选讲 【例1】 (常规题型) 数 1978n 与 1978m 最后三位相等, 试求使得 m ...
第一章-代数初步-奥数典型题(含答案)
第一章-代数初步-奥数典型题(含答案)_初一数学_...若正整数 a 分别加上 3 7 后,所得的两个...初一奥数第03讲 求代数式... 5页 1下载券 小学...
计算代数与计算数论
第二讲 数论与代数初步(... 暂无评价 18页 2下载券 代数数论历史及其在ICM上... 11页 7下载券 2013年(数论与代数)模拟... 3页 7下载券©...
五、代数与数论综合问题
上式两边同除以 n(n ? 1) 得设故 bn ? an (n ? 2) n(n ? 1) 3...第二讲 数论与代数初步(... 21页 免费 第五讲 数论综合 5页 1下载券 ...
专题六 数论初步与规律探究讲义
数论初步与规律探究讲义板块一:数论两宝——代数思想...(2)a3 . 第 1 页共 6 页 板块二:约数三大...(1)若圆周上依次放着数 1,2,3,4,5,6,问:...
更多相关标签:
代数数论 | 代数数论pdf | neukirch 代数数论 | 数论初步 | 代数数论 冯克勤 pdf | 初等数论与高等代数 | 黎景辉 代数数论 | 代数数论 冯克勤 |