Talk:Euclid's lemma

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 38.98.147.133 (talk) 20:04, 11 October 2012 (UTC)

New proof

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. 216.239.65.88 (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 (talk • contribs) 12:41, 10 June 2010 (UTC)

Unreferenced template

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)

rewrite

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)

OLD PROOF

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 [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)

As mentioned in Narkiewicz book "The development of Prime Number Theory", original Euclid's proof is incorrect 'cause proposition 20 has no proof (why c = na, d = nb ??). One can proof it using one step of Euclid's algo, but, as far as I know, there is no evidence of this step's existence in original proof. — Preceding unsigned comment added by 2A00:1370:8117:1BBA:A8AF:8EC9:C77B:8215 (talk) 02:57, 24 October 2016 (UTC)

Garbled sentences

This article needs help from someone who is both a subject matter expert in the field and understands English syntax. Some sentences are too messed up for a non-SME to decode into clear prose.2602:306:CDD1:2D00:7076:A115:27CB:15C9 (talk) 20:23, 18 December 2016 (UTC)

It's not subject-matter expertise that is the issue, it's the fact that we're directly quoting from a source that was written in a somewhat old-fashioned style of English. Please do not edit direct quotes, as you did, in an attempt to clean up their grammar. —David Eppstein (talk) 21:03, 18 December 2016 (UTC)

Proposition 19 is false in its current wording

Proposition 19 states:

If four numbers be proportional, the number produced from the first and fourth is equal to the number produced from the second and third; and, if the number produced from the first and fourth be equal to that produced from the second and third, the four numbers are proportional.

There is a note at the end of this which states:

If a ： b＝c ： d, then ad＝bc; and conversely

This is blatantly false, consider the simplest example consisting of x,2x,3x, and 4x. All of them are proportional, but the product of the first and forth is 4x^2, while the second and third produces 6x^2.

I think something has been misquoted here. — Preceding unsigned comment added by 49.199.23.115 (talk • contribs) 09:22, 18 September 2020 (UTC)

It is not true that x:2x = 3x:4x. The first of these two ratios is 1:2 and the second is 3:4, not equal. So this is not a counterexample. —David Eppstein (talk) 16:28, 18 September 2020 (UTC)

I agree that the proposition has errors. The Richard Fitzpatrick translation of the Heiberg text correct it in a way that seems different that Euclid's intentions (which are glossed over in this webpage https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX19.html).

The following is my interpretation which matches the webpage and seems to match Euclid's intentions. It also has a proof for the second case which Richard Fitzpatrick notes is incorrect.

There are errors with this proposition in Fitzpatrick's compendium, its transcription over time, or translation! Euclid means to say that for three given numbers (a, b, and c), find the fourth number such that the ratio of the first two numbers equals the ratio of the last two numbers if this is possible. The book corrects it for the assumption that Euclid was only talking about continuously proportional numbers.

Case 1: Correct. If a:b∷b:c and a and c are prime to one another, then there is no number d that can be found (Book IX, Proposition 17)

Case 2: Incorrect. E.g. 2, 4, 5, and 10. If a:b is not the same as b:c and a and c are prime to one another, then there is a number d=bc/a=ce if b is a multiple (e) of a.

          Proof
               	If b is a multiple of a, then let the multiple by e and thus ae=b.  Let d be the product of e and c (d=ce).  Thus, the same number (e) multiplies a and c to get b and d and so a:c∷b:d.
                  	If b is not a multiple of a, then a and b are prime to one another and are thus the smallest numbers having that ratio (a:b) (Book VII Proposition 14).  Assume that there is a number d such that a:b∷c:d.  Thus, c and d have the same ratio as a and b which have the least numbers of that ratio.  Thus, c and d are multiples of a and b, respectively (the least numbers measure those numbers having the same ratio as them the same number of times, the leading measuring the leading and the following the following).  Thus, c is a multiple of a (a measures c).  But, it was assumed that a and c are prime to one another (a also measures itself and thus it measures both a and c which are prime to one another, which is impossible).  Thus, there is no such d.

