关于线性同余用辗转相除,有更好的计算方法吗
例子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的最大公因子整除。