离散数学－集合论 南京大学计算机科学与技术系 自然数及数论初步 离散数学－集合论 南京大学计算机科学与技术系

内容提要 自然数 整数及基本运算 素数 欧拉函数

用集合定义自然数 设a为集合, 称a{a}为a的后继, 记为s(a)，或a+。 设A是集合，若A满足下列条件，称A为归纳集： 自然数集合N:是所有归纳集的交集。 因此：N = { Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}}, … } N的每一个元素称为一个自然数。 Ø记为0，s(0)记为1，s(1)记为2， s(2)记为3，以此类推

再具体一点 记号0表示： Ø 记号1表示s(0)：Ø{Ø}={Ø} 记号2表示s(1)：{Ø}{{Ø}}={Ø,{Ø}} 记号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+)、零、负整数 刘徽(A.D. 225-295) 4 x +20 =4

整数

整数之间的整除 对任意整数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.

同余算术 (高斯, 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) 任一大于2的偶数都可以写成2个素数之和？ 素数的分布？ 1+1（哥德巴赫猜想，1742） 1+2（陈景润证明，1966） 素数的分布？ 无穷多个“特殊形式的素数”，比如：搜寻尽可能大的梅森素数。 不超过n的素数有多少个？接近于n / ln n (n充分大时）

最大公约数 能整除两个（正）整数的最大正整数称为这两个（正）整数的最大公约数。记法：gcd(a, b) gcd(a, b) = max{ dN+ | d|a, d|b}, a0 或者b0 我们称a和b是互素的，如果gcd(a, b) = 1 若a = p11 p22 …pkk，b = p11 p2 2 …pk k, 则 gcd(a, b) = p11 p22 …pkk，i=min {i, i} 求2个正整数的最大公约数 gcd(a, b) = gcd(a, b-a) //不妨假设 ab。

欧几里德算法（求最大公约数） function gcd(a, b) // a0, b0 while a ≠ b if a > b a := a − b else b := b − a return a function gcd(a, b) // 不全为0的自然数 while b ≠ 0 t := b b := a mod b a := t return a function gcd(a, b) // ab0, a>0 if b=0 return a else return gcd(b, a mod b)

最大公约数（续） gcd(a, b)一定是a和b的线性组合，即： s, tZ，gcd(a, b)=sa+tb //欧几里德算法 非零整数a和b是互素的 iff s, tZ. sa+tb =1 必要性显然。 以下证明其充分性。假设s, tZ. sa+tb =1. 假设gcd(a, b)=d， a1, b1Z. a=a1d, b=b1d. 我们有sa1d+tb1d =1. 即 (sa1+tb1)d =1. 因此d=1. 即gcd(a, b)=1。

中国剩余定理（孙子算经，5世纪） 假设正整数m1, m2, ... , mn两两互素，一元线性同余方程组（S）有解，在模M同余下是唯一的。 今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？ 答曰：‘二十三’。 假设正整数m1, m2, ... , mn两两互素，一元线性同余方程组（S）有解，在模M同余下是唯一的。 解的唯一性，需要证明： m1|y, …, mn|y  (m1…mn)|y

中国剩余定理（孙子算经，5世纪） 需要下列引理： 设a, b和c是正整数, a和b是互素的, 若a|bc, 则a|c。 证明： s, tZ. sa+tb =1. c=(sa+tb)c=sac+tbc, 因此, a|c。 设a, b和c是正整数, a和b是互素的, 若a|c,若b|c,则ab|c。 证明： c=ua=vb, a|vb, a|v. (a和b互素) v=ka, c=kab, 因此, ab|c .

Euler‘s totient (函数) (n) = |{ k |1 ≤ k ≤ n , gcd(k, n) = 1}|, nN+ (3) = 2, (4) =2, (12) =4 设 n = p11 p22 …pkk 令 Ai = { x |1≤ x ≤ n , pi整除x} (n) = | ~A1 ~A2 … ~Ak | = n – (n/p1 +…+ n/pk) + (n/p1p2+…+n/pk-1pk) – … + (-1)k n/p1p2 … pk = n(1– 1/p1) (1– 1/p2) … (1– 1/pk)

欧拉函数(phi) 欧拉常数 γ = 0.577215665...

欧拉函数(phi) (p)=p-1，p是素数 如果m与n互素，则φ(mn) = φ(m)φ(n).

欧拉定理 Fermat小定理. 设正整数a不是p的倍数，则 Euler定理. 若正整数a与n互素，则

RSA的数学基础 若a与n互素，则 aφ(n)  1 (mod n) , 若 1 (mod φ(n)) , 则 a a (mod n) 若n=pq,  1 (mod φ(n)), 0<m <n, 则m m (mod n) 选取大素数p, q: n=pq (n难以分解成素数乘积）. 令 k= φ(n) (不知道n的质因子，k难以求出）. 设e为公钥，d为私钥，满足 ed ≡ 1 (mod k). 加密：S = me (mod n). 解密：t = Sd (mod n). (t = m，why?)

作业 教材[3.4, 3.5, 3.7] P156:  10, 13, 19, 25 P162:  2, 4, 7, 14, 17, 24 P182:  19, 20, 28, 41