Can two Mersenne numbers share a factor? - Page 3

LaurV · 2011-09-08, 07:49

Sorry I was interrupted by my daily duties.

If we try to follow the same steps as for base 2. In all that proof, the key is the affirmation "if k is odd, then k can not divide 2^b". Then it follows k divides 2^a-b-1. And we can continue our subtraction process of the exponents, till we get the gcd(a,b).

Here we can't say that. Or at least, not so easy. If k divides (b^x-1)/(b-1) and k divides (b^y-1)/(b-1), then it divides the difference, which is:
$\frac{b^x-1-b^y+1}{b-1}=\frac{b^x-b^y}{b-1}=\frac{b^y(b^{x-y}-1)}{b-1}=b^y*\frac{b^{x-y}-1}{b-1}$

To be able to continue the subtraction, we have to show that k does not divide b^y. And if so, it would follow that k divides the fraction, and we could continue the "gcd"-ing process.

What do we have now? We know that k divides $\frac{b^y-1}{b-1}$ (unfortunately the term in x is of no use here) and we have to show that in this case k can not divide $b^y$ .

When b is prime, all factors of $b^y$ are either b or $b^\alpha$ with $\alpha$ a factor (eventually improper) of y and it could be obvious they can not divide the fraction, if we expand it as a binomial, there is always the "1" at the end (in fact all terms below alpha, which we can regroup).

When b (and y) are composite, the only thing left is to expand (b^y-1)/(b-1) as a binomial, and see from there what we can do. If we let p be a prime factor of k, then if p divides b^y means p divides b. And in the expansion of the fraction, it will divide all terms, except the last one, which is 1. So we can't have a k that divides both $b^y$ and $\sum_{i=1}^{y}{B_{yi}b^{y-i}}$ , where B's are the binomial coefficients.

only_human · 2011-09-08, 08:50

Quote:

Originally Posted by LaurV

What do we have now? We know that k divides $\frac{b^y-1}{b-1}$ (unfortunately the term in x is of no use here) and we have to show that in this case k can not divide $b^y$ .

One thing, $\frac{b^y-1}{b-1}$ is an integer, so b^y-1 is a multiple of (b-1). So if k divides (b-1), then b^y-1 is also a multiple of k, thus in this case b^y is 1 mod (k). (Not divisible, as we wanted to show)

LaurV · 2011-09-08, 08:56

