Revision as of 07:40, 7 December 2024 edit Shashvat Verma (talk \| contribs) Extended confirmed users 1,602 edits →top: DoublE SpaceS RemoveD Tags: Mobile edit Mobile app edit Android app edit App full source ← Previous edit		Revision as of 16:59, 19 December 2024 edit undo Venatus9 (talk \| contribs) 7 edits m small phrasing change Tag: Visual edit Next edit →
Line 12: The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as {{math\|252 {{=}} 21 × 12}} and {{math\|105 {{=}} 21 × 5)}}, and the same number 21 is also the GCD of 105 and {{math\|252 − 105 {{=}} 147}}. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, that number is the GCD of the original two numbers. By [[#Bézout's identity\|reversing the steps]] or using the [[extended Euclidean algorithm]], the GCD can be expressed as a [[linear combination]] of the two original numbers, that is the sum of the two numbers, each multiplied by an [[integer]] (for example, {{math\|21 {{=}} 5 × 105 + (−2) × 252}}). The fact that the GCD can always be expressed in this way is known as [[Bézout's identity]]. The version of the Euclidean algorithm described above—which follows Euclid's original presentation—can ~~take many~~perform subtraction steps recursively to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by [[Gabriel Lamé]] in 1844 ([[Lamé’s Theorem\|Lamé's Theorem]]),<ref>{{Cite journal \|last=Lamé \|first=Gabriel \|year=1844 \|title=Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers \|journal=Comptes Rendus des Séances de l'Académie des Sciences \|language=French \|volume=19 \|pages=867–870}}</ref><ref>{{Cite journal \|last=Shallit \|first=Jeffrey \|date=1994-11-01 \|title=Origins of the analysis of the Euclidean algorithm \|journal=Historia Mathematica \|language=en \|volume=21 \|issue=4 \|pages=401–419 \|doi=10.1006/hmat.1994.1031 \|issn=0315-0860\|doi-access=free }}</ref> and marks the beginning of [[computational complexity theory]]. Additional methods for improving the algorithm's efficiency were developed in the 20th century. The Euclidean algorithm has many theoretical and practical applications. It is used for reducing [[Fraction (mathematics)\|fraction]]s to their [[Irreducible fraction\|simplest form]] and for performing [[Division (mathematics)\|division]] in [[modular arithmetic]]. Computations using this algorithm form part of the [[cryptographic protocol]]s that are used to secure [[internet]] communications, and in methods for breaking these cryptosystems by [[integer factorization\|factoring large composite numbers]]. The Euclidean algorithm may be used to solve [[Diophantine equation]]s, such as finding numbers that satisfy multiple congruences according to the [[Chinese remainder theorem]], to construct [[simple continued fraction\|continued fraction]]s, and to find accurate [[Diophantine approximation\|rational approximations]] to real numbers. Finally, it can be used as a basic tool for proving theorems in [[number theory]] such as [[Lagrange's four-square theorem]] and the [[fundamental theorem of arithmetic\|uniqueness of prime factorizations]].

Euclidean algorithm: Difference between revisions