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)
参考有关初等数论教材或著作
第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章 贪心法 ...
[编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...
三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...
224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......
热门文档