第4页
A与B之间的关系: R = {(张三, 离散数学), (张三, 数据结构), (张三, 英语), (李四, 数据结构), (王五, C语 言), (王五, 汇编语言)} A B. A, B与C之间的关系: S = {(张三, 离散数学, 优), (张三, 数据结 构, 良), (张三, 英语, 优), (李四, 数据结构, 优), (王五, C语言, 合格), (王五, 汇编语言, 良)} A B C.
第21页
(7) 若a b(mod m) 则对于整系数多项式 f(x), 有 f(a) f(b)(mod m). Proof f(x) = c0xn + c1xn-1 + …+ cn-1x +cn, ciZ, i.
根据已知条件m|(a - b).
f(a) - f(b) =
c0(a - b)n + c1(a - b)n-1 + …+ cn-1(a - b).
第2章 关系
2.1 关系的概念
本讲内容
1 2
3
n元关系的定义
2元关系的有关概念
Z上的整除关系“|” Z上的同余关系“m”
4
第1页
离散对象虽然离散, 但没有“关系”是不 行的. 在信息科学中, 数据与数据之间总存在一 定的关系. 科学研究的主要任务就是发现事物之间的 内在关系. 如何建立关系的数学模型? 关系内容对今后学习数据结构以及数据库 等很多课程都是很重要的.
第18页
(4) x , yZ, 若a b(mod m)且c d(mod m), 则ax + cy bx + dy (mod m). Proof 根据已知条件m|(a - b)且m|(c - d), 于是m|(a - b)x + (c - d)y, 即m|(ax + cy) - (bx + dy) , 进而ax + cy bx + dy (mod m).
第11页
关系符号:
任意集合符号可以作为关系符号. 对于常见的很有用的关系可以给出一个固定
的特殊符号.
自定.
第12页
本讲内容
1 2
3
n元关系的定义
2元关系的有关概念
Z上的整除关系“|” Z上的同余关系“m”
4
第13页
例2-3 整数集Z上的整除关系“|”或“D”.
m | n n qm, q Z. 2 | 6,2 | 6,2 | 6,2 | 6,2 | 2,2 | 2,0 | 0
数论(Number Theory)中的常用记号:
x m y
x y(mod m)
A. 关于模同余关系的性质. B. 关于模同余关系的三个重要定理.
第37页
Wilson Theorem: p为素数的充要条件是
( p 1)! 1(mod p).
Euler Theorem: 设aZ, n≥1, 若gcd(a, n) =1, 则 (n)
2元关系的有关概念
Z上的整除关系“|” Z上的同余关系“m”
4
第7页
2. 二元关系(binary relation) 下面主要讨论2元关系? 常见的是2元关系? n (≥3)元可归结到2元.
第8页
两个集合A和B(可以相同)间的关系称为2 元关系(简称关系): A到B的关系: R A B. A上的关系(A到A): R A A? 例2-1 A = {a, b}, B = {1, 2, 3},
gcd(4, 3) = 1: 4(3) 1(mod 3)
第27页
Proof 令S是所有小于等于n且与n互素的 正整数组成的集合, 于是|S| = (n). 不妨设 S = {r1, r2,…, r(n)} 由gcd(a, n) =1, 可以证明: S={ar1(modn),ar2(modn),…, ar(n)(modn)}.
第23页
Proof ()(反证)若p = ab(1<a, b< p), 则 a|(p - 1)! 根据已知条件, 有p|(p -1)! +1, 即ab|(p -1)! +1, 进而a|(p -1)! +1. 于是a|1, 不可能.
第24页
() 当p = 2, 3时,结论成立. 下设p > 3并考 虑S ={2, 3, 4, …, p-2}. 任取aS, 由于gcd(a, p) =1, 存在x , yZ满 足ax + py = 1, 所以ax 1(mod p). 令b = x(mod p), 有ab 1(mod p). 因为aS 且ax + py = 1, 于是b 0, 1, p – 1, 进而bS.
第20页
例如, 计算32015的个位数. 设32015的个位数为x, 则32015 x(mod 10). 而32015 = 34503 + 3, 33 7(mod 10), 34 1(mod 10), 由性质(6)知, 34503 = (34)503 1503(mod 10) = 1(mod 10), 由性质(5)知, 32015 = 34503 + 3 = (34)503 • 33 1 • 7(mod 10) = 7(mod 10). 所以, x = 7.
a(n) 1(modn).
第30页
Fermat Little Theorem: 素数且gcd(a, p) =1, 则
若a为整数, p为
a
p 1
1(mod p).
Hint 当gcd(a, p) = 1时, 由于(p) = p - 1, 由Euler定理即得.
第31页
Remark 关于Fermat great theorem:
第25页
下证a b: 若a = b, 则a2 1(mod p), 即 p|(a -1)(a +1). 于是p|(a -1)或p|(a +1), 不可能. 可将S中的数分成(p-3)/2对, 每对数a和b均 满足ab 1(mod p). 于是 2•3•4•…•(p-2) 1(mod p), 2•3•4•…•(p-2)•(p-1) (p-1)(mod p),
第5页
Def 2-1
A1 , A2 ,..., An
R A1 A2 ... An .
n个对象之间的关系(n-ary relation). 结合引例?
n 特别地, 若 R A A ... A , 则称R为A上的
n元关系.
第6页
本讲内容
1 2
3
n元关系的定义
第19页
(5) 若a b(mod m)且c d(mod m), 则 ac bd(mod m). Hint ac - bd = c(a - b) + b(c – d) (6) 若a b(mod m) 则对于正整数n, 有
an bn(mod m).
Hint an - bn = (a - b)(an-1 + an-1b +…+ bn-1 )
S ={ar1(modn),ar2(modn),…, ar(n)(modn)}.
第29页
ar1(modn)•ar2(modn) •…• ar(n)(modn) = r1•r2•…• r(n). ar1•ar2•…• ar(n)(modn)= r1r2…r(n) (modn).
a(n)r1r2 …r(n)(modn)= r1r2…r(n)(modn). gcd(ri, n) = 1, i =1, 2, …, (n),
(p-1)! -1(mod p).
第26页
Euler Theorem: 设a为整数, n为正整数, 若gcd(a, n) =1, 则
a
(n)
1(mod n).
gcd(2, 3) = 1: 2(3) 1(mod 3)
gcd(2, 5) = 1: 2(5) 1(mod 5)
gcd(3, 5) = 1: 3(5) 1(mod 5)
第22页
B. 关于模同余关系的三个重要定理: Wilson Theorem: p为素数的充要条件是
( p 1)! 1(mod p).
p = 2: 1! -1(mod 2)
p = 3: 2! -1(mod 3)
p = 5: 4! -1(mod 5)
p = 7: 6! -1(mod 7)
第28页
一方面, 由于gcd(a, n) = 1且gcd(ri, n) = 1, 于是gcd(ari, n) = 1, i =1, 2, …, (n), 进而 {ar1(modn),ar2(modn),…, ar(n)(modn)} S. 另一方面, ari(modn)} arj(modn)}, i j. 否则n|a(ri - rj), 不可能.
本讲内容
1 2
3
Z上的模同余关系(续) 关系的定义域和值域
关系的表示 函数的关系定义
4
第35页
例2-4(K. F. Gauss) 设m为正整数, 整数集 Z上的模m同余关系“m”:
x m y m | ( x y).
m|(x - y) x除以m的余数 = y除以m的余 数.
第36页
R {( a,3), (a,2), (b,1), (b,3)} A B ?
A B {( a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}.
第9页
A到B的空关系与全关系AB.
A上的空关系与全关系AA.
Theorem 2-1 若|A| = m, |B| = n, 则A到B的 关系有2mn.
a
1(mod n).
Fermat Little Theorem:设aZ, 若p为素数 且gcd(a, p) =1, 则
