My Math Forum Conjecture about odd semi-prime numbers

 Number Theory Number Theory Math Forum

 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?
 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.
 June 28th, 2014, 08:28 AM #3 Global Moderator     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.
 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.
 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.
June 30th, 2014, 04:06 AM   #6
Senior Member

Joined: Dec 2013

Posts: 1,101
Thanks: 40

Quote:
 Originally Posted by CRGreathouse 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.

June 30th, 2014, 05:18 AM   #7
Global Moderator

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

 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.
 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 ....
July 1st, 2014, 09:58 AM   #10
Global Moderator

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

 Tags conjecture, numbers, odd, semiprime

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mobel Number Theory 4 February 25th, 2014 01:10 PM billymac00 Number Theory 3 October 17th, 2013 01:36 PM Bogauss Number Theory 58 November 28th, 2011 11:19 AM islam Number Theory 6 November 14th, 2010 07:04 AM momo Number Theory 19 June 23rd, 2008 09:18 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top