首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

关于线性同余用辗转相除,有更好的计算方法吗,该如何处理

2012-04-25 
关于线性同余用辗转相除,有更好的计算方法吗例子1:(17n+5)/23m解:n(23m-5)/17 …… (6m-5)/17m(17n+5)/6

关于线性同余用辗转相除,有更好的计算方法吗
例子1:
(17n+5)/23=m
解:
n=(23m-5)/17 …… (6m-5)/17
m=(17n+5)/6 ......... (5n+5)/6
n=(6m-5)/5 ……. (m/5)
开始回溯:
m=5p
n=6p-1
m=17p-2
结果:n=23p-3 (p∈Z)



例子2:
(85n+7)/115=m
解:
n=(115m-7)/85 …… (30m-7)/85
m=(85n+7)/30 ……. (25n+7)/30
n=(30m-7)/25 …….. (5m-7)/25
m=(25n+7)/5 ……….5n+(7/5)
结果:无解


[解决办法]
(85n+7)/115=m-->115m - 85n = 7-->5(23m - 17n) = 7:7不能被(115,58)的最大公因子5整除,故无解!
(17n+5)/23=m-->23m - 17n = 5:(23,17)的最大公因子 = 1,显然可以整除5,故有解;

一般:ax + by = c有解的条件:c可以被a,b的最大公因子整除。

热点排行