能否估计

manthanein · 发表于 2017-1-16 22:17:47

您需要登录才可以下载或查看，没有账号？欢迎注册

×

给定两个互质的正整数\(a\)和\(b\)。我们要找出最小的正整数\(x\)，使得\(x\)除以\(a\)余\(1\)，除以\(b\)余\(0\)。
这个问题当然不难。我想问的事，这个\(x\)能不能由\(a\)和\(b\)估计出来？

王守恩 · 发表于 2017-1-17 03:38:15

设b为较小数，x最大是(b-1)a+1 。
在下面(b-1)个数中必有b的倍数：
1a+1，2a+1，3a+1，4a+1，...........，(b-1)a+1，

happysxyf · 发表于 2017-1-17 10:00:25

本帖最后由 happysxyf 于 2017-1-17 10:01 编辑

x=tb+b(t^2-1)/(a+b)
其中(t为参数)使得t^2-1能被a+b整除。

manthanein · 发表于 2017-1-20 17:49:43

终于发现了一个。
用欧拉函数可以求出一个解，然后就能求出最小解。（当然这个方法可能慢）

账号		自动登录	找回密码
密码			欢迎注册

[提问] 能否估计