【趣题征解】求一个正整数 n，使得 3^n ≡ 2  mod （n）

guanchunhe

如果能用手工完成检验，您认为哪个更有价值？

天山草

下面引用由guanchunhe在 2011/11/22 09:44am 发表的内容：
如果能用手工完成检验，您认为哪个更有价值？

那当然是用手工检验更有价值——如果你的检验范围比 mathematica 更大的话。或者，你的算法比 mathematica 更高效的话。

guanchunhe

举一例子：请问天山草先生，如何计算 3^161147 ≡ r   mod （161147） ?

天山草

下面引用由guanchunhe在 2011/11/23 07:56am 发表的内容：
举一例子：请问天山草先生，如何计算 3^161147 ≡ r   mod （161147） ?

如何手工计算这个，不会，一点也不会。若是用软件算，只须一条指令。

guanchunhe

使用软件需要多少时间？
我用手工（结合使用计算器）计算出r=140313 .
您看对不对？

guanchunhe

13^11 ≡ 2   (mod 11）    13^140711 ≡ 2   (mod 140711）
13^5 ≡ 3   (mod 5）      13^287603 ≡ 3   (mod 287603）
13^158287 ≡ 4   (mod 158287）
13^25433 ≡ 5   (mod 25433）
13^7 ≡ 6   (mod 7）   13^8743 ≡ 6   (mod 8743）
13^4975 ≡ 7   (mod （4975）
13^371285 ≡ 8   (mod 371285）
13^37114141 ≡ 9   (mod 37114141）
13^27181907 ≡ 10   (mod 27181907）
13^301823 ≡ 11   (mod 301823）
13^13757837 ≡ 12   (mod 13757837）

天山草

[这个贴子最后由天山草在 2011/11/26 07:19am 第 1 次编辑]

下面引用由guanchunhe在 2011/11/23 10:30am 发表的内容：
使用软件需要多少时间？
我用手工（结合使用计算器）计算出r=140313 .
您看对不对？

你算得正确。用 mathematica 计算 3^161147≡140313 (mod 161147) 用的时间是 1.33357*10^-17 秒，这个时间小到可以忽略不计。但是好像是指数超过 9 位数，软件就不会算了。

guanchunhe

在n<37114141范围内,以13为底数计算n次剩余r,当r=2,3,6,7,8,11时,已经发现重复出现的情况,当r=4,5,9,10,12时,虽然还没有发现重复出现的数据,但我觉得也应该还会发现其重复出现的情况. 特别是,由于我们已经得到7^387497≡6 (mod 387497)和7^789211≡6 (mod 789211), 因此,我们可以预料,3^n ≡2 (mod n) 应该还会有n>2929的解,只不过由于其计算过程中数据过大,一时难以找得到.因此,对这个问题的研究方向,应该是如何建立一套最简单的计算方法.

guanchunhe

暂时没有得到  17^n ≡16  (mod n) 的解。
已得到  19^39959 ≡ 18  (mod 39959) ,19^1076567 ≡ 18  (mod 1076567)
和      23^235 ≡ 22  (mod 235)  , 23^684715 ≡ 22  (mod 684715) , 23^1145503 ≡ 22  (mod 1145503)

guanchunhe

在n=1亿以内，没有找到满足  17^n ≡ 15,16 ( mod n） 的解。
天山草先生能否找到这的解？