mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Abstract Algebra & Algebraic Number Theory

Reply
 
Thread Tools
Old 2018-09-19, 14:46   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default 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
CRGreathouse is offline   Reply With Quote
Old 2018-09-19, 15:42   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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).
science_man_88 is offline   Reply With Quote
Old 2018-09-19, 17:20   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2018-09-19, 17:30   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-09-21, 15:20   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

115778 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2018-09-22, 00:12   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-09-24, 13:55   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

7·23·31 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2019-06-07, 06:48   #8
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

24×52 Posts
Default

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
jwaltos is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 17:40.


Fri Oct 22 17:40:12 UTC 2021 up 91 days, 12:09, 0 users, load averages: 1.24, 1.26, 1.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.