Abrir el menú principal

El algoritmu d'Euclides ye un métodu antiguo y eficiente para calcular el máximu común divisor (MCD). Foi orixinalmente descritu por Euclides na so obra Elementos. El algoritmu d'Euclides estendíu ye un llixeru cambéu que dexa amás espresar al máximu común divisor como una combinación llinial. Esti algoritmu tien aplicaciones en diverses árees como álxebra, teoría de númberos y ciencies de la computación, ente otres. Con unos llixeros cambeos suel ser utilizáu n'ordenadores electrónicos por cuenta de la so gran eficiencia.

Algoritmu orixinal de EuclidesEditar

 
AB y CD los segmentos conmensurables.
 
Exemplu del algoritmu orixinal de Euclides.

Na concepción griega de la matemática, los númberos entendíense como magnitúes xeométriques. Una tema recurrente na xeometría griega ye'l de la conmensurabilidad de dos segmentos: dos segmentos (númberos) AB y CD son conmensurables cuando esiste un tercer segmentu PQ que cabo esactamente un númberu enteru de vegaes nos primeros dos; esto ye, PQ «mide» (mensura: midida) a los segmentos AB y CD.

Non cualquier par de segmentos ye conmensurable, como atoparon los pitagóricos cuando establecen que'l llau y la diagonal d'un cuadráu nun son conmensurables, pero nel casu de dos segmentos conmensurables deseyar topar la mayor midida común posible.

Euclides describe na proposición VI I.2 de los sos Elementos un métodu que dexa topar la mayor midida común posible de dos númberos (segmentos) que nun sían primos ente sigo, anque d'alcuerdu a la dómina tal métodu esplicar en términos xeométricos, lo que s'ilustra na siguiente trescripción.

P'atopar la máxima midida común de dos númberos que nun sían primos ente sigo.

Sían AB y CD los dos númberos que nun son primos unu al otru. Precísase entós atopar la máxima midida común de AB y CD.

Si CD mide AB entós ye una midida común yá que CD midir a sigo mesmu. Y ye manifiestu que tamién ye la mayor midida pos nada mayor a CD puede midir a CD. Pero si CD nun mide a AB entós dalgún númberu va quedar de AB y CD, el menor siendo de cutio restáu del mayor y que va midir al númberu que-y preciede. Porque una unidá nun va quedar pos si nun ye asina, AB y CD van ser primos unu del otru [Prop. VII.1], lo cual ye lo contrario de lo que se supunxo.

Poro, dalgún númberu queda que va midir el númberu que-y preciede. Y seya CD midiendo BE dexando EA menor que sí mesmu y seya EA midiendo DF dexando FC menor que sí mesmu y seya FC midida de AE. Entós, como FC mide AE y AE mide DF, FC va ser entós midida de DF. Y tamién se mide a sigo mesmu. Por tantu tamién va midir tou CD. Y CD mide a BE. Entós CF mide a BE y tamién mide a EA. Asina mide a tou BA y tamién mide a CD. Esto ye, CF mide tantu a AB y CD polo que ye una midida común de AB y CD.

Afirmo que tamién ye la mayor midida común posible porque si nun lu fora, entós un númberu mayor que CF mide a los númberos AB y CD, seya ésti G. Puesto que G mide a CD y CD mide a BE, G tamién mide a BE. Amás, mide a tou BA polo que mide tamién a la borrafa AE. Y AE mide a DF polo que G tamién mide a DF. Mide tamién a tou DC polo que mide tamién a la borrafa CF, ye dicir el mayor mide al menor, lo cual ye imposible.

Poro, nengún númberu mayor a CF puede midir a los númberos AB y CD. Entós CF ye la mayor midida común de AB y CD, lo cual quería demostrase.

En llinguaxe modernu, l'algoritmu descríbese como sigue:

  1. Daos dos segmentos AB y CD (con AB>CD), restamos CD de AB tantes vegaes como seya posible. Si nun hai borrafa, entós CD ye la máxima midida común.
  2. Si llógrase un borrafa EA, ésti ye menor que CD y podemos repitir el procesu: restamos EA tantes vegaes como seya posible de CD. Si a la fin nun queda una borrafa, EA ye la midida común. En casu contrariu llogramos una nueva borrafa FC menor a EA.
  3. El procesu repitir hasta qu'en dalgún momentu nun se llogra borrafa. Entós la última borrafa llograda ye la mayor midida común.

El fechu de que los segmentos son conmesurables ye clave p'asegurar que'l procesu termina tarde o aína

Algoritmu d'Euclides tradicionalEditar

