Editing Euclidean algorithm (section)

=== Euclid's lemma and unique factorization ===
Bézout's identity is essential to many applications of Euclid's algorithm, such as demonstrating the [[Fundamental theorem of arithmetic|unique factorization]] of numbers into prime factors.<ref>{{Harvnb|Stark|1978|pp=26–36}}</ref> To illustrate this, suppose that a number {{math|''L''}} can be written as a product of two factors {{math|''u''}} and {{math|''v''}}, that is, {{math|1=''L'' = ''uv''}}. If another number {{math|''w''}} also divides {{math|''L''}} but is coprime with {{math|''u''}}, then {{math|''w''}} must divide {{math|''v''}}, by the following argument: If the greatest common divisor of {{math|''u''}} and {{math|''w''}} is {{math|1}}, then integers {{math|''s''}} and {{math|''t''}} can be found such that
: {{math|1=1 = ''su'' + ''tw''}}
by Bézout's identity. Multiplying both sides by {{math|''v''}} gives the relation:
: {{math|1=''v'' = ''suv'' + ''twv'' = ''sL'' + ''twv''}}

Since {{math|''w''}} divides both terms on the right-hand side, it must also divide the left-hand side, {{math|''v''}}. This result is known as [[Euclid's lemma]].<ref name="Ore, p. 44">{{Harvnb|Ore|1948|p=44}}</ref> Specifically, if a prime number divides {{math|''L''}}, then it must divide at least one factor of {{math|''L''}}. Conversely, if a number {{math|''w''}} is coprime to each of a series of numbers {{math|''a''<sub>1</sub>}}, {{math|''a''<sub>2</sub>}}, ..., {{math|''a''<sub>''n''</sub>}}, then {{math|''w''}} is also coprime to their product, {{math|''a''<sub>1</sub> × ''a''<sub>2</sub> × ... × ''a''<sub>''n''</sub>}}.<ref name="Ore, p. 44"/>

Euclid's lemma suffices to prove that every number has a unique factorization into prime numbers.<ref>{{Harvnb|Stark|1978|pp=281–292}}</ref> To see this, assume the contrary, that there are two independent factorizations of {{math|''L''}} into {{math|''m''}} and {{math|''n''}} prime factors, respectively
: {{math|1=''L'' = ''p''<sub>1</sub>''p''<sub>2</sub>...''p''<sub>''m''</sub> = ''q''<sub>1</sub>''q''<sub>2</sub>...''q''<sub>''n''</sub>&nbsp;}}.

Since each prime {{math|''p''}} divides {{math|''L''}} by assumption, it must also divide one of the {{math|''q''}} factors; since each {{math|''q''}} is prime as well, it must be that {{math|1=''p'' = ''q''}}. Iteratively dividing by the {{math|''p''}} factors shows that each {{math|''p''}} has an equal counterpart {{math|''q''}}; the two prime factorizations are identical except for their order. The unique factorization of numbers into primes has many applications in mathematical proofs, as shown below.