What, if anything, can be said about the factors of 2^n - 1 when n is composite?

[ATH]

Originally Posted by CRGreathouse

For example, take 2^9089 - 1 where 9089 = 61 * 149. Of course both 2^61 - 1 and 2^149 - 1 are factors, but what can be said of the remaining factors?

Looking at 2^(23*31)-1 ignoring the factors of 2^23-1 and 2^31-1 the remaining factors are of the form 2*k*23*31 + 1:
http://factordb.com/index.php?query=2%5E713-1

Same here on 2^(37*41)-1: http://factordb.com/index.php?query=2%5E1517-1 including the C418 factor.

In your example 2^(61*149)-1 both the 61426133391562678481131121023 factor and the C2645 are of the form 2*k*61*149 + 1.

[a1call]

Apologies for autocorrect entries by my swipes keyboard.
I know at least one mod will get a kick out of them.
Actually I'm not sure if it was autocorrect or the mod who is responsible.

[R. Gerbicz]

Originally Posted by ATH

Looking at 2^(23*31)-1 ignoring the factors of 2^23-1 and 2^31-1 the remaining factors are of the form 2*k*23*31 + 1:
http://factordb.com/index.php?query=2%5E713-1

Same here on 2^(37*41)-1: http://factordb.com/index.php?query=2%5E1517-1 including the C418 factor.

In your example 2^(61*149)-1 both the 61426133391562678481131121023 factor and the C2645 are of the form 2*k*61*149 + 1.

We lost some people, but this is still not the end of the story, because using advanced math for odd n values for all p prime factors p==1 or 7 mod 8. Compare this fact to the well known theory in the case where n is also prime, because for that polcyclo(n,2)=2^n-1 (Mersenne number) and we know all these.

And you can go further: if n=4*k+2, then for all remaining factors p==1 or 3 mod 8. (notice the difference in the condition).

[LaurV]

