¿Cómo descubrió Euclides el algoritmo para el máximo divisor común?

Answer 1

El algoritmo GCD, en su forma geométrica, era conocido por los pitagóricos y probablemente por otros antes. Es un algoritmo muy natural. Si tiene dos medidas en un plan, por ejemplo, es bueno encontrar una medida común más pequeña para que pueda expresar ambas medidas como múltiplos enteros de la medida común; entonces no tienes que usar fracciones.

¿Cómo encontramos una medida común en términos geométricos? Bueno, si a es la longitud mayor yb es la longitud menor, entonces cualquier medida común de esos dos también es una medida común de ab, que podemos encontrar colocando dos palos de punta a punta. Continuamos restando la longitud más pequeña de la más grande hasta que ambas tengan el mismo tamaño.

Antes de los pitagóricos, se pensaba que el proceso anterior siempre terminaba. Los pitagóricos (tal vez Hippasus) descubrieron que el proceso conduce a un descenso infinito en algunos casos, por lo que no hay una medida común. Hoy entendemos esa situación en términos de números irracionales. Los pitagóricos pueden haber encontrado primero un descenso infinito en la geometría del pentágono (longitudes diagonales y laterales). Un argumento geométrico similar pero más complicado muestra que las diagonales y los lados de un cuadrado no tienen una medida común. Vea el libro de Stepanov De las matemáticas a la programación genérica para una buena discusión.

Answer 2

Ref: algoritmo euclidiano

Parece que no lo descubrió. Era de conocimiento común entre los matemáticos de su tiempo y de antes. Simplemente lo entendió, lo escribió junto con una miríada de otros de sus descubrimientos y lo hizo (y otros teoremas) populares, ya que se consolidó en un solo lugar.