factoring 2ⁿ-2 equivalent to factoring 2ⁿ-1(I think)

[baih]

2ⁿ1= a*b

factoring 2ⁿ-2 equivalent to factoring 2ⁿ-1

if this condition is met (a-1) divided by (b-1)
then 2ⁿ-1 =1 mod b-1


example
M11 = 0 mod 23 and 88 =0 mod 22
2¹¹-2 = 0 mod 22



M23 = 0 mod 47
2²³-2 = 0 mod 46





M73 = 0 mod 439
2⁷³-2 = 0 mod 438

M83 = 0 mod 167
2⁸³-2 = 0 mod 166

M131 = 0 mod 263
2¹³¹-2 = 0 mod 262

[paulunderwood]

Originally Posted by baih

8<-----SNIP------

M29 = 0 mod 233
2²⁹-2 = 0 mod 232

8<-----SNIP------

(2^29-2)%232
174

[baih]

JUST arror because 2304167 MOD 232 not equal to n1
SO sory 29 is false


2ⁿ-1= a*b this condition is IF (a-1) divided by (b-1)

[Dr Sardonicus]

If p is prime then 2^p - 2 is divisible by 2p. So if q divides 2^p - 1, gcd(q-1, 2^p - 2) is divisible by 2p.

However, 2ⁿ - 2 is divisible by 2 but not by 4 if n > 1. If p is prime and the smallest prime factor q of 2^p - 1 is congruent to 1 (mod 4), q-1 does not divide 2^p - 2.

Consulting a table of factorizations of 2ⁿ - 1, I find that p = 29 (already noted) is the smallest p with this property. The next is p = 53 (q = 6361).

[baih]

greatest common factor
its clear that for a composite numbre n = ab

n-1 divide gcf(a-1,b-1)


if gcf are a big numbre we can use it for factoring n

this what make the contruction of RSA numbre (beware) of making gcf small and does not help for factoring

example

n= 14111 = 103* 137
14110 = 0 MOD 34


and of course gcf(102,136) = 34

[Uncwilly]

So

30526410117453380369827961 is a semi-prime
gcf(a-1,b-1) = 8 a free fact granted by me.

Does this help you find a and b?

n-1 = 2^3×5×17×5827×1288671127×5978327543
so the gcf could be any combination of 1 or more of those.

[baih]

no
becaus 8 very smal
i said earlier it needs to be very large to help

[mathwiz]

Originally Posted by baih

no
becaus 8 very smal
i said earlier it needs to be very large to help

http://factordb.com/index.php?query=2%5E1277-2 is fully factored. Are you saying you can therefore factor 2^1277-1?

[baih]

I DONT try to facto 2^1277-1 BY 2^1277-2
because i know the possibilty to find a large gcf(a-1,b-1) is very very small (excluded)
approximately the gcf < 10 digts it wont do anything if the factor is large

but this does not mean that the method is incorrect

[JeppeSN]

Originally Posted by mathwiz

http://factordb.com/index.php?query=2%5E1277-2 is fully factored. Are you saying you can therefore factor 2^1277-1?

I see an easy factorization of 2^n - 1 by induction: Suppose 2^(n-1) - 1 is factored. Then the factorization of 2^n - 2 is trivial. If we could somehow get the factorization from 2^n - 1 from that, ... /JeppeSN