Al estremar   ente   (númberos enteros), llógrase un cociente   y un borrafa  . Ye posible demostrar que'l máximu común divisor de   y   ye'l mesmu qu'el de   y  (Sía c el máximu común divisor de   y  ,.Como   y   estrema a   y a   estrema tamién a  . Si esistiera otru númberu mayor que   qu'estrema a   y a  , tamién estremaría a   , polo que   nun sería'l mcd de   y  , lo que contradiz la hipótesis). Ésti ye'l fundamentu principal del algoritmu. Tamién ye importante tener en cuenta que'l máximu común divisor de cualquier númberu   y   ye precisamente  . Pa fines prácticos, la notación   significa máximu común divisor de   y  .

Según lo antes mentáu, pa calcular el máximu común divisor de 2366 y 273 puede prosiguir de la siguiente manera:

Pasu Operación Significáu
1 2366 estremáu ente 273 ye 8 y sobren 182  
2 273 estremáu ente 182 ye 1 y sobren 91  
3 182 estremáu ente 91 ye 2 y arrayadura 0  

La secuencia d'igualdaes   impliquen que  . Puesto que  , entós conclúyese que  . Este mesmu procedimientu puede aplicase a cualesquier dos númberos naturales. Polo xeneral, si deseyar atopar el máximu común divisor de dos númberos naturales   y  , sígense les siguientes regles:

  1. Si   entós   y l'algoritmu termina #

N'otru casu,   onde   ye'l restu d'estremar   ente  . Pa calcular   utilícense estes mesmes regles

Asuma que llamamos   y  . Aplicando estes regles llógrase la siguiente secuencia d'operaciones:

Pasu Operación Significáu
1   estremáu ente   ye   y sobren    
2   estremáu ente   ye   y sobren    
3   estremáu ente   ye   y sobren    
     
    estremáu ente   ye   y sobren    
    estremáu ente   ye   y arrayadura    

Como la socesión de borrafes va menguando, a la fin una borrafa tien que ser cero y ye nesi momentu cuando l'algoritmu termina. El máximu común divisor ye precisamente   (la última borrafa que nun ye cero).

XeneralizaciónEditar

En realidá l'algoritmu d'Euclides funciona non yá pa los númberos naturales, sinón pa cualesquier elementos nos qu'esista una "división con borrafa". A esti tipu de divisiones llámase-yos divisiones euclidianes y a los conxuntos onde puede definise dicha división llámase-yos dominios euclídeos. Por casu, el conxuntu de los númberos enteros y el de los polinomios con coeficientes racionales son dominios euclídeos porque podemos definir una división con borrafa (vease División polinomial). D'esta manera, puede calculase el máximu común divisor de dos númberos enteros o de dos polinomios.

Por casu, pa calcular el máximu común divisor de los polinomios   y   l'algoritmu d'Euclides suxure la siguiente secuencia d'operaciones:

Pasu Operación Significáu
1   estremáu ente   ye   y arrayadura    
2   estremáu ente   ye   y arrayadura    
3   estremáu ente   ye   y arrayadura 0  

D'esta manera conclúyese qu'el so máximu común divisor ye  .

Descripción formalEditar

Puede espresase esti algoritmu de manera más formal usando pseudocódigo. Nesti casu la espresión " " significa "la borrafa d'estremar   ente  " (vease Aritmética modular). Plantía:Algoritmu Vale la pena notar qu'esti algoritmu nun ye eficiente ser implementáu direutamente nun ordenador, yá que riquiría memorizar tolos valores de  .

Algoritmu d'Euclides estendíuEditar

L'algoritmu d'Euclides estendíu dexa, amás d'atopar un máximu común divisor de dos númberos enteros   y  , espresalo como la mínima combinación llinial d'esos númberos, esto ye, atopar númberos enteros   y   tales que  . Esto xeneralízase tamién escontra cualquier dominiu euclideano.

FundamentosEditar

Esisten delles maneres d'esplicar l'algoritmu d'Euclides estendíu, una de les más comunes consiste na siguiente:

  1. Usar l'algoritmu tradicional de Euclides. En cada pasu, en llugar de "  estremáu ente   ye   y de restu  " escríbese la ecuación   (vease algoritmu de la división).
  2. Esténase'l restu de cada ecuación.
  3. Sustitúyese'l restu de la última ecuación na penúltima, y la penúltima na antepenúltima y asina socesivamente hasta llegar a la primer ecuación, y en tou pasu espresa cada restu como combinación llinial.

Sicasí, n'ares de la comprensión y memorización d'esti algoritmu, ye conveniente conocer la siguiente caracterización. Pa multiplicar dos matrices de tamañu   úsase la siguiente fórmula (vease Productu de matrices):

(1)  

Supóngase que s'utiliza l'algoritmu d'Euclides tradicional pa calcular los valores   y   qu'ende se describen. Per cada valor   calculáu puede formase la matriz  . Usando la ecuación (1) de manera repitida puede calculase el productu de les primeres   matrices d'esti tipu:

 

