南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）集合论——第8章 数论初步

数论初步 离散数学 南京大学计算机科学与技术系

数论初步 离散数学 南京大学计算机科学与技术系

急售扇 提要 整数的性质 ·整数的基本运算 ·质数 。Euler函数与Euler定理

提要  整数的性质  整数的基本运算  质数  Euler函数与Euler定理

什么是数论？ ■数论是纯数学的一个分支，也是纯数学的代 表，它主要研究整数的性质 ■数论的早期研究可追溯至Euclid时期(~300 B.C.):对质数和整除的研究 ■中国古代（~400A.D.)对同余方程的研究 为现代数论作出了基础性贡献

什么是数论？

般践感 现代数论的早期铺垫 证明质数无穷 -Euclid:Elements (~300 A.D.) ■筛法寻找质数 Eratosthenes (~250 A.D. ■辗转相除法求最大公约数 N- -Euclid:Elements (~300 A.D.) ·求解同余方程的中国剩余定理 《孙子算经》（~420B.C.)

现代数论的早期铺垫

整数集 整数集一般记为Z（来源于德语“数”： Zahlen的首字母)，同时用Z+表示正整数集 (N-{O}),用Z-表示负整数集(Z-N) Z为可列集：Z≈N,基数为o ■Z是全序集（朱来课程详述），无上界和下界 Z和加法运算形成一个循环群（未来课程详述）；和 加法运算及乘法运算形成一个环（参见抽象代数资料*）

整数集

条 整除 整除(divisible)是定义在Z上的二元关系： 设a,b∈Z,a≠0，ab台(3c∈Z)(b=a×c) alb读作“a整除b” 设a,b,c∈Z且a≠0，有： o(ab)A(alc)→al(b+c) oab→al(b×c) o(alb)A(blc)→alc

整除

般鷗感 余数 ■余数(remainder)来源于带余除法 定义（带余除法)：令a∈Z,d∈Z+,则： (3!q,r∈Z∧0≤r<d)(a=d×q+r) 0 其中，a称为被除数(dividend),d称为除数 (divisor),q称为商(quotient)4,r称为余数 0 记：q=a div d,r=a mod d,后者读作“"a模b” 例：：-11=3×(-4+1，-11m0d3=1 6

余数

条 余数 模的基本性质：令a,b∈Z,d∈Z+,则： o(a+b)mod d (a mod d+b mod d)mod d o (a x b)mod d [(a mod d)(b mod d)]mod d

余数

般线 同余 "同余(congruence modulo)是定义在Z上的 二元关系：设a,b∈Z, a≡b(modm)←台(3m∈Z+)(ml(a-b)) )上式读作“a与b模m同余(a is congruent to b modulo m)”,称m为上述“同余的模 (modulus of the congruent)” +4日 )同余关系及符号“=”由C.F.Gauss于1801年引入 例：26=14(m0d12),-5=13(mod6)

同余

&兔 质数 仅含2个正因子（1和自身)的大于1的整数称 为质数(prime number),大于1的非质数 整数称为合数(composite number) 定理（算术基本定理）：每个大于1的整数皆 可分解为有限个质数之积（这些质数称为质 因子)，若不考虑顺序，则分解唯一 0 n=p1p2…pg(p1<p2<…<pk,:eZ+)

质数