I also did a small pari/gp script to check if I missed something there. It took me 20 minutes to write it, and I already checked for bases between 3 and 100 for exponents up to 1000, and for bases 3 to 10 for exponents up to 10k. This process took few hours (since I started post #22). There seems not to be any common factor. If I did not miss anything, then the proof should be right

If someone wants to waste his time, you are free to save it with the extension .gp (mine is cfcf.gp) and run it in pari. There is no optimization done.

Code:

cfcf(bstart,bend,plimit,flags,exp1,exp2)=
{
/* "Check For Common Factors" of (b^e-1) and (b^f-1)
  bstart: base to start (first base checked)
  bend:   last base checked
  plimit: last exponent checked
  flags:  use 0 to print only common factors that are > b-1 
          (none, when gcd(e,f) is 1 :D)
    add 1 to have each base printed (when you have just few bases)
    add 2 to have all common factors printed, even if they are =(b-1) 
    add 4 to chech exponents which are not coprime (find their common factor)
    add 8 to check only prime exponent (obviously this cancel flag 4)

  example:
  
    cfcf(3,15,1000,1)
        will check for bases between 3 and 15 inclusive, 
        coprime exponents (including composites) below 1000,
        and it will print each base reached on the way (to show that 
        it is doing some progress)

    cfcf(5,5,10000) 
        will check the base 5 up to (coprimes) exponent 10000, prints nothing
        (except of course any common factors would find, that is none)

  it would make sense to implement something like: (now not implemented, but
        easy to add, unfortunately this hunting makes no sense)
  
  exp1: if present, it will test all (b^y-1) with y>exp1, against b^exp1-1
  exp2: if present, it will test all (b^y-1) with y<exp2, against b^exp2-1
        (could be good for continuation, or raising the exponent limit)

  if last two parameters are both present, it will only give the common factor of 
  (b^ex1-1)/(b-1) and (b^ex2-1)/(b-1) for all bases b between bstart and bend
*/
    for(b=bstart,bend,
        if(bitand(flags,8),
            if(bitand(flags,1),print("base: "b));
            forprime(e=2,plimit,
                forprime(f=e+1,plimit,                
                    x=gcd((b^e-1),(b^f-1));
                    if(x>b-1 || (x>1 && bitand(flags,2)),
                        print(b," : "e" & "f" >> divisible by "x);
                    )
                )
            ),
        /*else*/    
            if(bitand(flags,1),print("base: "b));
            for(e=2,plimit,
                for(f=e+1,plimit,                
                    if(gcd(e,f)==1 || bitand(flags,4),
                        x=gcd((b^e-1),(b^f-1));
                        if(x>b-1 || (x>1 && bitand(flags,2)),
                            print(b," : "e" & "f" >> divisible by "x);
                        )
                    )
                )
            )
        )
    )
}

LaurV · 2011-09-08, 09:06

Quote:

Originally Posted by only_human

So if k divides (b-1)..

We should not be interested in this case. In fact, the most of the factors of the fraction will NOT divide b-1. We expand the fraction as the sum at the end of my post. Of course it is an integer. In fact your post made me have a look again to that sum and I found out I (wrongly) inserted the binomial coefficients there. It was all in my head, did not put it on paper, that's why the mistake. Sorry for that.

$(b^y-1)=(b-1)(b^{y-1}+b^{y-2}+....+b^2+b+1)$

so

$\frac{b^y-1}{b-1}=b^{y-1}+b^{y-2}+....+b^2+b+1$

(that is why is called "repunit" in base b)

So, if p is a prime factor of k, and k divides b^y, then p divides b. So p divides all terms in the expansion, except the last one. That shows the fact that a prime p dividing both b^y and the fraction, can not exist, therefore k can not exist. Unless p=k=1.

only_human · 2011-09-08, 10:20

Just to mention, I have been looking at this paragraph from Chris K. Caldwell's paper "An Amazing Prime Heuristic":

Quote:

Next suppose that the prime q divides R_p(a) with p prime, Then the order of a (mod q) divides p, so is 1 or p. If the order is 1, then a ≡ 1 (mod q), R_p(a) ≡ p and therefore p = q. If the order is p, then since the order divides q -1, we know p divides q - 1. We have shown that every prime divisor q of R_p(a) is either p (and divides a - 1) or has the form kp + 1 for some integer k.

His notation R_p(a) is for the generalized repunit (a^p-1)/(a-1)

LaurV · 2011-09-08, 12:46

Now, that's a different story. Mr Caldwell is probably right there, but I believe he was trying to find the form of the factors, most probably to define some heuristic argument for counting such primes, i.e. to estimate some probability that a repunit is prime for some big base or exponent.

Our case is different. The problem could be re-formulated like: "can two repunits in the (same) base b have a common factor?". And if yes, then when? How? Where? Do their parents know? Etc.

We ca write our repunits, with respectively m and n digits, m>n, in base b, like:

$r_m=b^{m-1}+b^{m-2}+...+b^{n+1}+b^n+b^{n-1}...+b^2+b+1$

and respectively:

$r_n=b^{n-1}+b^{n-2}+.....+b^2+b+1$

and if any k divides both of them, then such k divides the difference, which is

$r_m-r_n=b^{m-1}+b^{m-2}+...+b^{n+1}+b^n$

We take out the common b^n factor, and from there on, is what we discussed already.

NOTE: Please remark there is no (b-1) involved anywhere.

If this reasoning is right, then two repunits in the same base can not share the same factor (beside of the obvious case when the exponents - their numbers of digits - share some factor, and they can be algebraically decomposed).

Case closed.

***********

The possibility of a k dividing (b-1) in fact, raises a new question, unrelated to our problem.

When does a factor of a repunit in base b divide (b-1)? (or is a multiple of b-1, if we accept composite factors).

Taking ten as base, easier to work with it (digits grouping for small exponents, for bigger exponents I got lazy):

(10²-1)/9 = 11, prime
(10³-1)/9 = 111 = 3*37
(10⁴-1)/9 = 11 11 = 11*101
(10⁵-1)/9 = 11111 = 41*271
(10⁶-1)/9 = 11 11 11 = 111 111 = 3*7*11*13*37
(10⁷-1)/9 = 1111111 = 239*4649
(10⁸-1)/9 = 11 11 11 11 = 1111 1111 = 11*73*101*137
(10⁹-1)/9 = 111 111 111 = 3²*37*333667
(10¹⁰-1)/9 = 11 11 11 11 11 = 11111 11111 = 11*41*271*9091
(10¹¹-1)/9 = 11111111111 = 21649*513239
(10¹²-1)/9 = 11 11 11 11 11 11 = 111 111 111 111 = 1111 1111 1111 = 111111 111111 = 3*7*11*13*37*101*9901

(got lazy of groupting the 1's)
(10¹³-1)/9 = 111111111111 = 53*79*265371653
(10¹⁴-1)/9 = 1111111111111 = 11*239*4649*909091
(10¹⁵-1)/9 = 11111111111111 = 3*31*37*41*271*2906161
(10¹⁶-1)/9 = 111111111111111 = 11*17*73*101*137*5882353
(10¹⁷-1)/9 = 1111111111111111 = 2071723*5363222357
(10¹⁸-1)/9 = 11111111111111111 = 3²*7*11*13*19*37*52579*333667
(10¹⁹-1)/9 = 1111111111111111111 = prime
(10²⁰-1)/9 = 11111111111111111111 = 11*41*101*271*3541*9091*27961

So, how many of these factors are factor of (b-1)=9 here? Beside of the one with exponents divisible by 3? There are none.

Can you find any 2's or 5's? (factors of the base?). None too.

That I was talking about.

axn · 2011-09-08, 13:18

Quote:

Originally Posted by LaurV

Here we can't say that. Or at least, not so easy. If k divides (b^x-1)/(b-1) and k divides (b^y-1)/(b-1), then it divides the difference, which is:
$\frac{b^x-1-b^y+1}{b-1}=\frac{b^x-b^y}{b-1}=\frac{b^y(b^{x-y}-1)}{b-1}=b^y*\frac{b^{x-y}-1}{b-1}$

To be able to continue the subtraction, we have to show that k does not divide b^y. And if so, it would follow that k divides the fraction, and we could continue the "gcd"-ing process.

Let p be a common prime factor of (b^x-1)/(b-1) and (b^y-1)/(b-1). It follows that p divides b^x-1 and, more importantly b^y-1. Suppose p divides b^y ==> then we have p dividing two consecutive numbers (b^y and b^y-1) ==> p=1.

Hence, no common factor will divide b^y (or b).

LaurV · 2011-09-08, 13:46

Quote:

Originally Posted by axn

...then we have p dividing two consecutive numbers ...

True. That is the shorter (and nicer) version. It did not occur to me...

R.D. Silverman · 2011-09-08, 14:08

Quote:

Originally Posted by LaurV

Now, that's a different story. Mr Caldwell is probably right there, but I believe he was trying to find the form of the factors, most probably to define some heuristic argument for counting such primes, i.e. to estimate some probability that a repunit is prime for some big base or exponent.

Our case is different. The problem could be re-formulated like: "can two repunits in the (same) base b have a common factor?". .

The answer is still yes.

Let p,q be prime. Assume q | (b^p-1)/(b-1)

Let r = pq. Then q | (b^r-1)/(b^p-1)

i.e. even after dividing out the algebraic factor b^p-1 from b^r-1, b^p-1
and b^r-1 share a common factor: q

e.g. 11 divides 14^5 - 1. But 11 ALSO divides (14^55-1)/(14^5-1)

That is, even after dividing out the algebraic factor 14^5-1 from 14^55-1,
the quotient still shares a common factor with 14^5 - 1.

Hint: Hensel's Lemma.

R.D. Silverman · 2011-09-08, 14:12

Quote:

Originally Posted by R.D. Silverman

The answer is still yes.

Let p,q be prime. Assume q | (b^p-1)/(b-1)

Let r = pq. Then q | (b^r-1)/(b^p-1)

i.e. even after dividing out the algebraic factor b^p-1 from b^r-1, b^p-1
and b^r-1 share a common factor: q

e.g. 11 divides 14^5 - 1. But 11 ALSO divides (14^55-1)/(14^5-1)

That is, even after dividing out the algebraic factor 14^5-1 from 14^55-1,
the quotient still shares a common factor with 14^5 - 1.

Hint: Hensel's Lemma.

Note further: 11 will also divide (14^(11*55) - 1)/(14^55-1) i.e.
even after pulling out the algebraic factor 14^55-1, (and hence the factor
11^2) from 14^605-1, a factor of 11 will still remain.

11 is referred to as an INTRINSIC PRIME FACTOR.

LaurV · 2011-09-08, 14:35

I usually agree with your (tough) posts where you sent the guys directly to the books, and I respect you for your way of thinking and for your past results. I also believe you are too busy with important thinks to get involved too deep in such elementary math as we discuss here. That is why you only read superficially, and in fact missed the part with "except the case when their number of digits share a common factor". As long as I know, 55 and 5 share a common factor (5), and that is why both are divisible by (14^5-1)/13, that is 11*3761. In fact, the bigger one is just a multiple of the small one.

Same case like for 2^5-1 and 2^55-1. Or 2^11-1 and 2^22-1. Etc. Everything is related to that bits (in base b) that you can group x by x...

If you run my script in post #25 with some suitable flag you would find plenty of such "intrinsic factors", prime or not. Could you please give us a counter-example where the exponents were coprime?

2011-09-08, 07:49	#23
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 Posts	Sorry I was interrupted by my daily duties. If we try to follow the same steps as for base 2. In all that proof, the key is the affirmation "if k is odd, then k can not divide 2^b". Then it follows k divides 2^a-b-1. And we can continue our subtraction process of the exponents, till we get the gcd(a,b). Here we can't say that. Or at least, not so easy. If k divides (b^x-1)/(b-1) and k divides (b^y-1)/(b-1), then it divides the difference, which is: $\frac{b^x-1-b^y+1}{b-1}=\frac{b^x-b^y}{b-1}=\frac{b^y(b^{x-y}-1)}{b-1}=b^y\frac{b^{x-y}-1}{b-1}$ To be able to continue the subtraction, we have to show that k does not divide b^y. And if so, it would follow that k divides the fraction, and we could continue the "gcd"-ing process. What do we have now? We know that k divides $\frac{b^y-1}{b-1}$ (unfortunately the term in x is of no use here) and we have to show that in this case k can not divide $b^y$ . When b is prime, all factors of $b^y$ are either b or $b^\alpha$ with $\alpha$ a factor (eventually improper) of y and it could be obvious they can not divide the fraction, if we expand it as a binomial, there is always the "1" at the end (in fact all terms below alpha, which we can regroup). When b (and y) are composite, the only thing left is to expand (b^y-1)/(b-1) as a binomial, and see from there what we can do. If we let p be a prime factor of k, then if p divides b^y means p divides b. And in the expansion of the fraction, it will divide all terms, except the last one, which is 1. So we can't have a k that divides both $b^y$ and $\sum_{i=1}^{y}{B_{yi}b^{y-i}}$ , where B's are the binomial coefficients. Last fiddled with by LaurV on 2011-09-08 at 08:47*

2011-09-08, 12:46	#28
LaurV Romulan Interpreter Jun 2011 Thailand 9611₁₀ Posts	Now, that's a different story. Mr Caldwell is probably right there, but I believe he was trying to find the form of the factors, most probably to define some heuristic argument for counting such primes, i.e. to estimate some probability that a repunit is prime for some big base or exponent. Our case is different. The problem could be re-formulated like: "can two repunits in the (same) base b have a common factor?". And if yes, then when? How? Where? Do their parents know? Etc. We ca write our repunits, with respectively m and n digits, m>n, in base b, like: $r_m=b^{m-1}+b^{m-2}+...+b^{n+1}+b^n+b^{n-1}...+b^2+b+1$ and respectively: $r_n=b^{n-1}+b^{n-2}+.....+b^2+b+1$ and if any k divides both of them, then such k divides the difference, which is $r_m-r_n=b^{m-1}+b^{m-2}+...+b^{n+1}+b^n$ We take out the common b^n factor, and from there on, is what we discussed already. NOTE: Please remark there is no (b-1) involved anywhere. If this reasoning is right, then two repunits in the same base can not share the same factor (beside of the obvious case when the exponents - their numbers of digits - share some factor, and they can be algebraically decomposed). Case closed. *********** The possibility of a k dividing (b-1) in fact, raises a new question, unrelated to our problem. When does a factor of a repunit in base b divide (b-1)? (or is a multiple of b-1, if we accept composite factors). Taking ten as base, easier to work with it (digits grouping for small exponents, for bigger exponents I got lazy): (10²-1)/9 = 11, prime (10³-1)/9 = 111 = 337 (10⁴-1)/9 = 11 11 = 11101 (10⁵-1)/9 = 11111 = 41271 (10⁶-1)/9 = 11 11 11 = 111 111 = 37111337 (10⁷-1)/9 = 1111111 = 2394649 (10⁸-1)/9 = 11 11 11 11 = 1111 1111 = 1173101137 (10⁹-1)/9 = 111 111 111 = 3²37333667 (10¹⁰-1)/9 = 11 11 11 11 11 = 11111 11111 = 11412719091 (10¹¹-1)/9 = 11111111111 = 21649513239 (10¹²-1)/9 = 11 11 11 11 11 11 = 111 111 111 111 = 1111 1111 1111 = 111111 111111 = 371113371019901 (got lazy of groupting the 1's) (10¹³-1)/9 = 111111111111 = 5379265371653 (10¹⁴-1)/9 = 1111111111111 = 112394649909091 (10¹⁵-1)/9 = 11111111111111 = 33137412712906161 (10¹⁶-1)/9 = 111111111111111 = 1117731011375882353 (10¹⁷-1)/9 = 1111111111111111 = 20717235363222357 (10¹⁸-1)/9 = 11111111111111111 = 3²71113193752579333667 (10¹⁹-1)/9 = 1111111111111111111 = prime (10²⁰-1)/9 = 11111111111111111111 = 11411012713541909127961 So, how many of these factors are factor of (b-1)=9 here? Beside of the one with exponents divisible by 3? There are none. Can you find any 2's or 5's? (factors of the base?). None too. That I was talking about. Last fiddled with by LaurV on 2011-09-08 at 13:01

2011-09-08, 14:35	#33
LaurV Romulan Interpreter Jun 2011 Thailand 22613₈ Posts	I usually agree with your (tough) posts where you sent the guys directly to the books, and I respect you for your way of thinking and for your past results. I also believe you are too busy with important thinks to get involved too deep in such elementary math as we discuss here. That is why you only read superficially, and in fact missed the part with "except the case when their number of digits share a common factor". As long as I know, 55 and 5 share a common factor (5), and that is why both are divisible by (14^5-1)/13, that is 113761. In fact, the bigger one is just a multiple of the small one. Same case like for 2^5-1 and 2^55-1. Or 2^11-1 and 2^22-1. Etc. Everything is related to that bits (in base b) that you can group x by x... If you run my script in post #25 with some suitable flag you would find plenty of such "intrinsic factors", prime or not. Could you please give us a counter-example where the exponents were coprime? Last fiddled with by LaurV on 2011-09-08 at 14:49*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Can Mersenne composites share "shape"?	jnml	Miscellaneous Math	31	2018-01-01 01:55
Small inconsistencies between mersenne.org and mersenne.ca factor databases	GP2	mersenne.ca	44	2016-06-19 19:29
6 digit numbers and the mersenne numbers	henryzz	Math	2	2008-04-29 02:05
LLT numbers, linkd with Mersenne and Fermat numbers	T.Rex	Math	4	2005-05-07 08:25
P-1 factoring != "Mersenne numbers to factor"?	James Heinrich	Marin's Mersenne-aries	8	2004-05-17 11:09