mersenneforum.org > Math Knuth's GCD Lemma
 Register FAQ Search Today's Posts Mark Forums Read

 2005-08-07, 01:53 #1 Dougy     Aug 2004 Melbourne, Australia 23·19 Posts Knuth's GCD Lemma 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.
2005-08-07, 13:32   #2
AntonVrba

Jun 2005

9810 Posts

Quote:
 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?

 2005-08-07, 13:49 #3 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 2^37-1 = 223 x 616318177 Alex
 2005-08-07, 14:41 #4 Dougy     Aug 2004 Melbourne, Australia 100110002 Posts 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
2005-08-07, 16:34   #5
AntonVrba

Jun 2005

2·72 Posts

Quote:
 Originally Posted by akruppa 2^37-1 = 223 x 616318177 Alex
oops - tired eyes too much computer work today

 2014-04-08, 20:50 #6 Qubit     Jan 2014 2×19 Posts *I hope it's okay bumping this. The lemma isn't true just for Mersenne numbers: Any integer $a>1$ satisfies $GCD(a^m-1,a^n-1)=a^{GCD(m,n)}-1$. 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). Last fiddled with by Qubit on 2014-04-08 at 20:52 Reason: img BB code doesn't work =/