20191219, 17:31  #1 
"James Short"
Mar 2019
Canada
22_{8} Posts 
How much smaller can "primitive" factors be?
When looking for "easy" to find integers that are forced to be congruent to where the congruence factor is "as large as possible" compared to , are the primitive factors of integers of the form where is a "highly composite number", the best way to find these?
https://en.wikipedia.org/wiki/Highly_composite_number PS: technical question here...….how can I combine a link (reference) into a text while I'm writing it, instead of just writing it at the bottom of my post? Last fiddled with by jshort on 20191219 at 17:45 Reason: edit 
20191219, 18:23  #2  
"Bob Silverman"
Nov 2003
North of Boston
2·3,779 Posts 
Quote:
And I suggest you use standard mathematical quantifiers/notation/terminology. Nor have you defined "easy". And your use of the variable "p" is just plain wrong. Primitive factors of 2^m+1 are 1 mod m. What do you think "p" is? Quote:
anything at all. What method did you have in mind? Saying that factors are 1 mod m does not specify a method. Using words such as "easy", "best", "as large as possible" is meaningless gibberish without quantifying them. The current "best" technique for finding primitive factors consists of (1) trial division by candidates of the form 1 + km for k < B; B is your choice depending on hardware and time constraints. Typically B = O(log^2 (2^m+1)) is a good choice. (1a) perhaps followed by P1, if desired. (2) Followed by ECM; choice of parameters depends on your goals and time constraints. (3) Followed by NFS if time and resources permit. 

20191219, 21:57  #3 
Feb 2017
Nowhere
2×3^{2}×5×71 Posts 
I'm not sure what you mean to be asking. Obviously, the smallest positive integer congruent to 1 modulo any positive integer modulus m is 1.
If you want integers whose prime factors are necessarily congruent to 1 modulo a given modulus, I repost a link to this paper which gives pertinent results about cyclotomic polynomials vis a vis "primitive factors." If you're asking how small the value of, say, can be compared to I don't know off hand. If you're asking about cracking primitive parts into prime factors, I refer you to the previous response. 
20191220, 15:13  #4  
Feb 2017
Nowhere
2×3^{2}×5×71 Posts 
Quote:
I noticed that substituting x = 2 and doing a bit of rearranging gives the crude but obvious bounds K = 0.288788+, and 1/K = 3.4627466+ Substituting x = a for a > 2 gives similar bounds. 

20191221, 16:19  #6 
Feb 2017
Nowhere
2×3^{2}×5×71 Posts 
I find the function
far more interesting than the decimal digits of its evaluation at a particular value of z. I note that is the generating function for Ramanujan's tau function. I also note that, using the above estimate, the question of how much smaller a primitive part of 2^{n}  1 can be than 2^{n} is reduced to the question of how small can be as a function of n. The best you can do here is taking n to be the product of the first umpteen primes, when 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"factors.txt.u1conflict..." files  Flatlander  Linux  3  20110221 02:32 
"On factors of Mersenne numbers"  Seiji Tomita  cheesehead  Math  6  20091215 17:45 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 