mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2008-10-23, 13:26   #1
aaa120
 
Oct 2008

24 Posts
Question 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}]
aaa120 is offline   Reply With Quote
Old 2009-03-16, 16:02   #2
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by aaa120 View Post
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
maxal is offline   Reply With Quote
Old 2019-03-08, 07:45   #3
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by maxal View Post
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 is offline   Reply With Quote
Old 2019-03-08, 08:08   #4
bbb120
 
bbb120's Avatar
 
Feb 2019
China

738 Posts
Default

Quote:
Originally Posted by bbb120 View Post
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!
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
bbb120 is offline   Reply With Quote
Old 2019-03-09, 16:46   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×1,481 Posts
Default

Quote:
Originally Posted by bbb120 View Post
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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
l'état, c'est moi. Give me what I want, and give it now!!! Stargate38 Lounge 7 2014-06-07 14:33
time to give up on oil ? science_man_88 Science & Technology 7 2010-07-29 13:13
Give back a work? Sounder Information & Answers 3 2007-10-08 00:41
who can give me a p95v237? rzr43 Software 1 2004-12-12 03:56
Oh give me a clone 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.