Máximo Común Divisor

¿Qué es $\text{GCD}(4,12)$?

Respuesta:

El GCD de $4$ y $12$ es $4$, ya que $4$ es el mayor número natural que divide a $4$ y $12$ a la vez.

¿Qué es $\text{GCD}(-36,16)$?

Responde:

Sabes que los divisores de $-36$ son $\pm 36,\pm 18,\pm 9,\pm 3,\pm 2,\pm 1$. Los divisores de $16$ son $16,8,4,2,1$. Recuerda que cuando eliges el MCD siempre tomas el mayor número natural que divide a ambos, por lo que el MCD siempre es un número positivo. Observando las listas de divisores, puedes ver entonces que \text{GCD}(-36, 16) = 2\).

Encuentra lo siguiente:

(a) $\text{GCD}(-4,0)$

(b) $\text{texto}GCD(10,24,35)$

(c) \(\texto{GCD} ( 24, 36) \)

Responde:

(a) Utilizando la propiedad de identidad y la propiedad conmutativa,

(b) Utilicemos la propiedad de asociación, que nos dice que

Empezando por la que parece más fácil, $\text{GCD}(24,35)=1$. Así que

(c) Éste es un buen lugar para utilizar la Propiedad Distributiva, ya que tanto $24$ como $36$ son divisibles por $2$. Es decir

\[ \año{comienzo{alineación} \text{GCD} (24, 36) &= \text{GCD} (2\cdot 12, 2\cdot 18) &= 2\cdot \text{GCD} (12, 18). \fin \]

Sabes que tanto $12$ como $18$ son divisibles por $2$, así que puedes volver a usar la Propiedad Distributiva para obtener

\[ \año{comienzo{alineación} \text{GCD} (24, 36) &= 2\cdot \text{GCD} (12, 18) &= 2\cdot \text{GCD} (2\cdot 6, 2\cdot 9)&= 2\cdot 2\cdot \text{GCD} (6, 9) &= 4\cdot \text{GCD} (6, 9) .\end{align} \]

Pero ahora $3$ divide tanto a $6$ como a $9$, así que puedes usar la Propiedad Distributiva una vez más para obtener

\[ \año{comienzo{alineación} \text{GCD} (24, 36) &= 4 \cdot \text{GCD} (6, 9) \cdot \text{GCD} (3\cdot 2, 3\cdot 3)&= 4\cdot 3 \cdot \text{GCD} (2, 3) \cdot \text{GCD} (2, 3) &= 12 \cdot \text{GCD} (2, 3) .\end{align} \]

Como $\text{GCD}(2,3)=1$ ahora puedes decir que

$$\text{GCD}(24,36)=12.$$

Supongamos que queremos hallar el DGC de $12,46$ y $78$.

Responde:

Por inspección, puedes enumerar todos los factores de los tres números:

• Los factores de $12$ son $1,2,3,4,6,12$.
• Los factores de $46$ son $1,2,23,46$.
• Los factores de $78$ son $1,2,3,6,13,26,39,78$.

Como el mayor número que aparece en las tres listas es $2$, escribirías $\text{GCD}(12,46,78)=2$.

Halla el máximo común divisor de $15$ y $36$.

Responde:

Puedes empezar escribiendo todos los divisores de $15$ y $36$:

• Los divisores de $15$ son $1,3,5,15.$
• Los divisores de $36$ son $1,2,3,4,6,9,12,18,36.$

Ahora puedes ver que hay dos divisores comunes a $15$ y $36$: $1$ y $3$.

Elige el que sea mayor, así que $3$ es el máximo común divisor de $15$ y $36$.

Tomando los enteros $44$ y $17$ y realizando la división larga se obtiene

$$\begin{array}{r}2\phantom{)} $ 17{overline{\smash{\big)}$,44\phantom{)}}$ \underline{-~\phantom(}0\phantom{-b)}$ 44\phantom{)}$ \underline{-~\phantom{()}34}$ 10\phantom{)}$end{array}$$.

Por tanto, 44 dividido por 17 da el cociente 2 con resto 10.

Así pues, si $a=44$ y $b=17$, al sustituir en la fórmula se obtiene

\[$$\begin{array}{rl}a& =qb+r\\ a44& =2\cdot 17+10.\end{array}$$\a].

Utiliza el Algoritmo Euclídeo para hallar el MCD de $44$ y $17$.

Contesta:

Paso 1: Como $44>17$, divide $44$ entre $17$ de modo que $44=17\cdot 2+10$ donde $10$ es el resto al dividir $44$ entre $17$. Entonces

\[\text{GCD} (44,17)=\text{GCD} (17,10) .\]

Paso 2: Ahora divide $17$ entre $10$, de modo que $17=1\cdot 10+7$. Así que

$$\text{GCD}(17,10)=\text{GCD}(10,7).$$

Paso 3: Ahora $10=1\cdot 7+3$, así que

\[\text{GCD} (10,7)=\text{GCD} (7,3) .\]

Paso 4: Aquí $7=2\cdot 3+1$, así que

$$\text{GCD}(7,3)=\text{GCD}(3,1).$$

Paso 5: En este paso, $3=1\cdot 3$ sin resto. Por tanto, $\text{GCD}(44,17)=1$.

Halla el DGC de $12$ y $30$ utilizando el Algoritmo Euclídeo.

Contesta:

Como $30>12$, $a=30$ y $b=12$ en el Algoritmo Euclídeo.

Paso 1: Ahora tienes que escribir $a$ en la forma $a=bq+r$, lo que te da $30=(12\cdot 2)+6$.

Sabes que $\text{GCD}(a,b)=\text{GCD}(b,r)$, por lo que

$$\text{GCD}(30,12)=\text{GCD}(12,6).$$

Paso 2: Ahora, deja que $b=12$ y $r_1=6$ y vuelve a realizar el mismo proceso. Es decir, $12=(6\cdot 2)+0$.

Ahora $r_1=6$ y $r_2=0$, entonces

$$\text{GCD}(r_1,r_2)=\text{GCD}(6,0)=6.$$

Paso 4: Espera, el algoritmo termina en cuanto obtienes un resto de $0$, ¡que ya tienes! Eso significa que puedes saltarte el Paso 4.

Paso 5: Ahora ya sabes que

\[ \inicio{alineación} \text{GCD} (6,0) &=\text{GCD} (12,6) \text{GCD} (30,12) \\=6 . \fin].

Por tanto, el MCD de $30$ y $12$ es $6$.

Halla el máximo común divisor de $32$, $254$ y $372$.

Respuesta:

Primero utilizarías el Algoritmo Euclídeo para hallar $\text{GCD}(32,254)=2$. Luego puedes volver a utilizar el Algoritmo Euclídeo para ver que $\text{GCD}(2,372)=2$.

Entonces, por la Propiedad Asociativa

\[ \año{comienzo{alineación} \text{GCD} (32, 254, 372) &=\text{GCD} (\text{GCD} (32,254), 372) \ &=texto{GCD} (2,372)&=2 . \fin].