Knuth's GCD Lemma

[Dougy]

For those of you who don't know, Knuth's GCD Lemma states that
gcd(2^a-1,2^b-1)=2^gcd(a,b)-1 for natural numbers a,b.

I'm curious of why Knuth's name is attached to this lemma, and why it's not just called "GCD lemma" or somesuch.

It's mentioned on Will Edgington's webpage, however I don't see any reason for it's name there.

[AntonVrba]

Originally Posted by Dougy

For those of you who don't know, Knuth's GCD Lemma states that
gcd(2^a-1,2^b-1)=2^gcd(a,b)-1 for natural numbers a,b.

I'm curious of why Knuth's name is attached to this lemma, and why it's not just called "GCD lemma" or somesuch.

It's mentioned on Will Edgington's webpage, however I don't see any reason for it's name there.

2^29-1 = 233 x 1103 x 2089

2^37-1 = 233 x 616318177

GCD(2^29-1,2^37-1)=233

GCD(29,37)=1

Either case B of Knuth Lemma (webpage ) is incorrect or my understanding of GCD incorrect?

[akruppa]

2^37-1 = 223 x 616318177

Alex

[Dougy]

Whoops. Hehe. It's fairly well known that any two distinct Mersenne numbers with prime exponents are coprime. It is a consequence of Knuth's GCD lemma. However it's not required to prove it.

Assume p<q and that s divides 2^p-1 and 2^q-1. Then 2^p = 2^q = 1 (mod s). Which implies that the multiplicative order of 2 modulo s divides p and q, and so they're not both primes.

[AntonVrba]

Originally Posted by akruppa

2^37-1 = 223 x 616318177

Alex

oops - tired eyes too much computer work today

[Qubit]

*I hope it's okay bumping this.

The lemma isn't true just for Mersenne numbers: Any integer satisfies .
In Graham, Knuth and Patashnik's book "Concrete Mathematics", an even more general version is given as an exercise:
i.imgur.com/ROd1fXX.png

I too am curious regarding the source of the said attribution (I've never heard about it outside of the given webpage).