|WikiProject Mathematics||(Rated Start-class, High-priority)|
I'd be interested in seeing Euclids proof of proposition 30 on there. It seems onky fitting
Issue with intro wording
"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 188.8.131.52 (talk) 20:04, 11 October 2012 (UTC)
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."
- 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. 184.108.40.206 (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
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)
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
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
In this edit reference for the alternative name "Euclid's first theorem" was requested I have added  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)