Máximo Común Divisor#

Introducción#

En esta sección vamos a definir el concepto de el Máximo Común divisor (mcm). Como ya vimos anteriormente, sabemos que un número puede tener varios divisores. Pensemos lo siguiente, tenemos dos números \(21\) y \(42\) sus respectivos divisores que son \(\{1,3,7,21\}\) y \(\{1,2,3,6,7,21,42\}\), podemos notar que tienen divisores en común pero el más grande que comparten es el \(21.\) Además, exploraremos cómo calcular el Máximo Común Divisor de dos o mas números y examinaremos algunas de sus propiedades importantes.

Definición del máximo común divisor#

Definición 12 (Máximo común divisor)

El máximo común divisor (mcd) de dos enteros \(a\) y \(b\), los cuales no son ambos ceros, es el entero positivo más grande que divide a \(a\) y \(b\); es denotado por \((a,b)\).

En otras palabras \(d=(a,b),\) si las siguientes dos condiciones se satisfacen:

  • \(d|a\) y \(d|b.\)

  • Si \(d'|a\) y \(d'|b\), entonces \(d' \le d\), y además \(d'|d\).

La idea para calcular el máximo común divisor de dos números \(a,b \in \mathbb{Z} \) sería pensar en el conjunto de divisores de \(a\), \(D_a=\{d \text{ tal que } d \in \mathbb{Z} \text{ y } d|a \}\) y en el conjunto de divisores de \(b,\) \(D_b=\{d' \text{ tal que } d' \in \mathbb{Z} \text{ y } d'|b \}\), luego nos fijaríamos en el elemento más grande de \(A\cap B\), y así obtendríamos el mcd.

Ejemplo 32

Encuentra el máximo común divisor de los siguientes números:

  1. \(12\) y \(18.\)

  2. \(12\) y \(25.\)

  3. \(-15\) y \(25.\)

Solución.

  1. Máximo común divisor de \(12\) y \(18.\)

Los divisores de \(12\) serían, \(D_{12} = \{ \pm1,\pm2,\pm3,\pm4,\pm6,\pm12 \}.\)

Los divisores de \(18\) serían, \(D_{18} = \{ \pm1,\pm2,\pm3,\pm6,\pm9,\pm18 \}.\)

Luego tendríamos que \(D_{12} \cap D_{18}=\{\pm1,\pm2,\pm3,\pm6 \}.\)

Si nos fijamos en el elemento mayor del conjunto \(D_{12} \cap D_{18},\) entonces \((12,18)=6.\)

  1. Máximo común divisor de \(12\) y \(25.\)

Los divisores de \(12\) serían, \(D_{12} = \{ \pm1,\pm2,\pm3,\pm4,\pm6,\pm12 \}.\)

Los divisores de \(25\) serían, \(D_{25} = \{ \pm1,\pm5,\pm25 \}.\)

Luego tendríamos que \(D_{12} \cap D_{25}=\{\pm1 \}.\)

Si nos fijamos en el elemento mayor del conjunto \(D_{12} \cap D_{25},\) entonces \((12,25)=1.\)

  1. Máximo común divisor de \(-15\) y \(25.\)

Los divisores de \(-15\) serían, \(D_{-15} = \{ \pm1,\pm3,\pm5,\pm15 \}.\)

Los divisores de \(25\) serían, \(D_{25} = \{ \pm1,\pm5,\pm25 \}.\)

Luego tendríamos que \(D_{-15} \cap D_{25}=\{\pm1,\pm5 \}.\)

Si nos fijamos en el elemento mayor del conjunto \(D_{-15} \cap D_{25},\) entonces \((-15,25)=5.\)

Dado que \((a,-b)=(-a,b)=(-a,-b)=(a,b)\), limitaremos la discusión del máximo común divisor a enteros positivos.

Pensemos lo siguiente, si tenemos dos números \(a\) y \(b\) es cierto que \(1|a\) y que \(1|b\). Entonces el máximo común divisor de dos números siempre existe.

Código para encontrar el máximo común divisor#

El siguiente código calculará el mcd de dos números enteros positivos. Nos mostrará los divisores de los números dados y los que tienen en común, luego buscará el mayor elemento de estos y nos dirá cual es el mcd.

def mcd(a,b):
  lst_i = []
  z = 0
  for i in [a,b] :
    lst_f = []
    for div in range(1,i+1):
      if (i % div) == 0:
        lst_f.append(div)
    lst_i.append(lst_f)
    print("Los divisores de ",i," son ",lst_i[z])
    z += 1
  intA_B = [x for x in lst_i[0] if x in lst_i[1]]
  print("Los divisores comunes de " ,a," y ",b," son", intA_B)
  print("Por tanto el máximo común divisor de ",a," y ",b," es: ",max(intA_B))

mcd(12,18)

Los divisores de  12  son  [1, 2, 3, 4, 6, 12]
Los divisores de  18  son  [1, 2, 3, 6, 9, 18]
Los divisores comunes de  12  y  18  son [1, 2, 3, 6]
Por tanto el máximo común divisor de  12  y  18  es:  6

mcd(85, 63)

Los divisores de  85  son  [1, 5, 17, 85]
Los divisores de  63  son  [1, 3, 7, 9, 21, 63]
Los divisores comunes de  85  y  63  son [1]
Por tanto el máximo común divisor de  85  y  63  es:  1

mcd(726,927)

Los divisores de  726  son  [1, 2, 3, 6, 11, 22, 33, 66, 121, 242, 363, 726]
Los divisores de  927  son  [1, 3, 9, 103, 309, 927]
Los divisores comunes de  726  y  927  son [1, 3]
Por tanto el máximo común divisor de  726  y  927  es:  3

Propiedades del máximo común divisor#

Proposición 10

Sea \((a,b)=d\). Entonces se cumple lo siguiente:

  1. \(\left( \frac{a}{d}, \frac{b}{d} \right)=1.\)

  2. \((a,a-b)=d.\)

Demostración. 1
Sea \(\left( \frac{a}{d}, \frac{b}{d} \right)=d'\).
Debemos mostrar que \(d'=1\). Ya que \(d'\) es un divisor común de \(\frac{a}{d}\) y de \(\frac{b}{d}\) tenemos que existen \(l\) y \(m\) tal que:

\[\frac{a}{d} = ld' \quad \text{ y } \quad \frac{b}{d} = md'.\]
De la ecuaciones anteriores podemos despejar \(a\) y \(b\) obteniendo que:
\[a =ldd' \quad \text{ y } \quad b = mdd'.\]
Podemos notar que \(dd'\) es un factor en común de \(a\) y \(b.\) Luego por la Definición 12 y como \((a,b) = d\) debería pasar que \(dd' \le d,\) así \(d' \le 1.\) Luego como \(d'\) es un entero positivo, concluimos que \(d'=1\). Por lo tanto si \((a,b)=d\), entonces \(\frac{a}{d}\) y \(\frac{b}{d}\) son primos relativos. \(\square\)

Demostración. 2
Sea \((a,a-b)=d'.\)
Debemos mostrar que \(d=d',\) para esto mostraremos que \(d\le d'\) y \(d \ge d'.\)

  • Primero probemos que \(d\le d'\).

Por hipótesis, ya que \(d\) es un divisor común de \(a\) y \(b\) tenemos que existen enteros \(m\) y \(n\) tal que:

\[a=md \quad \text{ y } \quad b=nd.\]
Ahora observemos que:
\[a-b=md - nd=(m-n)d.\]
Así podemos ver que \(d|a\) y también \(d|(a-b).\) Por lo tanto \(d\) es un divisor común de \(a\) y \(a-b.\) Entonces por la definición \(d\) debería ser menor o igual que \((a,a-b),\) esto es, \(d \le d'.\)

  • Ahora probemos que \(d' \le d.\)

Como \(d'\) es un factor común de \(a\) y \(a-b,\) entonces tenemos que existen \(m'\) y \(n'\) tal que:

\[a=m'd' \quad \text{ y } \quad a-b=n'd'.\]
Entonces tenemos que:

\[\begin{align*} a-(a-b) &= m'd' - n'd' \\ b &= (m' - n')d'. \end{align*}\]

Así \(d'\) es un factor común de \(a\) y \(b.\) Como \((a,b) = d,\) nuevamente por definición concluimos que \(d' \le d.\)

Por lo tanto como \(d\le d'\) y \(d\ge d',\) entonces \(d=d'\). \(\square\)

Corolario 4

Sean \(a,\) \(b\) y \(c\) enteros, entonces \((a+bc,b) = (a,b).\)

Demostración. Vamos a demostrar que el divisor común de \(a\) y \(b\) es exactamente el mismo común divisor de \(a+bc\) y \(b.\) Esto probará que \((a+bc,b) = (a,b).\)

Primero, supongamos que \(e\) es el divisor común de \(a\) y \(b.\)
Como \(e|a\) y \(e|b,\) existen enteros \(m\) y \(n\) tales que:

\[a = em \quad \text{ y } \quad b = en.\]
Si multiplicamos la ecuación \(b = en\) por \(c,\) obtenemos que \(bc = enc.\) Si sumamos ambas ecuaciones tenemos que:
\[a + bc = em + enc = e(m+nc).\]
Entonces \(e|(a+bc),\) por lo tanto \(e\) es también un divisor común de \(a+bc\) y \(b.\)

Ahora, supongamos que \(d\) es un divisor común de \(a+bc\) y \(b.\)
Como \(d|(a+bc)\) y \(d|b,\) existen enteros \(m'\) y \(n'\) tales que:

\[a+bc = dm' \quad \text{ y } \quad b = dn'.\]
Si multiplicamos la ecuación \(b = dn'\) por \(-c,\) obtenemos que \(-bc = -dn'c\). Entonces tenemos que:
\[a = a+bc-bc = dm' -dn'c = d(m' - n'c)\]
Entonces \(d|a,\) por lo tanto \(d\) es también un divisor común de \(a\) y \(b.\)
Por lo tanto \((a+bc,b) = (a,b). \square\)

La siguiente propiedad se dejará como ejercicio al lector.

Proposición 11

Sean \(a,b\) y \(c\) cuales quiera enteros positivos. Entonces \((ac,bc)=c\cdot (a,b)\).

El lema de Bézout#

Definición 13 (Combinación lineal entera)

Una combinación lineal entera de los enteros \(a\) y \(b\) es una suma de múltiplos de \(a\) y \(b\), esto es, una suma de la forma \(\alpha \cdot a + \beta \cdot b,\) en donde \(\alpha\) y \(\beta\) son enteros.

Lema 3

El máximo común divisor de los enteros positivos \(a\) y \(b\) es la más pequeña de las combinaciones lineales positivas de \(a\) y \(b\).

Demostración. Sea \(S\) el conjunto de las combinaciones lineales de \(a\) y \(b,\) esto es:

\[S = \{ ma+nb \mid ma+nb>0 , m , n \in \mathbb{Z} \}.\]
Veamos que \(S\) es no vacío.
Ya que \(a>0,\) podemos reescribir \(a\) como \(a = 1\cdot a + 0\cdot b,\) por lo cual \(1\cdot a + 0\cdot b \in S,\) entonces \(S\) es no vacío. Luego por el principio de la Proposición 5, \(S\) tiene un único elemento mínimo digamos \(d.\)
Ahora veamos que \(d = (a,b).\)
Como \(d \in S,\) entonces \(d = \alpha a + \beta b\) para enteros \(\alpha\) y \(\beta.\)

  • Primero veremos que \(d|a\) y \(d|b.\)

Por el Teorema 3 sabemos que existen \(q\) y \(r\) tales que \(a = dq + r,\) en donde \(0 \le r <d.\) Entonces tenemos lo siguiente:

\[\begin{align*} r &= a -dq \\ &= a - (\alpha a + \beta b)q \\ &= a - \alpha aq - \beta bq \\ & = (1 - \alpha q)a + (- \beta q)b. \end{align*}\]

Lo anterior muestra que \(r\) es una combinación lineal de \(a\) y \(b.\)
Si \(r>0,\) entonces \(r \in S.\) Como \(r < d,\) \(r\) es el elemento mas pequeño del conjunto \(S,\) lo cual es una contradicción. Entonces \(r = 0\) y asi \(a = dq,\) por lo tanto \(d|a.\)
También por el Teorema 3 sabemos que existen \(q'\) y \(r'\) tales que \(b = dq' + r',\) en donde \(0 \le r' <d.\) Entonces tenemos lo siguiente:

\[\begin{align*} r' &= b -dq' \\ &= b - (\alpha a + \beta b)q' \\ &= b - \alpha aq' - \beta bq' \\ & = (1 - \beta q')b + (- \alpha q')a. \end{align*}\]

Lo anterior muestra que \(r'\) es una combinación lineal de \(a\) y \(b.\)
Si \(r'>0,\) entonces \(r' \in S.\) Como \(r' < d,\) \(r'\) es el elemento mas pequeño del conjunto \(S,\) lo cual es una contradicción. Entonces \(r' = 0\) y asi \(b = dq',\) por lo tanto \(d|b.\)
Por lo tanto como \(d|a\) y \(d|b,\) \(d\) es un divisor común de \(a\) y \(b.\)

  • Por último veamos que cualquier divisor común \(d'\) de \(a\) y \(b\) es menor que \(d.\)

Como \(d'|a\) y \(d'|b\), por la Proposición 2 tenemos que \(d'|(\alpha a + \beta b),\) por lo cual \(d'|d.\) Entonces \(d' \le d.\)

Así, por lo anterior concluimos que \(d = (a,b)\). \(\square\)

Del lema anterior se deduce lo siguiente.

Teorema 10

Si \(d=(a,b)\) y \(d'\) es cualquier divisor común de \(a\) y \(b\), entonces \(d' \mid d\).

Ejemplo 33

Expresa \((9,12)\) como una combinación lineal de \(9\) y \(12.\)

Solución.

Notemos que \((9,12) = 3.\)
Ahora necesitamos buscar \(\alpha\) y \(\beta\) tales que \(\alpha \cdot 9 + \beta \cdot 12 = 3.\)
Hasta ahora no tenemos un método para encontrar a \(\alpha\) y \(\beta,\) además de que estos valores no son únicos.
Una manera de hacerlo es fijarnos en los múltiplos de cada número y buscar que la diferencia entre estos sea \(3,\) es decir:
Los múltiplos de 9 son \(\{9,18,\check{27},36,\check{45},54,\ldots \}.\)
Los múltiplos de 12 son \(\{12,\check{24},36,\check{48},60,\ldots \}.\)
Podemos notar que \(27 - 24 = 3\) y también \(48-45 = 3,\) entonces podríamos formas las siguientes combinaciones lineales:

  • \(\alpha = 3\) y \(\beta = -2,\) entonces \(3\cdot 9 + (-2)\cdot 12 = 3.\)

  • \(\alpha = -5\) y \(\beta = 4,\) entonces \((-5)\cdot 9 + 4\cdot 12 = 3.\)

Corolario 5

Si \(a|c\) y \(b|c\) y además \((a,b)=1,\) entonces \(ab|c.\)

Demostración. Por hipótesis tenemos que \(a|c\) y \(b|c,\) entonces existen \(m\) y \(n\) tales que:

\[c = ma \quad \text{ y } \quad c = nb.\]
Además como \((a,b) = 1,\) por el Lema 3 tenemos que \(\alpha a + \beta b = 1,\) para algunos enteros \(\alpha\) y \(\beta.\)
Ahora si multiplicamos por \(c\) la ecuación y luego sustituimos la primer \(c\) por \(nb\) y la segunda \(c\) por \(ma,\) tenemos lo siguiente:

\[\begin{align*} \alpha a + \beta b &= 1 \\ \alpha ac + \beta bc &= c \\ \alpha anb + \beta bma &= c \\ ab ( \alpha n + \beta m) &= c \end{align*}\]

Por lo tanto \(ab|c. \square\)

Definición de primos relativos#

Definición 14 (Primos relativos)

Se dice que dos enteros \(a\) y \(b\) son primos relativos si se cumple que su máximo común divisor es 1, es decir \((a,b)=1\).

Ejemplo 34

Por ejemplo \(6\) y \(35\) son primos relativos, ya que los divisores de \(6\) son \(\{ 1,2,3,6 \}\) y los divisores de \(35\) son \(\{ 1,5,7,35 \}.\) Por lo tanto \((6,35)=1.\)

Teorema 11

Dos enteros positivos \(a\) y \(b,\) son primos relativos si y solo si existen enteros \(\alpha\) y \(\beta\) tales que \(\alpha a + \beta b = 1.\)

Demostración. Tenemos que demostrar las dos contenciones.

  • Primero tomemos por hipótesis que \(a\) y \(b\) son primos relativos.
    Entonces \((a,b) = 1\). Luego por el Lema 3 existen \(\alpha\) y \(\beta\) tales que \(\alpha a + \beta b = 1.\)

  • Ahora tomemos por hipótesis que \(\alpha a + \beta b = 1.\)
    Supongamos que \((a,b) = d.\) Luego como \(d|a\) y \(d|b\) por la propiedad \(4\) de la Proposición 2 tenemos que \(d|(\alpha a + \beta b) = 1,\) de lo anterior tenemos que \(d|1,\) entonces \(d = 1\). Por lo tanto \((a,b)=1. \square\)

Corolario 6

Si \(a\) y \(b\) son primos relativos \((a,b)=1,\) y si \(a|bc,\) entonces \(a|c.\)

Demostración. Como \(a\) y \(b\) son primos relativos tenemos que \((a,b)=1.\) Entonces por el Teorema 11 podemos reescribir el máximo común divisor como una combinación lineal con \(\alpha\) y \(\beta\) enteros, esto es, \(\alpha a+\beta b=1.\) Luego si multiplicamos esta ecuación por \(c\) tenemos que:

\[\alpha ac+\beta bc=c.\]

De lo anterior tenemos que \(a | \alpha ac\) y \(a | \beta bc,\) entonces \(a| (\alpha ac+\beta bc)\) y por lo tanto \(a|c. \square\)

El máximo común divisor de \(n\) enteros positivos#

Definición 15 (Máximo común divisor (varios enteros))

El máximo común divisor de \(n \text{ } (n\ge 3)\) enteros positivos \(a_1,a_2,...,a_n\) es el entero positivo mas grande que divide a cada uno de los enteros \(a_n.\) De igual forma es denotado como \((a_1,a_2,...,a_n).\)

Ejemplo 35

El máximo común divisor de \(12,18\) y \(28\) sería \((12,18,28)=2\) ya que \(2\) es el entero positivo mas grande que divide a los tres números.
El máximo común divisor de \(12,36,60\) y \(108\) sería \((12,36,60,108)=12.\)

Veamos que, para calcular el máximo común divisor de 3 o mas enteros positivos podemos usar la recursión para encontrarlo.

Teorema 12

Sean \(a_1,a_2,...,a_n\) \(n\) enteros positivos en donde \(n\ge 3.\) Entonces

\[(a_1,a_2,...,a_n)=((a_1,a_2,...a_{n-1}),a_n).\]

Demostración. Sea \(d=(a_1,a_2,...,a_n) \text{, } d'=(a_1,a_2,...,a_{n-1})\) y \(d''=(d',a_n).\) Probaremos que \(d=d''.\)

  • Primero probaremos que \(d\mid d''.\)
    Ya que \(d=(a_1,a_2,...,a_n),\) entonces \(d \mid a_i\) para toda \(1 \le i \le n.\) Esto implica que \(d\mid d'\) y \(d\mid a_n,\) con lo cual tenemos que \(d\mid (d',a_n)\) y esto significa que \(d\mid d''.\)

  • Ahora veamos que \(d''\mid d.\)
    Ya que \(d''=(d',a_n),\) por definición \(d'' \mid d'\) y \(d''\mid a_n.\) Pero implicaría que \(d''\mid a_i\) para toda \(1\le i \le n-1.\) Así, \(d''\mid a_i\) para toda \(1\le i \le n,\) con lo cual tendríamos que \(d''\mid d.\)

Luego como \(d\mid d''\) y \(d''\mid d\) podemos concluir que \(d=d''. \square\)

Ejemplo 36

Usando el Teorema anterior, calcular \((18,30,60,75,132).\)

Solución.

\[\begin{align*} (18,30,60,75,132) &= ((18,30,60,75),132) \\ &= (((18,30,60),75),132) \\ &= ((((18,30),60),75),132) \\ &= (((6,60),75),132) \\ &= ((6,75),132) \\ &= (3,132) \\ &= 3. \end{align*}\]

Definición 16 (Primos relativos (varios enteros))

Los enteros positivos \(a_1,a_2,...,a_n\) son primos relativos por pares si todo par de estos enteros son primos relativos, esto es, \((a_i,a_j)=1\) siempre que \(i \neq j.\)

Ejemplo 37

Por ejemplo, los números \(8,15\) y \(49\) son primos relativos por pares, ya que \((8,15)=1,\) \((15,49)=1\) y \((8,49)=1.\)

Corolario 7

Si los enteros positivos \(a_1,a_2,...,a_n\) son primos relativos por pares, entonces \((a_1,a_2,...,a_n)=1\)

Explicación del código#

En esta sección aprendimos a seleccionar un elemento de las listas. Cuando creamos una lista los elementos dentro de esta tienen un índice, los índices de las listas comienzan con el valor cero. Por ejemplo si tuviéramos una lista con los números del 1 al 5.

lista = [1,2,3,4,5]

El primer elemento de la lista que es el número \(1\) tendría el índice \(0\), el segundo elemento de la lista que es número \(2\) tendría el índice \(1\) y así sucesivamente. Entonces si queremos seleccionar un valor de la lista simplemente tendríamos que saber su índice y ponerlo entre corchetes enfrente de la lista, es decir lista[índice]. Por ejemplo lo siguiente seleccionaría el número \(3\) de la lista.

lista[2]

Otra operación para las listas es la función max(), como argumento esta función recibe una lista. Lo que hace esta función es buscar dentro de la lista el valor entero más grande, sin importar si los números están ordenados de menor a mayor.

max(intA_B)

Una comprensión de listas es una forma concisa y legible de crear listas en Python. Permite construir una lista mediante la aplicación de una expresión a cada elemento de una secuencia (como otra lista o un rango) y opcionalmente aplicando condiciones para incluir solo ciertos elementos. La sintaxis básica es poner entre corchetes

lista = [expresión for elemento in iterable if condición]

Por ejemplo si tuviéramos que crear una lista con los cuadrados de un rango pero sin tomar el 5 tendríamos que:

lista = [x**2 for x in range(1,10) if x != 5]

La expresión x**2 significa elevar al cuadrado el número \(x.\) El elemento que tomamos está en el objeto iterable que es el rango de \(1\) a \(9.\) Por último nuestra condición es que \(x\) sea diferente de \(5,\) esto lo expresamos con la condición de diferente la cual es !=.

Veamos cómo funciona el código para calcular el máximo común divisor de dos números.

def mcd(a,b):
  lst_i = []
  z = 0
  for i in [a,b] :
    lst_f = []
    for div in range(1,i+1):
      if (i % div) == 0:
        lst_f.append(div)
    lst_i.append(lst_f)
    print("Los divisores de ",i," son ",lst_i[z])
    z += 1
  intA_B = [x for x in lst__i[0] if x in lst_i[1]]
  print("Los divisores comunes de " ,a," y ",b," son", intA_B)
  print("Por tanto el máximo común divisor de ",a," y ",b," es: ",max(intA_B))

  1. Creamos una función llamada «mcd», la cual recibe como argumentos dos enteros positivos.

def mcd(a,b):

  1. Creamos una lista vacía y una variable \(z\) con valor inicial de cero.

  lst_i = []
  z = 0

  1. Luego creamos un ciclo for. El ciclo empieza tomando \(i = a,\) el cual es el primer valor de la lista [a,b], la cual contiene los números que le proporcionamos. Iniciamos una lista vacía lst_f para guardar los divisores de cada número. Iniciamos dentro del mismo ciclo otro ciclo for que va a recorrer todos los números en el rango de \([ 1,i = a ].\) Ponemos un condicional if para revisar si el número div divide al valor \(i = a.\) Si el condicional if es verdadero, el número div es agregado a la lista vacía lst_f, si es falso pasa al siguiente valor del rango \([ 1,i = a ].\) Cuando termina de recorrer todos los valores obtenemos una lista con todos los divisores del número \(a,\) la cual se guarda en la lista lst_i. Luego nos muestra en la consola, la lista de divisores de dicho número \(a.\) Y suma una unidad al valor de \(z.\) Luego hace el mismo proceso para el siguiente número, es decir ahora tomaría \(i = b\) y repetiría el mismo proceso.

  for i in [a,b] :
    lst_f = []
    for div in range(1,i+1):
      if (i % div) == 0:
        lst_f.append(div)
    lst_i.append(lst_f)
    print("Los divisores de ",i," son ",lst_i[z])
    z += 1

  1. Con las listas obtenidas, hacemos una intersección entre la lista de divisores de \(a\) y la lista de divisores de \(b.\) el código funciona de la siguiente manera: para cada \(x\) en la lista de divisores de \(a,\) si \(x\) está en la lista de divisores de \(b\) entonces lo agrega a la lista creada intA_B.

intA_B = [x for x in lst__i[0] if x in lst_i[1]]

  1. Por último nos muestra en la consola los divisores en común entre los dos números \(a\) y \(b\) y con la función max() nos imprime el valor mas grande de la lista, el cual es el mcm.

  print("Los divisores comunes de " ,a," y ",b," son", intA_B)
  print("Por tanto el máximo común divisor de ",a," y ",b," es: ",max(intA_B))

Ejercicios de práctica#

  1. Sean \(a,b\) y \(c\) enteros positivos. Prueba que \(((a,b),c)=(a,(b,c))=(a,b,c).\)

  2. Demuestra que si \((a,b)=1\), entonces \((a+b,a-b)=1 \text{ o } 2.\)

  3. Demuestra que si \((a,b)=d\), entonces \((a+b,a-b)=d.\)

  4. Encuentra el máximo común divisor de \(a+b\) y \(a^2-b^2\), en donde \(a>b.\)

  5. Encuentra el máximo común divisor de los siguientes números:

    1. \((12,18,28,38,44)\)

    2. \((a^2b,ab^3,a^2b^2,a^3b^4,ab^4)\), para \(a\) y \(b\) números primos.

  6. Demuestra el Corolario 7 y muestra que el regreso no es cierto. Para ello, da tres enteros \(a,b,c\) tales que \((a,b)\), \((b,c)\), \((c,a)\) sean todos distintos de \(1\), pero \((a,b,c)=1\).