什么是数论? ■数论是纯数学的一个分支,也是纯数学的代 表,它主要研究整数的性质 ■数论的早期研究可追溯至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
余数