View Single Post
Old 2019-04-05, 21:05   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×13×193 Posts
Default Why don't we consider all integers as exponents, not just primes?

Well, all positive integers >1 that is? 21-1 is 1, 20-1 is 0, and 2n-1 for n<0 is a negative real, not an integer, so can't be a Mersenne prime.

For any Mersenne number formed from a composite exponent, the resulting Mersenne number is composite. https://primes.utm.edu/notes/proofs/Theorem2.html Some of the Mersenne number's factors are easily found by deriving them from the prime factors of the composite exponent. The Mersenne number of a composite exponent a*b is not only composite, it is a repdigit, with M(a*b) a repdigit in base 2a with b digits 2a-1, and in base 2b with a digits 2b-1.

Here are 3 ways of looking at it.
Numerical:
If n = a * b, 1<a<n and a<b<n, integers, the Mersenne number has factors f1 = 2a - 1 and f2 = 2b - 1 (and a cofactor). For example, 26 - 1 = 2(2*3) - 1 is divisible by (22-1) and by (23-1); 63 = 3 * 7 * cofactor 3, and 215-1 = 2(3*5) - 1 = 32767 = 7 * 31 * 151 = (23 - 1) * (25 - 1) * cofactor 151.

Algebraic
:
Note in the proof section of https://primes.utm.edu/notes/proofs/Theorem2.html and that r and s can be swapped. For a difference of squares such as 22a-1, substitute 2a=x into x2-1=(x-1)(x+1)
or for a difference of cubes 23a-1, substitute 2a=x into x3-1=(x-1)(x2+x+1)
26 - 1 = (23)2 - 1 = (23-1)(23+1), because this is an x2 - 1
Or
26 - 1 = (22)3 - 1 = (22-1)(24+22+1), because this is an x3 - 1
One factor is sufficient to eliminate an exponent from consideration, but one can continue,
(23+1) = (2+1)(22-21+1) = 3 *3

Visual:
For M(n)=2n-1 where n=a b, M(n) has factors 2a-1 and 2b-1. Such a number is a repdigit in base 2a and in base 2b.
It's similar to being able to tell at a glance that numbers like 99, 999, 9999, and 99999 are divisible by nine (and by 11, 111, 1111, and 11111 respectively).

Consider the small example 230-1 = 1073741823. 30 = 2 * 3 * 5.
22-1 = 3; 23-1=7; 25-1=31.
230-1 in binary is 30 ones bits consecutively, which can be grouped into equal-sized groups in several ways;

first the digits that form prime factors (3, 7, 31);
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 = 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 base 4;
111 111 111 111 111 111 111 111 111 111 = 7 7 7 7 7 7 7 7 7 7 base 8;
11111 11111 11111 11111 11111 11111 = 1F 1F 1F 1F 1F 1F base 32 (sort of; using multidigit hexadecimal to represent the base-32 individual digits here and for large bases below, rather than pedantically adopt different large ASCII or UNICODE symbol sets for one or two lines of uses);

these digits are composite factors (22*3-1 =63, 22*5-1= 1023, 23*5-1 = 32767);
111111 111111 111111 111111 111111 = 3F 3F 3F 3F 3F base 64;
1111111111 1111111111 1111111111 = 3FF 3FF 3FF base 1024;
111111111111111 111111111111111 =7FFF 7FFF base 32768.

Fully factoring it such as via https://www.alpertron.com.ar/ECM.HTM yields
1073 741823 = 32 * 7 * 11 * 31 * 151 * 331
It has Mersenne primes among its prime factors.


(extended with input from Batalov, specifically the polynomial factoring section)


Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1

Last fiddled with by kriesel on 2021-02-07 at 12:04 Reason: slight edit in response to base32 etc. quibble
kriesel is offline