文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 第八章 数论算法及计算几何算法
侵权投诉

第八章 数论算法及计算几何算法

第八章 数论算法及计算几何算法 229

★定义3 设a、b和m为整数,其中m>0。若a和b被m除得的余数相同,则称a

和b对模m同余。记为a b(modm)或a b(m)。

一切整数n可以按照某个自然数m作为除数的余数进行分类,即n=pm+r(r=0,1,…,m-1),称r为n关于m所在的剩余类,恰好m个。于是同余的概念可理解为:若对n1、n2,有n1=q1m+r,n2=q2m+r,那么n1、n2对模m同余,即它们除以m所得的余数相等。利用整数的剩余类表示法,可以证明同余式有如下简单性质: (1)若a b(m),则m|(b-a)。反过来,若m|(b-a),则a b(m);

(2)如果a=km+b(k为整数),则a b(m);

(3)每个整数恰与0,1,…,m-1这m个整数中的某一个对模m同余; (4)同余关系是一种等价关系:

① 反身性 a a(m);

② 对称性a b(m),则b a(m),反之亦然; ③ 传递性a b(m),b c(m),则a c(m)。 (5)如果a b(m),x y(m),则

① a x=(b y)(m);

②ax by(m)特别地a b(m)。

应用同余式的上述性质,可以解决许多有关整数的问题。

【例8-1】(1898年匈牙利奥林匹克竞赛题)求使2n+1能被3整除的一切自然数n。 解:2 1 0(mod 3) 2 1 1 1(mod 3) 2 1(mod 3) (8-3) ∵2 1(mod 3) ∴2 ( 1)(mod 3)

∴当n为奇数时,(8-3)式成立,2n+1能被3整除;当n为偶数时,(8-3)式不成立,2n+1不能被3整除。

【例8-2】求2999最后两位数码。 解:考虑用100除2999所得的余数。

∵2mod100 4096mod100 4 mod 100 ∴2

999

n

n

n

n

n

k

k

12

(212)83 23 ( 4)83 23(mod 100)

又46 4096 mod 100 4 mod 100

∴483(mod 100) (46)13 45 413 45 (46)3 ( 4)3 64(mod 100) ∴2999 ( 4)83 23 64 23 512 (mod 100) 88(mod 100) ∴2999的最后两位数字为88。 2.同余方程

★定义4 设f(x) anxn a1x a0是整系数多项式,m是正整数,称

f(x) 0(mod m) (8-4)

上一页第5页

热门文档

相关文档

  • 第8章 数论算法及计算几何算法

    第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? ...

  • 第8章 数论算法及计算几何算法

    第8章 数论算法及计算几何算法_数学_自然科学_专业资料。第八章 数论算法及计算几何算法 教学目标 ? 理解求最大公约数的算法 ? 掌握欧几里德公式的推广 ? ...

  • 第8章 数论算法及计算几何算法

    第八章 数论算法及计算几何算法 8.5 凸包问题 1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点...

  • 数论和计算几何

    数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 ... 第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与...

  • 数论和计算几何

    第八章 数论算法及计算几... 28页 免费 奥数几何,数论,行程专题 8页 7...快速幂是用来快速计算a^n mod p的一种方 法。 如果n是偶数则a^n=a^(n/...

  • 离散数论-第八章

    离散数学--11.1-2初等数论 24页 免费 数论-第八章 14页 1财富值 108第八章数论及其猜想的意... 41页 1财富值 第八章 数论算法及计算几何... 暂无...

  • 第二章 贪心法

    第八章 数论算法及计算几何... 第九章 NP完全理论1/2 相关文档推荐 第2章 贪心法 56页 5财富值 第2章 贪心法 暂无评价 42页 1财富值 第2章 贪心法 ...

  • 进化算法EA

    [编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...

  • 第8章 几何运算

    三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...

  • 第一章 算法及基础知识

    224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email