find 4-tuples (e, r, p, s)
问题：找满足如下条件的自然数组 (e,r,p,s)：(1) p是奇素数, p-1 能被 9 整除，s=\frac{p-1}{9}；
(2) r 与 s 互素，即 (r,s)=1；
(3) 2^s 模 p 余 1，即 2^s\equiv 1 (\text{mod} p) ；
(4) 2r+es 与 9 互素，即 (2r+es,9)=1；
(5) 当 x 从 1 以步长 1 递增到 p-1 时，x^r(1+x^(es)) 模 p 的余数的集合刚好有 p-1 个数。
e=1,r=1时我找到了三组：
(1, 1, 35803, 3978)
(1, 1, 86257, 9584)
(1, 1, 152623, 16958)
当e=1时，r>1的情形一组都没有找到. 原帖由 mathabc 于 2009-4-19 19:23 发表 http://bbs.emath.ac.cn/images/common/back.gif
问题：找满足如下条件的自然数组 (e,r,p,s)：
(1) p是奇素数, p-1 能被 9 整除，s=\frac{p-1}{9}；
(2) r 与 s 互素，即 (r,s)=1；
(3) 2^s 模 p 余 1，即 2^s\equiv 1 (\text{mod} p) ；
(4) 2r+es 与 9 互素， ...
帖子的名字好像以前论坛里见大侠们讨论过。
我不懂。不过看你三组前面都是1 1，感觉有点简化题目了。 这个应该不难,总可以选择s=p-1,
于是最后一步变成$2*x^r(mod p)$这好遍历p的同余类,于是(r,p-1)=1就可以了 刚才没有注意到你这里s是指定为${p-1}/9$的,关键在于最后一个条件.
所以可以取e=9使得最后一个条件得以简化 mathe果真洞悉天机。
我忘了还有一个条件 (9,e) = 1 ，这个条件忘了写上.
写程序不难，似乎计算量大的惊人.
[ 本帖最后由 mathabc 于 2009-4-20 13:55 编辑 ] 原帖由 winxos 于 2009-4-19 20:12 发表 http://bbs.emath.ac.cn/images/common/back.gif
帖子的名字好像以前论坛里见大侠们讨论过。
我不懂。不过看你三组前面都是1 1，感觉有点简化题目了。
也没有简化题目，从最简单的算起，于是就从 e=1, r=1 开始。
页:
[1]