论坛 › 趣题妙解 › 这个猜想成立吗？

nnd 发表于 2009-9-5 09:45:47

这个猜想成立吗？

对于任意自然数m，一定存在自然数n，使2^n-1能被2m+1整除．

282842712474 发表于 2009-9-5 09:54:21

就是说$2^n-1$的因数中含有所有的奇数，感觉不会成立

gxqcn 发表于 2009-9-5 10:20:42

猜想是成立的。

由欧拉定理，只要取 $n=\varphi(2m+1)$ 即可。

nnd 发表于 2009-9-5 11:50:42

3# gxqcn
看了一下欧拉定理，确实如此，这个猜想是欧拉定理的一个实例而已。
这个结论如果能够用到大数除法中去，一定是很过瘾的事啊。

nnd 发表于 2009-9-5 14:51:24

关键是，当m很大时怎么样才能够快速地找到n的值呢？

northwolves 发表于 2009-9-5 16:39:58

2m+1 是素数，n=φ(2m+1)=2m
2m+1 是合数p1*p2（P1,P2互质）,n=φ(p1)*φ(p2)
所以，对2m+1 分解质因数即可

gxqcn 发表于 2009-9-5 16:59:57

欧拉函数的计算，本身就要先进行因数分解。

nnd 发表于 2009-9-5 17:47:51

本帖最后由 nnd 于 2009-9-5 17:52 编辑

6# northwolves

这种方法从理论上是没有问题的，但是m很大时，n会比较大，这种方法会很慢。实际上，试验的时候，n可以很小的。

我想用算法找到一个最小的n值，然后用它来加快大数除法的计算。

nnd 发表于 2009-9-5 22:07:07

看来不行，因为有时候n太大了。

如果将条件放宽呢？

对于任意自然数m，求出一个最小的自然数n，满足2^n-k能被2m+1整除．（k可以适当设定为小于2^64的某个数）

gxqcn 发表于 2009-9-6 08:53:54

离散对数问题恐怕对于你原本要解决的问题更要复杂。

查看完整版本: 这个猜想成立吗？