ChNumbers离散数学英文版PPT课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《ChNumbers离散数学英文版PPT课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ChNumbers 离散数学 英文 PPT 课件
- 资源描述:
-
1、Chapter 4:Number TheoryElements of Discrete Structures1Intro to Integers and Division A branch of mathematics is called Number Theory It involves integers and their properties Basic concept of number theory is used through out computer science We will study:integer division,modular arithmetic,primes
2、(素数),greatest common divisors and some algorithms in number theory2DivisionDefinition:If aZ and bZ with a 0,we say that a divides b if c Z,b=ac.It is also called b is divisible by a When a divides b,we say a is a factor of b and that b is a multiple of a We use a|b to denote a divides bWe use a b to
3、 denote a does not divides b3Example Let n and d be positive integers.Question:How many positive integers n are divisible by d?Those numbers are 1d,2d,kd,where kd n and(k+1)d n So,from kd n,we know k n/d.We conclude that there are n/d positive integers n that are divisible by d When n=11,d=3,11/3=3.
4、The positive integers that are divisible by 3 are 3,6,and 94Theorem 1Theorem 1:Let a,b and c Z:1)If a|b and a|c,then a|(b+c)2)If a|b then a|bc for all c Z3)If a|b and b|c,then a|cProof of 1):by definition,d Z e Z and b=ad and c=ae.So b+c=ad+ae=a(d+e),d+e is an integer.By definition,a divides b+c5The
5、 Division Algorithm Theorem 2:(Proof will be given later)Every integer a,when divided by a positive integer d,can be expressed uniquely in terms of a quotient q Z and a remainder r N as a=dq+r (0 r d)We call d the divisor,a the dividend,q the quotient,and r the remainder.q=a div d r=a mod d(a modulo
6、 d)(Be used very often)6The Division Algorithm Division Algorithm Examples:1)11 div 3=3;11 mod 3=2;Or 11=33+22)-11 div 3=-4;-11 mod 3=1;Or-11=3(-4)+13)12 div 3=4;12 mod 3=0;Or 3 divides 12,or 3|124)“a divides b”is equivalent to“b mod a=0”7Modular Arithmetic Definition:Given two integers a and b,and
7、a positive integer m.Then a is congruent(同余同余)to b modulo m,denoted by a b(mod m),if m|(a b)Theorem 3:Let a and b be integers and m a positive integer.Then a b(mod m)iff (a mod m)=(b mod m)By the Division Theorem,let a=mq1+r1 and b=mq2+r28Modular Arithmetic Proof of Theorem 3:IF:if(a mod m)=(b mod m
8、)(remainders are the same:r1=r2),then a b=mq1+r1 (mq2+r2)=m(q1 q2)or m|(a b).By definition,a is congruent to b modulo m9Modular Arithmetic Proof of Theorem 3:ONLY-IF:by definition of congruence,there exists k Z,a b=km,or a=b+km (i)From the Division Algorithm,for some q,r Zb=qm+r,(0 r 1 is called pri
9、me if the only positive factors of p are 1 and p Definition:a positive integer 1 that is not prime is called composite Primes less than 100 are2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,71,73,79,83,89,9712The Fundamental Theorem of Arithmetic Every positive integer can be written uniquely as
展开阅读全文