谁能给我一个证明？？？

mathematica

设n是一个大于3的整数，b等于2^(n-1)+1
试证明b不可能是n的倍数！！！！
我用mathematica验证了，n从3到300000000
都是成立的。我只能得到：如果有这样的n，
那么n一定是奇合数！有谁能够证明不存在这样的
n呢？（n大于3）


mathematica的验证代码
Do[If[Mod[PowerMod[2,n-1,n]+1,n]==0,Print[n]],{n,3,3*10^8,2}]

mathematica

如果设n是一个大于3的整数，b等于3^(n-1)+1，
那么倒是存在n，使得b是n的倍数。以下是用
mathematica得到的结果，其代码是：
Do[If[Mod[PowerMod[3, n - 1, n] + 1, n] == 0,
  Print[{n, FactorInteger[n]}]], {n, 3, 10^4}]

我有些相信存在这无数这样的n，但是谁又能够证明呢？
{4,{{2,2}}}
{28,{{2,2},{7,1}}}
{532,{{2,2},{7,1},{19,1}}}
{1036,{{2,2},{7,1},{37,1}}}
{4636,{{2,2},{19,1},{61,1}}}
{6364,{{2,2},{37,1},{43,1}}}

后面的是关于这个数的分解

mathe

原帖由 mathematica 于 2008-11-29 18:04 发表
设n是一个大于3的整数，b等于2^(n-1)+1
试证明b不可能是n的倍数！！！！
我用mathematica验证了，n从3到300000000
都是成立的。我只能得到：如果有这样的n，
那么n一定是奇合数！有谁能够证明不存在这样的
n呢？ ...

Assuming $n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}$
Assuming $p_i-1=2^{s_i}u_i$ where $u_i$ is odd number.
Assuming the ordering of 2 for prime $p_i$ is $2^{h_i}k_i$ where $k_i$ is odd number
We could get $h_1=h_2=...=h_t=h$ and $n-1=2^{h-1}v$ where v is odd number
After that, we could get $1+2^{h-1}-=1+2^{h-1}v=n=p_1p_2...p_t-=1(mod 2^h)$

mathe

For the second one, it is easy to prove 2|n or maybe 4|n

mathematica

真的没有看懂mathe的证明，
不知道是什么意思。

mathe

Assuming the ordering of 2 for prime $p_i$ is $h_i$, it means $2^{2^{h_i}k_i}-=1(mod p_i)$ and $2^{2^{h_i-1}k_i}-=-1(mod p_i)$ ($p_i>2$).
So we could get n-1 is time of $2^{h_i-1}k_i$ but it is not time of $2^{h_i}k_i$. This means the power of 2 in n-1 is $h_i-1$. So we get $h_1=h_2=...=h_t=h$.

mathematica

我觉得你应该从头到尾写一个完整的证明，最好
不要用英语。我要求证明b不可能是n的倍数。
但是你的证明中好像没有这个结果呀。

无心人

呵呵
他家新装的linux没有中文输入法

medie2005

mathe只是分析了一下n的形式,并没有说n是否存在.
我觉得还是可以有n满足2^(n-1)=-1 mod n的.
2^(n-1)=-1 mod n
容易看到,n为奇合数,并且,n的素因子的指数均为1.
phi(n)|2(n-1).
再根据mathe列出的n满足的条件,搜一下.

xiugakei

这个问题是挺有意义的。理论上是存在满足条件的n的,但是这个数应该很大。