El algoritmo de euclides

ronaldchen393 530 views 1 slides Apr 19, 2016

Slide 1 of 1

About This Presentation

Algoritmo de Euclides

Size: 282.92 KB

Language: es

Added: Apr 19, 2016

Slides: 1 pages

Slide Content

R Chén
Página 1 de 1

El Algoritmo de Euclides

Profesor Ronald Chén

Algoritmo de Euclides

El algoritmo de Euclides es sin duda uno de los algoritmos más antiguos y más ampliamente
conocidos. Este es un método de calcular el máximo común divisor (MCD) de dos números enteros a
y b.

Contenido
Algoritmo de Euclides

Algoritmo de Euclides

El algoritmo de Euclides es básicamente una repetición continua del algoritmo de la división de
números enteros. El punto es dividir repetidamente el divisor por el resto hasta que el residuo es 0.
El MCD es el último resto no nulo en este algoritmo. El ejemplo siguiente muestra el algoritmo para
encontrar el MCD de 102 y 38.

&#3627409359;&#3627409358;&#3627409360;=&#3627409360;×&#3627409361;&#3627409366;+&#3627409360;&#3627409364;
&#3627409361;&#3627409366;=&#3627409359;×&#3627409360;&#3627409364;+&#3627409359;&#3627409360;
&#3627409360;&#3627409364;=&#3627409360;×&#3627409359;&#3627409360;+&#3627409360;
&#3627409359;&#3627409360;=&#3627409364;×&#3627409360;+&#3627409358;

El MCD es 2, ya que es el último resto no nulo que aparece antes de que finalice el algoritmo.

Ejemplo

Usar el algoritmo de Euclides para encontrar el MCD de 42823 y 6409.

Tenemos
&#3627409362;&#3627409360;&#3627409366;&#3627409360;&#3627409361;=&#3627409364;&#3627409362;&#3627409358;&#3627409367;×&#3627409364;+&#3627409362;&#3627409361;&#3627409364;&#3627409367;
&#3627409364;&#3627409362;&#3627409358;&#3627409367;=&#3627409362;&#3627409361;&#3627409364;&#3627409367;×&#3627409359;+&#3627409360;&#3627409358;&#3627409362;&#3627409358;
&#3627409362;&#3627409361;&#3627409364;&#3627409367;=&#3627409360;&#3627409358;&#3627409362;&#3627409358;×&#3627409360;+&#3627409360;&#3627409366;&#3627409367;
&#3627409360;&#3627409358;&#3627409362;&#3627409358;=&#3627409360;&#3627409366;&#3627409367;×&#3627409365;+&#3627409359;&#3627409365;
&#3627409360;&#3627409366;&#3627409367;=&#3627409359;&#3627409365;×&#3627409359;&#3627409365;+&#3627409358;

El último resto no nulo es 17, por lo tanto, el MCD es 17.