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

正理

[这个贴子最后由正理在 2011/12/30 09:37am 第 3 次编辑]

φ(29)=28，φ(n101)=100，φ(2929)=2800,
3^2929≡3^129(mod 2929)
3^129≡3^17=3*81^4≡3*6^4≡3*49=147≡2(mod 29)
3^129≡3^29=3*81^7≡3*81*20^6≡41*400^3≡41*(-4)^3≡41*37≡2(mod 101)
所以
3^2929≡2(mod 2929)

guanchunhe

在这里得到的数据都已经通过实际计算得到证明。
现在需要的是能否得到新的数据。

guanchunhe

刚才在百度论坛上看的的一个帖子。转过来供大家欣赏。
我也想到了这种方法，但没有得到结果。
这位朋友得到的确实是一个非常好的结果。
给定a（a>1)和b(b≠0），怎么找到a^n=b(mod n)的解呢？
这个方程在a=2,b=1的时候是无解的，简单证明如下：设p是n最小的素因子，d是2^k=1(mod p)的最小解(k>1),那么d|(p-1),d|n,所以d是比p更小的n的因子，从而d=1,p=1,矛盾。所以a=2,b=1时是无解的。
而在其他情况下，方程几乎总是有解。例如当a=3,b=1时，n=2^k时，3^n-1总能被n整除。
特别地，考察b=1的情况：假如p|n,而n是a^n=1(mod n)的解，那么pn也是方程的解。
而在一般情况下（a>2,b≠0,1),方程的解要复杂的多，但是有一个很好的算法可以求出其中一些特殊的解，以a=3,b=2为例，我们可以假设n=p*q,p、q是不相等的奇素数。那么3^n=3^(pq)=3^p=2(mod q),同理3^q=2(mod p),于是可以这样来找方程的解：先取一个素数p，解出3^t=2(mod p),得t=s*k+f,其中s|(p-1),且3^s=1(mod p),如果（s,f)=1,那么分解3^p-2,如果其中有一个因子q=f(mod s),那么n=pq就是一个解了。
用这个方法，可以求出两个解为n=2929=29*101,以及n=31744873758348589012852097851=97*327266739776789577452083483


2011-12-26 21:47回复

天山草

下面引用由guanchunhe在 2012/01/08 09:48pm 发表的内容：
刚才在百度论坛上看的的一个帖子。转过来供大家欣赏。
我也想到了这种方法，但没有得到结果。
这位朋友得到的确实是一个非常好的结果。

确实是好帖。谢谢guanchunhe的推荐！
“用这个方法，可以求出两个解为n=2929=29*101,以及n=31744873758348589012852097851=97*327266739776789577452083483”
只是 n=31744873758348589012852097851 数字太大了，不好验证。

guanchunhe

检验这个结果应该不会太难，难点在于判定其中较大的因数是否为素数。
到得这个例子，就证明了我在21楼给出的预测。
现在可以得出结论，3^n ≡ 2  mod （n）的解有无穷多。

天山草

下面引用由guanchunhe在 2012/01/09 10:56am 发表的内容：
检验这个结果应该不会太难，难点在于判定其中较大的因数是否为素数。

31744873758348589012852097851确实只有二个因数，就是 97 和327266739776789577452083483

guanchunhe

天山草先生：你可否计算一下  3^97-2=327266739776789577452083483*?

天山草

下面引用由guanchunhe在 2012/01/09 02:50pm 发表的内容：
天山草先生：你可否计算一下  3^97-2=327266739776789577452083483*?

3^97-2 = 19088056323407827075424486287615602692670648961=
        = 327266739776789577452083483 * 58325683619504773267

guanchunhe

先生的计算能力让人佩服，这就说明这个结果确实正确。

天山草

[这个贴子最后由天山草在 2012/01/10 06:50am 第 1 次编辑]

下面引用由guanchunhe在 2012/01/09 07:49pm 发表的内容：
先生的计算能力让人佩服，这就说明这个结果确实正确。

非也，我只不过是用了一个计算软件而已，就是 mathematica。这个软件要是直接算 mod(3^n，n)，当 n 是19088056323407827075424486287615602692670648961时，它根本算不出来。