My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
June 28th, 2014, 05:30 AM   #1
Senior Member
 
Joined: Dec 2013

Posts: 1,101
Thanks: 40

Conjecture about odd semi-prime numbers

Hi everybody,

Let n=pq where p and q are odd primes.
Let d=(2^k)-n where 2^k is immediately superior to n (example : 2^6 is immediately > to 35=5*7 or 55=5*11 or 39=3*13 )

My conjecture is that it ALWAYS exists at least one number t>0 such as :

gcd (d-(2^t), n) = p or q

Example :

p=5
q=7
n=5*7=35

k=6
d=2^6-35=29

t=3

gcd(29-2^3,35)= gcd (29-8,35)= gcd(21,35)=7

n=39

d=25

t=2

gcd(21,39)=3

If the conjecture is true then it will lead to a new factorization method.

Any counter-example or proof?
mobel is offline  
 
June 28th, 2014, 06:22 AM   #2
Member
 
Joined: Apr 2014
From: norwich

Posts: 84
Thanks: 9

I've tried a couple of examples myself (n = 2073 & n = 122) and neither are a counterexample.

I'll look into trying to prove it.

Last edited by William Labbett; June 28th, 2014 at 06:39 AM.
William Labbett is offline  
June 28th, 2014, 08:28 AM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
The smallest counterexample is 2047.
CRGreathouse is offline  
June 28th, 2014, 08:49 AM   #4
Senior Member
 
Joined: Dec 2013

Posts: 1,101
Thanks: 40

So if there are not lot of conter-examples then this will lead to a new factorization method.
Thank you for your counter-example.

Anyway I have to rephrase my idea or maybe to rethink it.
mobel is offline  
June 28th, 2014, 08:50 AM   #5
Senior Member
 
Joined: Dec 2013

Posts: 1,101
Thanks: 40

I just started 2 days ago to think to a new way to approach the problem.
mobel is offline  
June 30th, 2014, 04:06 AM   #6
Senior Member
 
Joined: Dec 2013

Posts: 1,101
Thanks: 40

Quote:
Originally Posted by CRGreathouse View Post
The smallest counterexample is 2047.
Counter examples less than 10^8???
If I can have an idea it will help to understand why?

Thank you for any help.

My feeling is that there is some mysterious link between the prime numbers and the powers of 2.
mobel is offline  
June 30th, 2014, 05:18 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by mobel View Post
My feeling is that there is some mysterious link between the prime numbers and the powers of 2.
Probably more important is that the 2-adic valuations of 23 and 89 are equal.

Quote:
Originally Posted by mobel View Post
Counter examples less than 10^8???
If I can have an idea it will help to understand why?
If that's a request for further calculation, no thanks -- my program can only find candidates, I have to prove them by hand. 10^8 is a lot bigger than 2047.
CRGreathouse is offline  
June 30th, 2014, 12:58 PM   #8
Newbie
 
Joined: Jun 2014
From: Reno, NV

Posts: 2
Thanks: 0

The first number I tested failed:

==========================
number: 11,096,787,649
found 2 power: 17,179,869,184 = 2^34
d: 6,083,081,535
GCD between 11096787649 and 6083081534 (d - (2^0)) = 1
GCD between 11096787649 and 6083081533 (d - (2^1)) = 1
GCD between 11096787649 and 6083081531 (d - (2^2)) = 1
GCD between 11096787649 and 6083081527 (d - (2^3)) = 1
GCD between 11096787649 and 6083081519 (d - (2^4)) = 1
GCD between 11096787649 and 6083081503 (d - (2^5)) = 1
GCD between 11096787649 and 6083081471 (d - (2^6)) = 1
GCD between 11096787649 and 6083081407 (d - (2^7)) = 1
GCD between 11096787649 and 6083081279 (d - (2^8)) = 1
GCD between 11096787649 and 6083081023 (d - (2^9)) = 1
GCD between 11096787649 and 6083080511 (d - (2^10)) = 1
GCD between 11096787649 and 6083079487 (d - (2^11)) = 1
GCD between 11096787649 and 6083077439 (d - (2^12)) = 1
GCD between 11096787649 and 6083073343 (d - (2^13)) = 1
GCD between 11096787649 and 6083065151 (d - (2^14)) = 1
GCD between 11096787649 and 6083048767 (d - (2^15)) = 1
GCD between 11096787649 and 6083015999 (d - (2^16)) = 1
GCD between 11096787649 and 6082950463 (d - (2^17)) = 1
GCD between 11096787649 and 6082819391 (d - (2^18)) = 1
GCD between 11096787649 and 6082557247 (d - (2^19)) = 1
GCD between 11096787649 and 6082032959 (d - (2^20)) = 1
GCD between 11096787649 and 6080984383 (d - (2^21)) = 1
GCD between 11096787649 and 6078887231 (d - (2^22)) = 1
GCD between 11096787649 and 6074692927 (d - (2^23)) = 1
GCD between 11096787649 and 6066304319 (d - (2^24)) = 1
GCD between 11096787649 and 6049527103 (d - (2^25)) = 1
GCD between 11096787649 and 6015972671 (d - (2^26)) = 1
GCD between 11096787649 and 5948863807 (d - (2^27)) = 1
GCD between 11096787649 and 5814646079 (d - (2^28)) = 1
GCD between 11096787649 and 5546210623 (d - (2^29)) = 1
GCD between 11096787649 and 5009339711 (d - (2^30)) = 1
GCD between 11096787649 and 3935597887 (d - (2^31)) = 1
GCD between 11096787649 and 1788114239 (d - (2^32)) = 1
==========================

