谁能给我一个证明？？？

mathematica

这个问题应该太难了吧。估计没有人能够证明出来！

mathematica

Assume that n>1 that divides 2^(n-1)+1 exists. Then n is odd and we can represent it in the form n = m*2^k +1 where m is odd and k>=1. Since n divides 2^(n-1)+1 = 2^(m*2^k) + 1 so does every prime divisor p of n, implying that the multiplicative order of 2 modulo p must be a multiple of 2^(k+1) and p must be of the form t*2^(k+1) + 1 for some integer t.
Therefore, we've got that n = m*2^k + 1 is the product of prime factors of the form t*2^(k+1) + 1, implying that n-1 is divisible by 2^(k+1). This contradiction proves that the required n does not exist.


谁能读懂上面的证明？

mathe

同我前面的差不多。实际上对于任意a>0,可以证明不存在大于1的奇数n使得$a^{n-1}+1 -=0(mod n)$

mathematica

mathe 发表于 2011-11-24 20:47
同我前面的差不多。实际上对于任意a>0,可以证明不存在大于1的奇数n使得$a^{n-1}+1 -=0(mod n)$

能够证明n存在的话一定是奇数，因此2与n互质
如果2^(n-1)=-1(mod n)
那么2^(2n-2)=1 (mod n)
因此2的阶=2n-2>n
而2^phi(n)=1 (modn)
因此2的阶<=phi(n)<n
矛盾！
这个证明看起来对3^(n-1)+1不是n的倍数应该也成立呀，
但是为什么n=4就是3的情况一个反例呢？28也是反例，
到底什么地方有问题呢？

mathematica

mathe 发表于 2011-11-24 20:47
同我前面的差不多。实际上对于任意a>0,可以证明不存在大于1的奇数n使得$a^{n-1}+1 -=0(mod n)$

还有你能证明，对于3^(n-1)+1是n的倍数的时候，
n一定是4的倍数吗？
下面的都是反例！
{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}}}

{11476,{{2,2},{19,1},{151,1}}}

{19684,{{2,2},{7,1},{19,1},{37,1}}}

{40132,{{2,2},{79,1},{127,1}}}

{80956,{{2,2},{37,1},{547,1}}}

{266476,{{2,2},{7,1},{31,1},{307,1}}}

{280756,{{2,2},{7,1},{37,1},{271,1}}}

{307396,{{2,2},{31,1},{37,1},{67,1}}}

{356644,{{2,2},{163,1},{547,1}}}

{490372,{{2,2},{43,1},{2851,1}}}

{544348,{{2,2},{7,1},{19441,1}}}

{557956,{{2,2},{7,1},{19927,1}}}

{565516,{{2,2},{7,1},{19,1},{1063,1}}}

{572716,{{2,2},{67,1},{2137,1}}}

{808228,{{2,2},{37,1},{43,1},{127,1}}}

mathe

这个我偏向于不成立，也就是应该存在大于2的是2的倍数但不是4的倍数的n使得n|3^{n-1}+1