Case 3: Correct. If a:b∷b:c then a:b∷b:c∷c:e for e=d/a for d=bc if and only if d is a multiple of a.

Case 4: Correct. If a:b∷b:c then a:b∷b:c∷c:e for e=d/a for d=bc if and only if d is a multiple of a.

Euclid's division lemma

hi, i just wanted to know if the euclid's division lemma is same as euclid's lemma. The page named 'euclid's division lemma' does not exist in wikipedia. Is it known by some other name, or it has to be created. Huzaifa abedeen (talk) 03:54, 30 September 2020 (UTC)Huzaifa abedeen

References

Euclid's division lemma exists in Wikipedia, and is different from Euclid's lemma. D.Lazard (talk) 08:07, 30 September 2020 (UTC)

Proof by induction

Hello,

about that part of the current induction proof:

"Similarly, if n > a one has

$(n-a)q=a(b-q),$

and the same argument shows that n – a and a are coprime. As n – a, q and a are positive, the same is true for b – q. Therefore, one has 0 < a (b − q < ab, and the conclusion follows from the induction hypothesis."

I don't really get how that is already enough to conclude that n divides b. From my point of view, :$(n-a)q=a(b-q)$ together with the induction hypothesis only leads to n – a | b – q, so $p(n-a)=(b-q)$.

Maybe I'm missing something, but if not, I'd suggest using the above equation like this:

$(n-a)b=n(b-q)=np(n-a),$

so by division with n – a:

$b=np$ which leads to the conclusion.

Also, isn't the induction's base clause missing? (ab = 1 which leads to a = b = 1 as long as they are both positive; n arbitrary and positive; n | ab -> n = 1 = a; so we have the first case of the case distinction)

Kind of picking at details here, sorry :D

Regards

Effectively, the proof was incomplete. Hopefully, I have fixed it.

Because strong induction is used, no initial clause is needed. However, the case $n=a=1$ may be considered as the initial clause. D.Lazard (talk) 18:22, 29 March 2022 (UTC)

Thanks!

I think there was a tiny error left and hope my last change fixed that.

You're right that n = a = 1 is basically the initial clause.

(But, generally, doesn't strong induction need some initial clause as well? The way I understand it, the difference is just in the hypothesis as it assumes that the statement holds for all smaller elements instead of just the one predecessor.) RoundEaredSengi (talk) 18:42, 29 March 2022 (UTC)

The base case is always there. In induction, the structure of the proposition itself separates a base case.

$$\forall P\,{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n\,{\bigl (}P(n){\bigr )}{\Bigr )},$$

You see the P(0) there. In strong induction the statement that would be the base case is a particular case of the statement of the strong induction. Note that in "If for all non-negative k < n: P(k), then P(n)", if you particularize to n=0, then the hypothesis "for all non-negative k < 0: P(k)" is vacuously true. Therefore, if the strong induction is going to be satisfied we must have P(0).

All of these is independent of whether a particular proof by strong induction will need to separate a base case in its presentation. Depending on the proposition P in question, it is possible that the case P(0) and perhaps many more cases could need to be proven using separate argumentations from other parts of the proof. So, it is not true that because it is strong induction, a base case is not needed. It is only that because of the structure of this particular proof by strong induction, the base case is already there, as a particular case (the case n=a), of one of the three cases. 75.98.195.50 (talk) 19:41, 10 October 2023 (UTC)

There is actually a step in the proof which I find unclear. When you write the formula $(n-a)q=a(b-q)$, how do you use that $n-a$ and $a$ have no common divisors to show that $(n-a)|(b-q)$? The proof of that fact usually uses prime factorizations, which are in turn shown by using Euclid's lemma, so it makes sense to try to avoid that to not fall into a circular argument. Also induction is done on $ab$ for fixed $n$, so we cannot apply it to $(n-a)|a(b-q)$, even though $a(b-q)<ab$. Or is the induction first done on $n$ and then for each fixed $n$ on $ab$? That should probably be specified for clarity. Ashsan98 (talk) 13:15, 17 December 2024 (UTC)