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

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

230 是关于未知数x的模m的同余方程,简称为模m的同余方程。若an为n次同余方程。

0(modm)则称式(8-4)

★定义5 设x0是整数,当x=x0时式(8-4)成立,则称x0是同余方程(8-4)的解。凡对

于模m同余的解,被视为同一个解。同余方程(8-4)的解数是指它的关于模m互不同余的所有解的个数,也即在模m的一个完全剩余系中的解的个数。

由定义3可知同余方程(8-4)的解数不超过m。 3.一次同余方程

★定义6 设a,b为整数,且

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

a

为一次同余方程。

0(modm),则称同余方程

ax b(mod m) (8-5)

★定义7 设a1,a2,…,an是非零整数,b是整数,称关于未知数x1,x2,…,xn的方程

a1x1+a2x2+…+anxn=b

是n元一次不定方程。

★定理3 一次同余方程有解的充要条件是gcd(a,m)|b。若有解,则恰有d=gcd(a,m)

个解。

证明 显然,一次同余方程(8-5)等价于一次不定方程 ax+my=b (8-6)

根据一次不定方程a1x1+a2x2+…+anxn=b有解的充要条件是gcd(a1, ,an)b

(1)

可知第

一个结论成立。

若同余方程(8-5)有解x0,则存在y0,使得x0与y0是方程(8-6)的解。此时,方程(8-6)的全部解是

m

x x t0 gcd(a,m)

t Z (8-7) a

y y0 t gcd(a,m)

由式(8-7)所确定的x都满足方程(8-6)。记d=gcd(a,m)以及t=dq+r, q Z,r=0,1,2,…,d-1, 则x x0 qm

mm

r x0 r(mod m) dd

m2m(d 1)m

,x0 ,……, x0 对于ddd

容易验证,r=0,1,2,…,d-1时相应的解x0,x0

模m是两两不同余的,所以同余方程(8-5)恰有d个解。证毕。

4.一次同余方程的求解步骤 步骤1:求gcm(a,m);

步骤2:令d= gcm(a,m),如果d,则式(8-5)无解,算法结束;如果db,则转步骤3; 步骤3:根据欧几里德公式的推广,求出式(8-5)的一个解x0。

步骤3-1:根据欧几里德公式的推广算法求得满足ax' +my'=d的x',y';具体方法: 将ax'+my'=d变形可得到: (1)

参考有关初等数论教材或著作

上一页第6页

热门文档

相关文档

  • 第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