It should factor to:
104743
105943

Few more examples:

==========================
number: 4559
found 2 power: 8192 = 2^13
d: 3633
GCD between 4559 and 3632 (d - (2^0)) = 1
GCD between 4559 and 3631 (d - (2^1)) = 1
GCD between 4559 and 3629 (d - (2^2)) = 1
GCD between 4559 and 3625 (d - (2^3)) = 1
GCD between 4559 and 3617 (d - (2^4)) = 1
GCD between 4559 and 3601 (d - (2^5)) = 1
GCD between 4559 and 3569 (d - (2^6)) = 1
GCD between 4559 and 3505 (d - (2^7)) = 1
GCD between 4559 and 3377 (d - (2^8)) = 1
GCD between 4559 and 3121 (d - (2^9)) = 1
GCD between 4559 and 2609 (d - (2^10)) = 1
GCD between 4559 and 1585 (d - (2^11)) = 1
==========================

==========================
number: 319
found 2 power: 512 = 2^9
d: 193
GCD between 319 and 192 (d - (2^0)) = 1
GCD between 319 and 191 (d - (2^1)) = 1
GCD between 319 and 189 (d - (2^2)) = 1
GCD between 319 and 185 (d - (2^3)) = 1
GCD between 319 and 177 (d - (2^4)) = 1
GCD between 319 and 161 (d - (2^5)) = 1
GCD between 319 and 129 (d - (2^6)) = 1
GCD between 319 and 65 (d - (2^7)) = 1
==========================

Last edited by gsorreta; June 30th, 2014 at 01:12 PM.
gsorreta is offline  
July 1st, 2014, 06:45 AM   #9
Senior Member
 
Joined: Dec 2013

Posts: 1,101
Thanks: 40

To analyze carefully the next days.
Maybe a big progress ....
mobel is offline  
July 1st, 2014, 09:58 AM   #10
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by gsorreta View Post
The first number I tested failed:

==========================
number: 11,096,787,649
I guess this depends on how you interpret the conjecture. If you check only 2^t < d then there are lots of counterexamples: 683396 up to 10 million. But if you allow d - 2^t to go negative then you can find examples for 'most' numbers with enough patience. In your example you need to go to t = 17491 to get gcd(6083081535 - 2^17491, 11096787649) = 104743. Of course at this point you're working with 5000-digit numbers just to factor an 11-digit number.

But even if you take t to $+\infty$ you won't find an example that factors 2047.

Last edited by CRGreathouse; July 1st, 2014 at 10:02 AM.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
conjecture, numbers, odd, semiprime



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
To come in june : factorizing big odd semi prime numbers mobel Number Theory 4 February 25th, 2014 01:10 PM
arxiv conjecture Prime Numbers billymac00 Number Theory 3 October 17th, 2013 01:36 PM
Factorization of large semi-prime numbers:a partial solution Bogauss Number Theory 58 November 28th, 2011 11:19 AM
new conjecture on prime numbers .... i hope islam Number Theory 6 November 14th, 2010 07:04 AM
Semi-prime numbers and factorization momo Number Theory 19 June 23rd, 2008 09:18 AM





Copyright © 2017 My Math Forum. All rights reserved.