This reminds me that long ago I requested eliminating the "exponent must be prime" criteria from mfaktX, or giving the possibility to the user to have a command line switch to disable the primality test - there was the time when I was trying to factor 2^18xx-1 (I forgot the xx, sorry, but it was a composite exponent in 1800's, and right now the FDB looks down too, so I can not look for it) which had (and maybe still has) a composite cofactor of about 300 digits left. At the time the logic was that at least some of the factors may of the form 2*k*a*b+1, and I may get lucky. Here on the forum I got banged by RDS, who understood that I claim that all factors are of this type. The discussion must be somewhere. Which I ignored. At the time he suggested that some factors may NOT be of this form. Of course, I could not prove one way or the other.

Edit: FDB still says "Database repair, will take a day or two."
Grrr... Hoping that some bugs will get fixed too, and some malformed factrors and aliquots will get fixed too! I am dying to see it...

[axn]

Originally Posted by LaurV

there was the time when I was trying to factor 2^18xx-1

Offtopic, but TF on such a small exponent is just waste of time even if we could use mfaktc. ECM is the way to go.

[R. Gerbicz]

Originally Posted by LaurV

This reminds me that long ago I requested eliminating the exponent must be prime" criteria from mfaktX, or giving the possibility to the user to have a command line switch to disable the primality test - there was the time when I was trying to factor 2^18xx-1 (I forgot the xx, sorry, but it was a composite exponent in 1800's, and right now the FDB looks down too, so I can not look for it) which had (and maybe still has) a composite cofactor of about 300 digits left. At the time the logic was that at least some of the factors may of the form 2*k*a*b+1, and I may get lucky. Here on the forum I got banged by RDS, who understood that I claim that all factors are of this type. The discussion must be somewhere. Which I ignored. At the time he suggested that some factors may NOT be of this form. Of course, I could not prove one way or the other.

Yes, that is a crazy restriction, though these are different problems, we are speaking about the divisors of polcyclo(n,2) and this is different from 2^n-1 when n is composite. Note that in n==2 mod 4 case it is giving a different set of remainder classes (p=1 or 3 mod 8), any wheel sieve could handle this, but if your wheel sieve expects that n is prime, then you'll have to rewrite that part also.

For a proof that p==1 mod n is true see for example http://www.maths.lancs.ac.uk/jameson/cyp.pdf the 11th page.

For the extra factor of two saving (what it looks like not discussed there):

Fix the base b=2.
If n is odd and p is a prime divisor of polcyclo(n,2) then 2^n==1 mod p, so x^2==2 mod p is solvable, one solution is 2^((n+1)/2). Hence (2/p)=1 (Legendre symbol), from this p==1 or 7 mod 8.

If n==2 mod 4, then 2^n==1 mod p, so p|2^n-1=(2^(n/2)-1)*(2^(n/2)+1), but it can't divide the first term, because in that case the order would be smaller, so 2^(n/2)==-1 mod p, as above, but now (-2) is a quadratic residue: 1=(-2/p)=(-1/p)*(2/p), these are known values, you get that p==1 or 3 mod 8.

You can work out this for a general b!=2 base also (you will not get exactly the same conditions).

https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem is also interesting, what is in the pdf, using this 2^n-1 has at least one(!!) primitive divisor (for n>0). The only exception is n=1 AND n=6. So yes, you can hunt for this/these primitive divisors, you will find at least one of the 2^n-1 when n is composite!=6 (or prime). Ofcourse in the theorem the primitive prime divisors of 2^n-1 are the (primitive) prime divisors of polcyclo(n,2).

[LaurV]

So, just for fixing it on the math side, RDS can not post in the forum, as he is still banned, but he is reading us from time to time and that is what he wrote to me related to my previous post, in his characteristic style, which, well... this time it may be forgiven in this particular situation, in case I just put in his mouth affirmations that he didn't say... Sorry, but if I did so, it is only my memory getting weak as I get older, and I didn't do it intentionally...

Originally Posted by RDS, few minutes ago

Enough!

Let n be composite. Assume that n is odd.
(if n is even then 2^n-1 splits as the difference of two squares: (2^(n/2) - 1)* (2^(n/2) + 1) )

There are three kinds of factors of 2^n-1.

(1) Algebraic. These are factors of 2^m-1 for m | n.
(2) Intrinsic. If n = p*m and 2^m-1 is divisible by p, then
2^pm -1 will be divisible by p^2 (i.e. you pick up another power of p via Hensel's Lemma)
(3) Primitive. All primitive prime factors of 2^n-1 are
primes that do not divide 2^j - 1 for j < n. All primitive prime factors are 1 mod 2n.

(the emphasis is mine, I mean it is his text, I added the emphasis).

Now I remember this discussion we had long ago, he replied about of the same kind, when I was saying that "if m and n have no common factor, then 2^m-1 and 2^n-1 have no common factor, even if m and/or n are not prime".

Actually, these are the kind of inputs I valued most at him... you know, I am missing him sometimes (not that I know he is reading us... )

[LaurV]

Originally Posted by axn

Offtopic, but TF on such a small exponent is just waste of time even if we could use mfaktc. ECM is the way to go.

For sure I believe you. But as I said, one may get lucky... Both ECM and P-1 have the bad habit of missing small factors because they are not smooth enough... We all like to play lottery from time to time, even if we know that probabilistically, it is fallacious...

[Dr Sardonicus]

Originally Posted by R. Gerbicz

For a proof that p==1 mod n is true see for example http://www.maths.lancs.ac.uk/jameson/cyp.pdf the 11th page.

Sweet! I downloaded it as a handy reference. Thanks for posting the link.

[GP2]

Originally Posted by LaurV

For sure I believe you. But as I said, one may get lucky... Both ECM and P-1 have the bad habit of missing small factors because they are not smooth enough... We all like to play lottery from time to time, even if we know that probabilistically, it is fallacious...

That's true of P−1, but I've seen ECM find very non-smooth factors, sometimes even with prime k.

[LaurV]

They are still "smooth" in their own "elliptic" way. Otherwise ECM would find all factors in order, no skip, no miss.. Think about it!...

Both P-1 and ECM look for factors with some "special" properties. Each in its own way.