
Number Theory Number Theory Math Forum 
 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 semiprime 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^635=29 t=3 gcd(292^3,35)= gcd (298,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 counterexample 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: 932 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 conterexamples then this will lead to a new factorization method. Thank you for your counterexample. 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  
June 30th, 2014, 05:18 AM  #7  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
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: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
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  

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 02:10 PM 
arxiv conjecture Prime Numbers  billymac00  Number Theory  3  October 17th, 2013 01:36 PM 
Factorization of large semiprime numbers:a partial solution  Bogauss  Number Theory  58  November 28th, 2011 12:19 PM 
new conjecture on prime numbers .... i hope  islam  Number Theory  6  November 14th, 2010 08:04 AM 
Semiprime numbers and factorization  momo  Number Theory  19  June 23rd, 2008 09:18 AM 