mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-08-07, 01:53   #1
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

2308 Posts
Default 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.
Dougy is offline   Reply With Quote
Old 2005-08-07, 13:32   #2
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

2·72 Posts
Default

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?
AntonVrba is offline   Reply With Quote
Old 2005-08-07, 13:49   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

2^37-1 = 223 x 616318177

Alex
akruppa is offline   Reply With Quote
Old 2005-08-07, 14:41   #4
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23×19 Posts
Default

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.
Dougy is offline   Reply With Quote
Old 2005-08-07, 16:34   #5
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

9810 Posts
Default

Quote:
Originally Posted by akruppa
2^37-1 = 223 x 616318177

Alex
oops - tired eyes too much computer work today
AntonVrba is offline   Reply With Quote
Old 2014-04-08, 20:50   #6
Qubit
 
Qubit's Avatar
 
Jan 2014

2·19 Posts
Default

*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 =/
Qubit is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Knuth-Schroeppel analysis akruppa Factoring 8 2010-01-08 17:01
Write to Donald Knuth! cheesehead Lounge 20 2009-08-17 03:19

All times are UTC. The time now is 17:07.

Tue Sep 29 17:07:41 UTC 2020 up 19 days, 14:18, 0 users, load averages: 2.00, 1.90, 1.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.