mersenneforum.org Who can give me a proof ?
 Register FAQ Search Today's Posts Mark Forums Read

 2008-10-23, 13:26 #1 aaa120   Oct 2008 24 Posts Who can give me a proof ? 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}]
2009-03-16, 16:02   #2
maxal

Feb 2005

22·32·7 Posts

Quote:
 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.

Last fiddled with by maxal on 2009-03-16 at 16:08

2019-03-08, 07:45   #3
bbb120

Feb 2019
China

59 Posts

Quote:
 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,

2019-03-08, 08:08   #4
bbb120

Feb 2019
China

738 Posts

Quote:
 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)
Code:
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

Last fiddled with by bbb120 on 2019-03-08 at 08:09

2019-03-09, 16:46   #5
Dr Sardonicus

Feb 2017
Nowhere

3×1,481 Posts

Quote:
 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)
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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Lounge 7 2014-06-07 14:33 science_man_88 Science & Technology 7 2010-07-29 13:13 Sounder Information & Answers 3 2007-10-08 00:41 rzr43 Software 1 2004-12-12 03:56 xilman Soap Box 5 2004-02-15 00:38

All times are UTC. The time now is 01:43.

Sun Apr 11 01:43:33 UTC 2021 up 2 days, 20:24, 1 user, load averages: 1.26, 1.52, 1.57