Factors of numbers of special form

CRGreathouse · 2018-09-19, 14:46

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?

science_man_88 · 2018-09-19, 15:42

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

CRGreathouse · 2018-09-19, 17:20

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.

science_man_88 · 2018-09-19, 17:30

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.

Dr Sardonicus · 2018-09-21, 15:20

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.

science_man_88 · 2018-09-22, 00:12

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.

Dr Sardonicus · 2018-09-24, 13:55

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.

jwaltos · 2019-06-07, 06:48

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.

2018-09-19, 14:46	#1
CRGreathouse Aug 2006 2²×1,493 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

2019-06-07, 06:48	#8
jwaltos Apr 2012 Standing, top right. 2⁴·23 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
Special whole numbers...	Xyzzy	Lounge	447	2020-11-13 09:02
factoring special form of 1024-bit RSA key	Johnatan	YAFU	20	2016-04-22 04:33
Special Form of Mersenne and Fermat Number Factors	michael	Math	31	2015-09-04 05:57
Factors with special form	RedGolpe	Factoring	5	2011-11-03 18:38
Factors of the Form 7 mod 8	JuanTutors	Data	3	2004-03-29 02:31

2018-09-19, 17:20	#3
CRGreathouse Aug 2006 2²·1,493 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-24, 13:55	#7
Dr Sardonicus Feb 2017 Nowhere 1000011101000₂ 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.