已知正整数N，求最小的正整数对(a,m)

aimisiyou

已知正整数N，求最小的正整数对（a,m），使得a^1,a^2,a^3……a^n 分别 (mod  m)所得的结果集合为连续的自然数。
如N=3，则（a,m）=(2,5).
若N=29,(a,m)=?

mathe

试验m=31

northwolves

a最小？m最小？还是a+m最小？

aimisiyou

northwolves 发表于 2020-3-7 11:15
a最小？m最小？还是a+m最小？

取a+m最小吧

aimisiyou

mathe 发表于 2020-3-7 11:01
试验m=31

如果N+2=m是质数，则选(a，m),a是m的原根且a^(n +1)（mod  m）  等于1或（n+1）就符合要求了。但若a^(n +1)（mod  m）  不等于1或（n+1）就不妙了。有没有其他的通用方法。

aimisiyou

初步想了下，如果m取大于N的较小奇数，则分别取模后的出现重复几率高，如果m取较大的奇数，取模后分布相对稀疏，也就不容易构成连续自然数。这是个两难问题。难道只有当n为一些特殊值时才有解？

aimisiyou

先找N=7时，（a,m）=?

northwolves

a,m在200以内列表如下：
n=3,(a,m)=(2,5)
n=4,(a,m)=(2,5)
n=5,(a,m)=(3,7)
n=6,(a,m)=(3,7)
n=8,(a,m)=(6,11)
n=9,(a,m)=(2,11)
n=10,(a,m)=(2,11)
n=11,(a,m)=(2,13)
n=12,(a,m)=(2,13)
n=15,(a,m)=(3,17)
n=16,(a,m)=(3,17)
n=17,(a,m)=(2,19)
n=18,(a,m)=(2,19)
n=21,(a,m)=(5,23)
n=22,(a,m)=(5,23)
n=26,(a,m)=(15,29)
n=27,(a,m)=(2,29)
n=28,(a,m)=(2,29)
n=29,(a,m)=(3,31)
n=30,(a,m)=(3,31)
n=34,(a,m)=(19,37)
n=35,(a,m)=(2,37)
n=36,(a,m)=(2,37)
n=39,(a,m)=(6,41)
n=40,(a,m)=(6,41)
n=41,(a,m)=(3,43)
n=42,(a,m)=(3,43)
n=45,(a,m)=(5,47)
n=46,(a,m)=(5,47)
n=50,(a,m)=(27,53)
n=51,(a,m)=(2,53)
n=52,(a,m)=(2,53)
n=56,(a,m)=(30,59)
n=57,(a,m)=(2,59)
n=58,(a,m)=(2,59)
n=59,(a,m)=(2,61)
n=60,(a,m)=(2,61)
n=64,(a,m)=(34,67)
n=65,(a,m)=(2,67)
n=66,(a,m)=(2,67)
n=69,(a,m)=(7,71)
n=70,(a,m)=(7,71)
n=71,(a,m)=(5,73)
n=72,(a,m)=(5,73)
n=77,(a,m)=(3,79)
n=78,(a,m)=(3,79)
n=80,(a,m)=(42,83)
n=81,(a,m)=(2,83)
n=82,(a,m)=(2,83)
n=87,(a,m)=(3,89)
n=88,(a,m)=(3,89)
n=95,(a,m)=(5,97)
n=96,(a,m)=(5,97)
n=98,(a,m)=(51,101)
n=99,(a,m)=(2,101)
n=100,(a,m)=(2,101)

aimisiyou

northwolves 发表于 2020-3-7 18:01
a,m在200以内列表如下：
n=3,(a,m)=(2,5)
n=4,(a,m)=(2,5)

感谢提供这么多结果！
想问一下，断开的N是能够证明不存在对应的(a,m)吗？还是对应的(a,m)太大了。

northwolves

aimisiyou 发表于 2020-3-7 18:45
感谢提供这么多结果！
想问一下，断开的N是能够证明不存在对应的(a,m)吗？还是对应的(a,m)太大了。

不好说，不会证明。

n=7,a,m在50000内无解