谁能给我一个证明？？？

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的,但是这个数应该很大。