20180919, 14:46  #1 
Aug 2006
3×1,993 Posts 
Factors of numbers of special form
I have a number of special form, let's say N = 3^n + k for n reasonably large and k not too large. What, if anything, can be said about the form of the factors of N? If we can spend some time preprocessing, can we discover anything about the congruence classes the prime factors fall into?
Last fiddled with by CRGreathouse on 20180919 at 14:48 
20180919, 15:42  #2  
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 
Quote:


20180919, 17:20  #3 
Aug 2006
3·1,993 Posts 
If k = 1 mod p then you can look at the order of 3 mod p, yes, but in general I don't have that.

20180919, 17:30  #4  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
here's how I got what I did: I realize now this needs to divide by the order of 3 mod p and this order divides p1( assuming coprimality) but without forcing the order and parity of it all I fail the intermediate steps. Last fiddled with by science_man_88 on 20180919 at 17:33 

20180921, 15:20  #5  
Feb 2017
Nowhere
53×109 Posts 
Quote:
Of course, the special values k = 3^e or 3^e let you cheat, by giving evaluations at x = 3 which are 3^e times the values for k = 1. More generally, you want to know when x  3 is a linear factor of x^n + f(x). The beauty of a polynomial with an Abelian Galois group is that the irreducible factors (mod p) generally all have the same degree, so if you have one linear factor, the polynomial splits completely into linear factors (mod p). When the polynomials g(x) = x^n + f(x) have nonAbelian Galois groups, you can of course force x  3 to be a linear factor of g(x) (mod p) by demanding that g(x) split completely (mod p), but this is not determined entirely by congruences. One can approach the question from a different direction, and ask, for a given k, what primes p can divide 3^n + k for some n. An obvious answer is that, if p does not divide k, and if 3 is a primitive root (mod p), then 3^n == k (mod p) is solvable, and the solutions form a residue class (mod p1). Alas, I do not know any way to determine which primes p have 3 as a primitive root, but Artin's conjecture says a positive proportion do. A bit more generally, if znorder(k, p) divides znorder(3,p) there will be such n, and they will form a residue class (mod znorder(3, p)). So it might be feasible, for a given k, to draw up a list of "small" primes p having one of these two properties, and do some sieving with them. If znorder(k,p) does not divide znorder(3,p), there will still be values of n for which znorder(k,p) divides n*znorder(3,p). You might be able to get something from them. 

20180922, 00:12  #6 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
If the order of 3 has to divide both, then it divides their gcd . Which means factors of p1 coprime with n, need to divide ord(k) mod p to be the ord(3) mod p. Which for someone stupid like me is interesting.

20180924, 13:55  #7 
Feb 2017
Nowhere
13221_{8} Posts 
My previous post to this thread had a nice crop of editing and other mistakes. I left the (Mod p) out of at least one statement.
I misstated the usage of znorder(). It should have been znorder(Mod(3,p)) and so on  I left out the "Mod." Most egregiously, I misstated when x^n + f(x) for a fixed nonzero f(x) in Z[x] has an Abelian Galois group for all positive integers n. Obviously, f(x) can be either +/1 or +/x^e, for any positive integer e. There might be others, but I have no clue as to what they might be. Of course, one can produce Aurifeuillian factorizations of x^n + k in special cases. 
20190607, 06:48  #8 
Apr 2012
Oh oh.
11×41 Posts 
I would start here:
I would look at complex fractional exponents and progress into hyperbolic functions and seek to generalize this statement as far as possible. Once a context has been obtained within which the initial statement is a special case I can then better outline what I'm looking at. Last fiddled with by jwaltos on 20190607 at 06:56 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Special whole numbers...  Xyzzy  Lounge  447  20201113 09:02 
factoring special form of 1024bit RSA key  Johnatan  YAFU  20  20160422 04:33 
Special Form of Mersenne and Fermat Number Factors  michael  Math  31  20150904 05:57 
Factors with special form  RedGolpe  Factoring  5  20111103 18:38 
Factors of the Form 7 mod 8  JuanTutors  Data  3  20040329 02:31 