因此N={,{},{,{}},{,{},{,{}}},…}-南京大学.ppt

* * * * 自然数及数论初步 离散数学－集合论 南京大学计算机科学与技术系 内容提要 自然数 整数及基本运算 素数 欧拉函数 用集合定义自然数 设a为集合, 称a?{a}为a的后继, 记为s(a)，或a+。 设A是集合，若A满足下列条件，称A为归纳集： ??A ?a(a?A?s(a)?A} 自然数集合N:是所有归纳集的交集。 因此：N = { ?, {?}, {?, {?}}, {?, {?}, {?, {?}}}, … } N的每一个元素称为一个自然数。 ?记为0，s(0)记为1，s(1)记为2， s(2)记为3，以此类推 再具体一点 记号0表示： ? 记号1表示s(0)：??{?}={?} 记号2表示s(1)：{?}?{{?}}={?,{?}} 记号3表示s(2): {?,{?}, {?,{?}}} 1?3 2?3 1?3 2?3 1∪3=3 2∩3=2 皮亚诺公理(Peano axioms for natural numbers) 零是个自然数. 每个自然数都有一个后继（也是个自然数）. 零不是任何自然数的后继. 不同的自然数有不同的后继. （归纳公理）设由自然数组成的某个集合含有零，且每当该集合含有某个自然数时便也同时含有这个数的后继，那么该集合定含有全部自然数. 备注：另有4个与自然数相等有关的公理 自然数上的运算 加法（递归定义） m + 0 = m m + s(n) = s(m+n) 乘法（递归定义） m * 0 = 0 m * s(n) = m + m*n 算筹（中国古代数学） 算筹数码，四则运算（九九表）、乘方、开方 “战国”或之前 正整数(N+)、零、负整数 4 x +20 =4 刘徽(A.D. 225-295) 整数 整数之间的整除 对任意整数a和b, a ? 0, 我们说a整除b (记作a|b) , 如果存在整数c使得 b = a c . 设a, b和c是整数，a ? 0, 若a|b，且 a|c，则 a|(b+c) 若a|b，则 a|(b c) 若a|b，且 b|c，则 a|c 带余除法 令a为整数，d为正整数，则存在唯一的整数q和r，且 0??r ? d ，满足 a = d q + r . d为除数，a为被除数，q为商，r为余数。 记作 q = a div d，r = a mod d. 举例：-11 mod 3 =? 证明： S={r?N | ? q?Z. r = a-dq}是N的非空子集 N是良序的，S有最小元素，记为r0，即r0 = a-dq0 用反证法易证r0?d, 否则r0-d是S中比r0更小的元素, 矛盾 唯一性证明， 0 ? r1 - r0 = d (q0-q1) ? d，因此，q1=q0 带余除法（续） 令a和b为整数，d为正整数，则 (a + b) mod d=(a mod d+ b mod d) )mod d. (a b) mod d=((a mod d) (b mod d))mod d. 同余算术 (高斯, Gauss) 素数 大于1的正整数p称为素数，如果p仅有的正因子是1和p。大于1又不是素数的正整数称为合数。 正整数n是合数 iff ?a?N. 1? a ? n, 且 a | n . 算术基本定理：每个大于1的正整数都可以唯一地写为一个素数或者若干个素数的乘积，其中素数因子以非递减序出现。 n = p1?1 p2?2 …pk?k 素数举例：2, 3, 5, 7, 11, 13, 17, 19, … 合数举例：100= 22 52. 999= 33 37, 1024= 210 . 埃拉托色尼筛选法(Eratosthenes, BC276–195) 用筛选法求素数（以25以内的为例） 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 [2] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 [3] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 [5] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 素数（续） 素数（续） 任意给定K，存在K个成等差级数的素数(陶哲轩,格林, 2004) 举例：当K=3时，