mersenneforum.org Factors of numbers of special form
 Register FAQ Search Today's Posts Mark Forums Read

 2018-09-19, 14:46 #1 CRGreathouse     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 2018-09-19 at 14:48
2018-09-19, 15:42   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by CRGreathouse 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?
https://primes.utm.edu/notes/proofs/MerDiv.html allows us to use the first step $3^n\equiv -k \bmod p$ which gets us that the order of -k mod p times n either divides or is divisible by the order of 3 mod p ( not sure which so I can't go further).

 2018-09-19, 17:20 #3 CRGreathouse     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.
2018-09-19, 17:30   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

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

here's how I got what I did:

$3^n+k\equiv 0 \bmod p; 3^n\equiv -k \bmod p; (3^n)^{ord(-k)}\equiv 3^{n* ord(-k)}\equiv -k^{ord(-k)}\equiv 1\bmod p$ I realize now this needs to divide by the order of 3 mod p and this order divides p-1( 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 2018-09-19 at 17:33

2018-09-21, 15:20   #5
Dr Sardonicus

Feb 2017
Nowhere

53×109 Posts

Quote:
 Originally Posted by CRGreathouse 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?
Ideally, you would want a polynomial f(x) such that f(3) = k, such that x^n + f(x) has an Abelian Galois group for all n. Apart from f(x) = 1 or -1, I don't know any. Generically, you could always take the constant polynomial f(x) = k. The polynomials x^n + k "generically" have a Galois group which is a semidirect product of a cyclic group of order n, and (Z/nZ)* -- the splitting field is "generically" a cyclic extension of degree n over the field of n-th roots of unity.

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 non-Abelian 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 p-1). 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.

2018-09-22, 00:12   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by science_man_88 here's how I got what I did: $3^n+k\equiv 0 \bmod p; 3^n\equiv -k \bmod p; (3^n)^{ord(-k)}\equiv 3^{n* ord(-k)}\equiv -k^{ord(-k)}\equiv 1\bmod p$ I realize now this needs to divide by the order of 3 mod p and this order divides p-1( assuming coprimality) but without forcing the order and parity of it all I fail the intermediate steps.
If the order of 3 has to divide both, then it divides their gcd . Which means factors of p-1 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.

 2018-09-24, 13:55 #7 Dr Sardonicus     Feb 2017 Nowhere 132218 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.
 2019-06-07, 06:48 #8 jwaltos     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 2019-06-07 at 06:56

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Lounge 447 2020-11-13 09:02 Johnatan YAFU 20 2016-04-22 04:33 michael Math 31 2015-09-04 05:57 RedGolpe Factoring 5 2011-11-03 18:38 JuanTutors Data 3 2004-03-29 02:31

All times are UTC. The time now is 10:46.

Mon May 23 10:46:55 UTC 2022 up 39 days, 8:48, 0 users, load averages: 1.33, 1.24, 1.15