Resulta ser que los valores   y   tienen la propiedá de que  , esto ye, espresen a   como una combinación llinial de   y  . Particularmente, como   entós tiense  , lo cual ye la solución del problema. Esta propiedá nun tendría de ser sorprendente, pos esta multiplicación de matrices equival al métodu antes descritu onde se substituye cada ecuación na anterior. Ye importante calcular   nesi mesmu orde. La matriz   apaez nel estremu derechu y la matriz   nel esquierdu.

Tornando al primer exemplu, la socesión de cocientes ye  ,   y  . Entós puede calculase

 

Utilizando'l primera renglón d'esta matriz puede lleese que  , esto ye, atopóse la manera d'espresar al máximu común divisor de 2366 y 273 como una combinación llinial.

Descripción formalEditar

Pa espresar l'algoritmu d'Euclides estendíu ye conveniente notar la manera en que se calculen los valores   y   cola multiplicación de matrices:

 

D'esta manera   y amás  . Polo tanto l'algoritmu en pseudocódigo puede espresase como sigue: Plantía:Algoritmu

AplicacionesEditar

Simplificar fraccionesEditar

Al momentu de faer cálculos con fracciones, ye de gran importancia saber cómo simplificales. Por casu, la fracción   ye equivalente con   (vease Númberu racional). De manera más xeneral,   siempres que  . P'amenorgar una fracción cualesquier  , namái se precisa estremar   y   ente'l so máximu común divisor.

Por casu, si deseyar amenorgar  , primero úsase l'algoritmu d'Euclides p'atopar  . Fáense les divisiones   y  . Depués entós conclúyese que  .

Fracciones continuesEditar

La socesión de divisiones que s'efectúen al siguir algoritmu d'Euclides puede ser utilizada pa espresar una fracción cualesquier   como fracción continua. Esto debe a que si   y  , entós

(3)  

Por casu, p'atopar el máximu común divisor de   y   l'algoritmu xenera la siguiente secuencia de divisiones:

Pasu Operación Significáu
1 93164 estremáu ente 5826 ye 15 y sobren 5774  
2 5826 estremáu ente 5774 ye 1 y sobren 52  
3 5774 estremáu ente 52 ye 111 y sobren 2  
4 52 estremáu ente 2 ye 26 y arrayadura 0  

Toes estes ecuaciones podemos facer asemeyaes a la ecuación (3 3):

  1.  
  2.  
  3.  
  4.  

Si sustitúi la segunda ecuación na primera, llógrase

 

Si repite esti procesu de substitución entós llógrase la espresión deseyada:

 

De manera más xeneral, la fracción continua atopada con esti algoritmu siempres ye de formar

 


=== Inversos módulu m===.

Dicimos que dos númberos enteros son congruentes módulu   (anque tamién puede xeneralizase pa cualesquier otru dominiu euclídeo) si al estremalos ente   llogramos la mesma borrafa (vease Congruencia). Por casu, 7 ye congruente con 12 módulu 5 porque al estremar 7 ente 5 y 12 ente 5, en dambos casos llogramos la mesma borrafa (que ye 2). Cuando   ye congruente con   módulu   escríbese  , nel exemplu anterior tiense  . Supóngase que se conocen los valores de  ,   y  , pero que se desconoz el valor   na siguiente congruencia: Plantía:Ecuacion Basta atopar un valor   que satisfaiga:  , pos d'esta manera al multiplicar la ecuación (2) por   va tenese la solución deseyada: Plantía:Ecuacion Al elementu   llámase-y "inversu módulu  " de  . Desafortunadamente esti valor non siempres esiste. Por casu, con   y   nun esiste nengún númberu enteru   tal que  . De fechu esti valor esiste si y namái si   (la esistencia de soluciones depende de la condición  , ente que la unicidá depende de qu'el  ). Entá más, si al usar l'algoritmu d'Euclides estendíu (agora con  ) llógrase  , entós el valor   ye l'inversu módulu   de  . Por casu, deseyar resolver la ecuación Plantía:Ecuacion Entós col algoritmu d'Euclides estendíu llógrase que  . Como   entós 5 tien un inversu módulu  . Entá más, como  , entós esi inversu ye 2. Entós Plantía:Ecuacion Ye dicir que'l valor de   ye  .

Complexidá del algoritmuEditar

 
Gráfica del númberu de divisiones efectuaes nel algoritmu d'Euclides. El colloráu indica poques operaciones, ente qu'el colores eventualmente más azules representen mayor númberu d'operaciones.

El teorema de Lamé afirma que'l casu peor pa esti algoritmu ye cuando se-y pide calcular el máximu común divisor de dos númberos consecutivos de la socesión de Fibonacci. Por casu, si deseyar calcular el máximu común divisor de   y   llógrase la siguiente secuencia d'operaciones:

