Teste

O algoritmo de Euclides é um dos mais antigos algoritmos ainda em uso.[2] Surge na sua obra Os Elementos (c. 300 a.C.), especificamente nos Livros 7 (Proposições 1–2) e 10 (Proposições 2–3). No Livro 7, o algoritmo é formulado para inteiros, enquanto no Livro 10 é formulado para comprimentos de segmentos lineares (dir-se-ia hoje que estaria formulado para números reais. Comprimentos, áreas e volumes, representados como números reais hoje em dia, não são medidos nas mesmas unidades, e não existe uma unidade natural de comprimento, área ou volume. O conceito de número real era desconhecido à época de Euclides. O último algoritmo é geométrico. O MDC de dois comprimentos a e b corresponde ao maior comprimento g que mede propriamente a e b; por outras palavras, os comprimentos a e b são o resultado da multiplicação do comprimento g por números inteiros.

O algoritmo não foi provavelmente concebido por Euclides, que compilou resultados de matemáticos anteriores nos seus Elementos.[3][4] O matemático e historiador Bartel van der Waerden sugere que o Livro VII provém de um texto em teoria dos números escrito por matemáticos da escola de Pitágoras.[5] O algoritmo era provavelmente conhecido por Eudoxo de Cnido (cerca de 375 a.C.).[2][6] Poderá ainda ser anterior a Eudoxo,[7][8] a julgar pelo uso do termo técnico ἀνθυφαίρεσις (anthyphairesis, subtração recíproca) em trabalhos de Euclides e Aristóteles.[9]

Séculos mais tarde, o algoritmo de Euclides terá sido reinventado de forma independente na Índia e China,[10] sobretudo para resolver equações diofantinas que surgiram relacionadas com a Astronomia e a elaboração de calendários precisos. No final do século V, o matemático indiano e astrónomo Aryabhata descrevu o algoritmo como o "pulverizador",[11] por causa da sua eficácia a resolver equações diofantinas.[12] Embora um caso especial do teorema chinês do resto já fora descrito pelo matemático e astrónomo chinês Sun Tzu,[13] a solução geral foi publicada por Ch’in