Talk:Euclid's lemma

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, High-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
High Priority
 Field: Number theory

I'd be interested in seeing Euclids proof of proposition 30 on there. It seems onky fitting

Issue with intro wording[edit]

"It states that if a prime divides the product of two numbers, it must divide at least one of the factors" <-- It's ambiguous whether or not the prime must divide one of the two numbers we multiplied, or if it must divide any one of the factors of the resulting number (which are potentially much more than the two we originally multiplied). — Preceding unsigned comment added by (talk) 20:04, 11 October 2012 (UTC)

New proof[edit]

Perhaps I'm missing something, but the new proof seems to me to use completely circular logic. For example, it says:

"Since a′ < a, and a was chosen as small as possible, (*) must be true for p, a′ and b. Therefore p either divides a′ or divides b."

But (*) is the statement of the lemma itself... how on earth can we use that fact when trying to prove the lemma? JokeySmurf (talk) 15:26, 5 January 2010 (UTC)

First p is chosen to be the smallest prime for which (*) is false. Since (*) is false for p, there are some a and b making it false. But the proof doesn't just choose any a and b for which (*) is false, it chooses them so that a is as small as possible.
Now, since the number a was chosen to be the smallest for which (*) can be false (for the chosen p), and a′ < a, (*) must be true for a′ (and the chosen p and b).
The method is called mathematical induction. It is not circular reasoning, because you use the truth of (*) for smaller values of the variables to establish its truth for larger values. Have a look at Infinite descent and Mathematical induction#Complete induction. You don't really need to know about those things to understand the proof, but the idea is the same. (talk) 12:51, 6 January 2010 (UTC)

as the example quoted N=42 42= 2*3*7

hence every number can be represented as a multiplication of prime numbers

so the main thing to be understood is that every number can be represented by prime numbers —Preceding unsigned comment added by Pankajgarg india (talkcontribs) 12:41, 10 June 2010 (UTC)

Unreferenced template[edit]

With the exception of one link to google books, there are no references in the paper at the moment. It might be good to add some. (In particular, I was not able to locate the alternative proof in any textbooks.) --Kompik (talk) 09:46, 24 July 2011 (UTC)


I have rewritten the article. It now has references. I replaced the "Alternative proof" with a "Euclidean proof". - Virginia-American (talk) 17:13, 5 July 2012 (UTC)


Euclid's lemma is based on Euclid's algorithm. Euclid's algorithm has to be embedded in theorem 1 of Euclidean number theory. The properties and the name encluded in the embedding will be clear if you apply the algorithm. I wrote a good example in the talk page of the site Euclid's algorithm. If you like I can edit another one in your article. Most sites don't use this algorithm, which is a pity and a source of endless twaddle.

Theorem 1 : [Euclid's algorithm] Each pair a, b ε Z+ have a gcd (a, b). This gcd (a, b) can be calculated by Euclid's algorithm and has the following propertiies. (i) Gcd (a, b) ε Ζ+. (ii) Gcd (a, b) is a common divisor of a and b. (iii) Each common divisor of a and b is a divisor of gcd (a, b). (iv) The equation ax + by = gcd (a, b) has a solution in Z. The properties (ii) and (iii) explain the name greatest common divisor.

Theorem 2 : [Euclid's lemma] p prime and p | ab -----> p | a or p | b.

Given p prime, p | ab and assume p is not a divisor of a. Then gcd (p, a) = 1, because the only divisors of p are 1 and p himself but p is by assumption not a divisor of a. Now applying Euclid's algorithm [point (iv)] one concludes : the equation px + ay = gcd (p, a) = 1 has a solution for x and y in Z+. Multiplying this equation by b one gets bpx + bay = b. In this equation p | bpx and p | (ab)x [given]. Thus p | b [their sum]. End.C.W. Vugs (talk) 15:01, 13 April 2013 (UTC)

"Euclidean proof" is overkill[edit]

I find the entire "Euclidean proof" section to be ridiculously excessive. The sheer size of the section gives entirely the wrong impression and is likely to put off casual readers. The only bits that are actually relevant are the last three lines. Just because we want to include Euclid's original proof doesn't mean we have to include every single lemma and proposition leading up to it, by that logic the article on the Pythagorean theorem would include most of Book I of the Elements.

It also buries the artistry in the actual proof. What intermediate steps are embedded in the proof of a theorem, versus which ones are separated out into lemmas, is an expression of the mathematician's feelings on how the mathematical structures under study fit together, and what is the most elegant way of understanding them.

The entire section could be shortened to this:

Since a|bc, a ≠ 0. If b = 0, gcd(a, 0) = 1 implies that a = ±1 . But then a|c. If b ≠ 0, let m = lcm(a, b). Since gcd(a, b) = 1, m = |ab|. Since a|bc and b|bc, bc is a common multiple of a and b. Therefore m|bc, ab|bc, a|c.

The only non-trivial fact that this relies on is the relationship between LCM and GCD, which is elementary number theory. I'm going to make the change, please discuss it here if you're opposed. Gaiacarra (talk) 21:22, 19 September 2013 (UTC)

Also called Euclid's first theorem[edit]

In this edit reference for the alternative name "Euclid's first theorem" was requested I have added [1] one book] where I found this results under this name. If you know other (perhaps more appropriate) references, please, edit the article. --Kompik (talk) 06:24, 25 April 2015 (UTC)

It's a bad name (because it is very far from being the first name in Euclid) but it does indeed appear to be called that. I added another reference, as well as a note pointing out the badness of the name and giving a reference to the result in geometry that is actually Euclid's first theorem. —David Eppstein (talk) 06:45, 25 April 2015 (UTC)