Pasu Operación Significáu
1 89 estremáu ente 55 ye 1 y sobren 34  
2 55 estremáu ente 34 ye 1 y sobren 21  
3 34 estremáu ente 21 ye 1 y sobren 13  
4 21 estremáu ente 13 ye 1 y sobren 8  
5 13 estremáu ente 8 ye 1 y sobren 5  
6 8 estremáu ente 5 ye 1 y sobren 3  
7 5 estremáu ente 3 ye 1 y sobren 2  
8 3 estremáu ente 2 ye 1 y sobren 1  
9 2 estremáu ente 1 ye 2 y arrayadura 0  

Nesti exemplu reparar que con estos dos númberos de dos díxitos decimales, precísase faer 9 divisiones. Polo xeneral, el númberu de divisiones efectuaes pol algoritmu nunca supera 5 vegaes el númberu de díxitos que tienen estos númberos. En términos de complexidá computacional, esto significa que se riquir   divisiones pa calcular el máximu común divisor de   y   onde  .

El númberu promediu de divisiones efectuaes pol algoritmu tuvo investigándose dende 1968, pero namái hasta apenes l'añu 2002, Brigitte Vallée demostró que si los dos númberos pueden representase con   bits, entós el númberu promediu de divisiones necesaries ye  .

Sicasí, nun basta con saber el númberu de divisiones. Hai que recordar que l'algoritmu d'Euclides funciona tantu pa polinomios como pa númberos enteros, y polo xeneral, cualquier dominiu Euclídeo. En cada casu, la complexidá del algoritmu depende del númberu de divisiones efectuaes y del costo de cada división. Nel casu de los polinomios, el númberu de divisiones ye   onde   ye'l grau de los polinomios.

Implementación en pseudocódigoEditar

Polo xeneral, los algoritmos Plantía:Algref y Plantía:Algref nun son bien apoderaos pa implementase direutamente nun llinguaxe de programación, especialmente porque peracaben muncha memoria. Si nun se precisen los valores entemedios, y namái se deseya calcular el máximu común divisor de dos númberos enteros, convien usar estes variantes:

Plantía:Algoritmu Plantía:Algoritmu Plantía:Algoritmu Plantía:Algoritmu Plantía:Algoritmu Alrodiu de la notación emplegada:

  •   significa "asigne a la variable   el valor actual de  ". En llinguaxes como C, Java, C#, Python y Visual Basic esto significa a cencielles x = y. N'otros llinguaxes como Pascal traducir en a := b, en Maxima ye a : b, en R, S y Ocaml ye x <- y, y inclusive utilízase la flecha x ← y como'l casu d'APL.
  •   significa que primero s'evalúen los valores   y depués asígnase  , etc. En llinguaxes como Python, Ruby o Maxima esta instrucción tien una estructura bien similar, como por casu en Python: (x,y,z) = (a,b,c). N'otros llinguaxes ye necesariu l'usu de variables auxiliares, como por casu en llinguaxe C: aux1 = b; aux2 = c; x = a; y = aux1; z = aux2;.
  •   significa "el cociente d'estremar   ente  ". A esta operación conózse-y tamién como la división truncada porque ataya la parte fraccionaria del númberu. En munchos llinguaxes de programación esto impleméntase a cencielles como a/b. Otres maneres son a\b (Visual Basic) , a div b (Pascal) o bien a//b (Python 3).
  •   significa "la borrafa d'estremar   ente  ". A esta operación conózse-y a cencielles como módulu. En munchos llinguaxes de programación impleméntase como a % b, ente que n'otros ye a mod b (Visual Basic o Pascal) o bien a rem b (Ada).

Ver tamiénEditar

ReferenciesEditar

BibliografíaEditar

Grimaldi (1998). Matemátiques Discreta y Combinatoria. Méxicu: Addison Wesley Longman de Méxicu. ISBN 968-444-324-2.

  • Cárdenes, Humberto; Lluis, Emilio; Raggi, Francisco; Tomás, Francisco (2004). «Divisibilidad», Álgebra Cimeru. Méxicu: Tríes. ISBN 968-24-3783-0.
  • Pérez Siguí, María Luisa (2006). «Divisibilidad», Teoría de Número. Institutu de Matemátiques, UNAM. ISBN 970-32-1170-0.
  • Sánchez Velázquez, Jesús (1998). Introducción al analís d'algoritmo. Méxicu: Tríes. ISBN 968-24-4341-5.
  • Baldor, Aurelio (2008). «Máximu común divisor», Álgebra. Méxicu: Grupu Editorial Patria. ISBN 978-970-817-000-0.

Enllaces esternosEditar



  • Esplicación dinámica del máximu común divisor nesti videu de YouTube[1].
  • En gaussianos[2] pueden vese esplicaciones y exemplos un pocu más avanzaos d'esti algoritmu.