20050807, 01:53  #1 
Aug 2004
Melbourne, Australia
2^{3}·19 Posts 
Knuth's GCD Lemma
For those of you who don't know, Knuth's GCD Lemma states that
gcd(2^a1,2^b1)=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. 
20050807, 13:32  #2  
Jun 2005
98_{10} Posts 
Quote:
2^291 = 233 x 1103 x 2089 2^371 = 233 x 616318177 GCD(2^291,2^371)=233 GCD(29,37)=1 Either case B of Knuth Lemma (webpage ) is incorrect or my understanding of GCD incorrect? 

20050807, 13:49  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
2^371 = 223 x 616318177
Alex 
20050807, 14:41  #4 
Aug 2004
Melbourne, Australia
10011000_{2} 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<q and that s divides 2^p1 and 2^q1. 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. 
20050807, 16:34  #5  
Jun 2005
2·7^{2} Posts 
Quote:


20140408, 20:50  #6 
Jan 2014
2×19 Posts 
*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). Last fiddled with by Qubit on 20140408 at 20:52 Reason: img BB code doesn't work =/ 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
KnuthSchroeppel analysis  akruppa  Factoring  8  20100108 17:01 
Write to Donald Knuth!  cheesehead  Lounge  20  20090817 03:19 