Who can give me a proof ?

[aaa120]

Let n is an integer which is great then 3,
b=2^(n-1)+1 ,
Is there anybody who can prove that n
can't be the factor of b？

I verified that there is no counterexample
for n below 300000000.

Until now I can only prove:If there is such
an n ,then n must be an odd composite number !
Maybe it is a problem which is just like Fermat Last Theorem
which is easy to understand but difficult to give a
proof .I guess that there may be no such a
bright man in the world who can prove it !



I verified it by using Mathematica 6.0.
The code is follow:
Do[If[Mod[PowerMod[2,n-1,n]+1,n]==0,Print[n]],{n,3,3*10^8,2}]

[maxal]

Originally Posted by aaa120

Let n is an integer which is great then 3,
b=2^(n-1)+1 ,
Is there anybody who can prove that n
can't be the factor of b？

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.

[bbb120]

Originally Posted by maxal

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.

if 2^(n-1)=-1(mod n),then
2^(2n-2)=1(mod n)
this told me that ordn(2)=2n-2>n
2^eulerphi(n)=1(mod n)
this told me that ordn(2)<eulerphi(n)<n,
contradict!

[bbb120]

Originally Posted by bbb120

if 2^(n-1)=-1(mod n),then
2^(2n-2)=1(mod n)
this told me that ordn(2)=2n-2>n
2^eulerphi(n)=1(mod n)
this told me that ordn(2)<eulerphi(n)<n,
contradict!

Do[If[Mod[PowerMod[3, n - 1, n] + 1, n] == 0, 
  Print[{n, FactorInteger[n]}]], {n, 3, 10^6}]

my proof is not correct,because
3^(28-1)+1=272342767321*28 is multiple of 28
i do not know why

[Dr Sardonicus]

Originally Posted by bbb120

if 2^(n-1)=-1(mod n),then
2^(2n-2)=1(mod n)
this told me that ordn(2)=2n-2>n
2^eulerphi(n)=1(mod n)
this told me that ordn(2)<eulerphi(n)<n,
contradict!

No, it doesn't tell you that. It does tell you that 2n-2 is a multiple of znorder(Mod(2,n)).

A correct proof has already been posted, which I summarize:

If 2^(n-1) == -1 (mod n), it follows that n is odd, and

valuation(n-1,2) < valuation(p-1, 2) for every prime factor p of n,

where valuation(N,2) is the exact number of times 2 divides N.

This is impossible.