Metraipolis › archive › dc_c665b378e66d

Euclidean algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Euclidean_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T09:24:48.537Z
SHA-256 of the archived text
17a2f7d61b43764bf84568155280be53ba4358d9f210ac03ec1a92732d8e7cad
Stable URL of this page
https://metraipolis.com/documento/dc_c665b378e66d

How to cite

Euclidean algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Euclidean_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_c665b378e66d (Metraipolis archive dc_c665b378e66d, sha256 17a2f7d61b43764bf84568155280be53ba4358d9f210ac03ec1a92732d8e7cad)
BibTeX
@misc{dcc665b378e66d,
  title = {Euclidean algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Euclidean_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_c665b378e66d; sha256 17a2f7d61b43764bf84568155280be53ba4358d9f210ac03ec1a92732d8e7cad},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Euclidean_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC). It is an example of an algorithm, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. 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 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 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 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, 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—may require many subtraction steps 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), 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 fractions to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such 

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Euclidean algorithm» — https://en.wikipedia.org/wiki/Euclidean_algorithm
Wikidata Q230848 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q230848
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Euclidean_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1375335874, consultata il 2026-10-06T08:23:29.837Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 7928b33cf893c4cce7391dc595c7ade6aa292a446154278484e3e9c31b6284d4