¿Cómo se conectan los nodos y los noks? Encontrar el GCD usando el algoritmo de Euclides y usando factorización prima

Para aprender a encontrar el máximo común divisor de dos o más números, debe comprender qué son los números naturales, primos y complejos.

Un número natural es cualquier número que se utiliza para contar números enteros.

Si un número natural solo se puede dividir entre sí mismo y uno, entonces se llama primo.

Todos los números naturales se pueden dividir por sí mismos y por uno, pero el único número primo par es el 2, todos los demás números primos se pueden dividir por dos. Por lo tanto, solo los números impares pueden ser primos.

demasiados numeros primos lista completa ellos no existen Para encontrar el GCD, es conveniente usar tablas especiales con dichos números.

Mayoria números naturales se pueden dividir no solo por uno, ellos mismos, sino también por otros números. Entonces, por ejemplo, el número 15 se puede dividir por 3 y 5. Todos ellos se llaman divisores del número 15.

Por lo tanto, el divisor de cualquier A es el número por el cual se puede dividir sin resto. Si un número tiene más de dos divisores naturales, se llama compuesto.

El número 30 tiene divisores como 1, 3, 5, 6, 15, 30.

Puedes ver que 15 y 30 tienen los mismos divisores 1, 3, 5, 15. El máximo común divisor de estos dos números es 15.

Por lo tanto, el divisor común de los números A y B es el número por el cual puedes dividirlos completamente. El máximo puede considerarse el máximo. numero total en que se pueden dividir.

Para resolver problemas, se utiliza la siguiente inscripción abreviada:

MCD (A; B).

Por ejemplo, MCD (15; 30) = 30.

Para escribir todos los divisores de un número natural, se utiliza la notación:

D(15) = (1, 3, 5, 15)

mcd (9; 15) = 1

EN este ejemplo Los números naturales solo tienen un divisor común. Se llaman coprimos, respectivamente, la unidad es su máximo común divisor.

Cómo encontrar el máximo común divisor de números

Para encontrar el MCD de varios números, necesitas:

Encuentra todos los divisores de cada número natural por separado, es decir, descompóngalos en factores (números primos);

Seleccione todos los mismos factores para los números dados;

Multiplícalos juntos.

Por ejemplo, para calcular el máximo común divisor de 30 y 56, escribirías lo siguiente:

Para no confundirse con , conviene escribir los multiplicadores en columnas verticales. En el lado izquierdo de la línea, debe colocar el dividendo y, a la derecha, el divisor. Debajo del dividendo, debe indicar el cociente resultante.

Entonces, en la columna de la derecha estarán todos los factores necesarios para la solución.

Los divisores idénticos (factores encontrados) se pueden subrayar por conveniencia. Se deben reescribir y multiplicar y se debe anotar el máximo común divisor.

MCD (30; 56) = 2 * 5 = 10

Así de sencillo es encontrar el máximo común divisor de números. Con un poco de práctica, puedes hacerlo casi automáticamente.

muchos divisores

Considere el siguiente problema: encuentre el divisor del número 140. Es obvio que el número 140 no tiene un divisor, sino varios. En tales casos, se dice que la tarea tiene un montón de soluciones Encontrémoslos a todos. En primer lugar, descompongamos este número en factores primos:

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Ahora podemos escribir fácilmente todos los divisores. Comencemos con divisores simples, es decir, los que están presentes en la expansión anterior:

Luego escribimos los que se obtienen por multiplicación por pares de divisores primos:

2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.

Entonces - los que contienen tres divisores simples:

2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.

Finalmente, no olvidemos la unidad y el propio número descomponible:

Todos los divisores encontrados por nosotros forman un montón de divisores del número 140, que se escribe con llaves:

El conjunto de divisores del número 140 =

{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

Para facilitar la percepción, hemos escrito los divisores aquí ( establecer elementos) en orden ascendente, pero en general, esto no es necesario. Además, introducimos una abreviatura. En lugar de "El conjunto de divisores del número 140" escribiremos "D (140)". Por lo tanto,

De manera similar, uno puede encontrar el conjunto de divisores para cualquier otro número natural. Por ejemplo, a partir de la expansión

105 = 3 ∙ 5 ∙ 7

obtenemos:

D(105) = (1, 3, 5, 7, 15, 21, 35, 105).

Del conjunto de todos los divisores, se debe distinguir el conjunto de los divisores primos, que para los números 140 y 105 son iguales, respectivamente:

PD(140) = (2, 5, 7).

PD(105) = (3, 5, 7).

Cabe destacar que en la descomposición del número 140 en factores primos el dos está presente dos veces, mientras que en el conjunto PD(140) es sólo uno. El conjunto de PD(140) es, en esencia, todas las respuestas al problema: "Encontrar un factor primo del número 140". Está claro que la misma respuesta no debe repetirse más de una vez.

Reducción de fracciones. Máximo común divisor

Considere una fracción

Sabemos que esta fracción se puede reducir por un número que es a la vez divisor del numerador (105) y divisor del denominador (140). Veamos los conjuntos D(105) y D(140) y anotemos sus elementos comunes.

D(105) = (1, 3, 5, 7, 15, 21, 35, 105);

D(140) = (1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140).

Elementos comunes de los conjuntos D(105) y D(140) =

La última igualdad se puede escribir más corta, a saber:

D(105) ∩ D(140) = (1, 5, 7, 35).

Aquí, el signo especial "∩" ("bolsa con el agujero hacia abajo") solo indica que de los dos conjuntos escritos según lados diferentes de él, debe seleccionar solo elementos comunes. La entrada "D (105) ∩ D (140)" dice " intersección conjuntos de Te de 105 y Te de 140.

[Tenga en cuenta que puede realizar varias operaciones binarias con conjuntos, casi como con números. Otra operación binaria común es Unión, que se indica con el icono "∪" ("bolso con el agujero hacia arriba"). La unión de dos conjuntos incluye todos los elementos de ambos conjuntos:

PD(105) = (3, 5, 7);

PD(140) = (2, 5, 7);

PD(105) ∪ PD(140) = (2, 3, 5, 7). ]

Entonces, descubrimos que la fracción

se puede reducir a cualquiera de los números pertenecientes al conjunto

D(105) ∩ D(140) = (1, 5, 7, 35)

y no puede ser reducido por ningún otro número natural. Eso es todo formas posibles reducciones (excepto la reducción poco interesante por uno):

Es obvio que lo más práctico es reducir la fracción a un número, si es posible, mayor. En este caso, es el número 35, que se dice que es máximo común divisor (MCD) números 105 y 140. Esto se escribe como

mcd(105, 140) = 35.

Sin embargo, en la práctica, si nos dan dos números y necesitamos encontrar su máximo común divisor, no tenemos que construir ningún conjunto. Basta simplemente factorizar ambos números en factores primos y subrayar aquellos de estos factores que son comunes a ambas factorizaciones, por ejemplo:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Multiplicando los números subrayados (en cualquiera de las expansiones), obtenemos:

mcd(105, 140) = 5 ∙ 7 = 35.

Por supuesto, es posible que haya más de dos factores subrayados:

168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;

396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.

A partir de aquí es claro que

mcd(168, 396) = 2 ∙ 2 ∙ 3 = 12.

Mención especial merece la situación en la que no hay factores comunes en absoluto y no hay nada que destacar, por ejemplo:

42 = 2 ∙ 3 ∙ 7;

En este caso,

mcd(42, 55) = 1.

Dos números naturales para los que el mcd es igual a uno se llaman coprime. Si haces una fracción de tales números, por ejemplo,

entonces tal fracción es irreducible.

En términos generales, la regla para reducir fracciones se puede escribir de la siguiente manera:

Aquí se supone que un y b son números naturales y todas las fracciones son positivas. Si ahora asignamos un signo menos a ambos lados de esta igualdad, obtenemos la regla correspondiente para fracciones negativas.

Suma y resta de fracciones. Minimo común multiplo

Supongamos que desea calcular la suma de dos fracciones:

Ya sabemos cómo se descomponen los denominadores en factores primos:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Inmediatamente se sigue de esta descomposición que, para llevar las fracciones a un denominador común, basta con multiplicar el numerador y el denominador de la primera fracción por 2 ∙ 2 (el producto de los factores primos no acentuados del segundo denominador), y el numerador y el denominador de la segunda fracción por 3 (“producto” de factores primos sin subrayar del primer denominador). Como resultado, los denominadores de ambas fracciones serán iguales a un número que se puede representar de la siguiente manera:

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.

Es fácil ver que ambos denominadores iniciales (tanto 105 como 140) son divisores del número 420, y el número 420, a su vez, es un múltiplo de ambos denominadores, y no solo un múltiplo, es minimo común multiplo (CON) números 105 y 140. Esto se escribe así:

MCM(105, 140) = 420.

Mirando más de cerca la expansión de los números 105 y 140, vemos que

105 ∙ 140 = MCM(105, 140) ∙ MCD(105, 140).

De manera similar, para números naturales arbitrarios b y d:

b ∙ d= MCM( b, d) ∙ MCD( b, d).

Ahora completemos la suma de nuestras fracciones:

Pero muchos números naturales son divisibles por otros números naturales.

por ejemplo:

El número 12 es divisible por 1, por 2, por 3, por 4, por 6, por 12;

El número 36 es divisible por 1, por 2, por 3, por 4, por 6, por 12, por 18, por 36.

Los números por los cuales el número es divisible (para 12 es 1, 2, 3, 4, 6 y 12) se llaman divisores de números. divisor de un numero natural un es el número natural que divide al número dado un sin rastro. Un número natural que tiene más de dos divisores se llama compuesto. Tenga en cuenta que los números 12 y 36 tienen divisores comunes. Estos son los números: 1, 2, 3, 4, 6, 12. El mayor divisor de estos números es 12.

Divisor común de dos números dados un y b es el número por el cual los dos números dados son divisibles sin resto un y b. Divisor común de números múltiples (MCD) es el número que sirve de divisor para cada uno de ellos.

Brevemente el máximo común divisor de números un y b se escriben asi:

Ejemplo: mcd (12; 36) = 12.

Los divisores de números en la notación de la solución denotan letra mayúscula"D".

Ejemplo:

mcd (7; 9) = 1

Los números 7 y 9 tienen un solo divisor común: el número 1. Tales números se llaman coprimechi golpe.

Números coprimos son números naturales que solo tienen un divisor común: el número 1. Su mcd es 1.

Máximo Común Divisor (MCD), propiedades.

• Propiedad principal: máximo común divisor metro y norte es divisible por cualquier divisor común de estos números. Ejemplo: para los números 12 y 18 el máximo común divisor es 6; es divisible por todos los divisores comunes de estos números: 1, 2, 3, 6.
• Corolario 1: conjunto de divisores comunes metro y norte coincide con el conjunto de divisores mcd( metro, norte).
• Corolario 2: conjunto de múltiplos comunes metro y norte coincide con el conjunto de múltiples LCM ( metro, norte).

Esto significa, en particular, que para reducir una fracción a una forma irreducible, es necesario dividir su numerador y denominador por su mcd.

• Máximo común divisor de números metro y norte se puede definir como el elemento positivo más pequeño del conjunto de todas sus combinaciones lineales:

y por lo tanto representar como una combinación lineal de números metro y norte:

Esta relación se llama relación de Bezout, y los coeficientes tu y v — coeficientes de bezout. Los coeficientes de Bézout se calculan de manera eficiente mediante el algoritmo de Euclides ampliado. Esta declaración se generaliza a conjuntos de números naturales; su significado es que el subgrupo del grupo generado por el conjunto es cíclico y está generado por un elemento: mcd ( un 1 , un 2 , … , un).

Cálculo del máximo común divisor (mcd).

Formas eficientes de calcular el mcd de dos números son Algoritmo de Euclides y binarioalgoritmo. Además, el valor de GCD ( metro,norte) se puede calcular fácilmente si se conoce la expansión canónica de los números metro y norte para factores primos:

donde son primos distintos y y son enteros no negativos (pueden ser cero si el primo correspondiente no está en la descomposición). Entonces mcd ( metro,norte) y MCM ( metro,norte) se expresan mediante las fórmulas:

Si hay más de dos números: , su MCD se encuentra de acuerdo con el siguiente algoritmo:

- este es el GCD deseado.

Asimismo, para encontrar máximo común divisor, puedes descomponer cada uno de los números dados en factores primos. Luego escribe por separado solo aquellos factores que están incluidos en todos los números dados. Luego multiplicamos los números escritos entre ellos: el resultado de la multiplicación es el máximo común divisor .

Analicemos paso a paso el cálculo del máximo común divisor:

1. Descomponer los divisores de números en factores primos:

Los cálculos se escriben convenientemente usando una barra vertical. A la izquierda de la línea, primero escriba el dividendo, a la derecha, el divisor. Más adelante en la columna de la izquierda anotamos los valores de privado. Vamos a explicar de inmediato con un ejemplo. Factoricemos los números 28 y 64 en factores primos.

2. Subrayamos los mismos factores primos en ambos números:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Hallamos el producto de factores primos idénticos y anotamos la respuesta:

MCD (28; 64) = 2. 2 = 4

Respuesta: MCD (28; 64) = 4

Puede organizar la ubicación del GCD de dos maneras: en una columna (como se hizo anteriormente) o "en una línea".

La primera forma de escribir GCD:

Encuentra GCD 48 y 36.

MCD (48; 36) = 2 . 2. 3 = 12

La segunda forma de escribir GCD:

Ahora escribamos la solución de búsqueda GCD en una línea. Encuentra GCD 10 y 15.

D(10) = (1, 2, 5, 10)

D(15) = (1, 3, 5, 15)

D(10, 15) = (1, 5)

Este artículo está dedicado a una pregunta como encontrar el máximo común divisor. Primero, explicaremos qué es y daremos algunos ejemplos, introduciremos las definiciones del máximo común divisor de 2, 3 o más números, después de lo cual nos detendremos en las propiedades generales. este concepto y demostrarlos.

Yandex.RTB R-A-339285-1

¿Qué son los divisores comunes?

Para entender qué es el máximo común divisor, primero formulamos qué es un divisor común para números enteros.

En el artículo sobre múltiplos y divisores, dijimos que un número entero siempre tiene múltiples divisores. Aquí estamos interesados ​​en los divisores de un cierto número de enteros a la vez, especialmente comunes (idénticos) para todos. Escribamos la definición principal.

Definición 1

El divisor común de varios enteros será un número que puede ser divisor de cada número del conjunto especificado.

Ejemplo 1

Aquí hay ejemplos de dicho divisor: el triple será un divisor común para los números - 12 y 9, ya que las igualdades 9 = 3 · 3 y − 12 = 3 · (− 4) son verdaderas. Los números 3 y -12 tienen otros divisores comunes, como 1, -1 y -3. Tomemos otro ejemplo. Los cuatro enteros 3 , − 11 , − 8 y 19 tendrán dos divisores comunes: 1 y -1 .

Conociendo las propiedades de la divisibilidad, podemos decir que cualquier número entero se puede dividir por uno y menos uno, lo que significa que cualquier conjunto de números enteros ya tendrá al menos dos divisores comunes.

También tenga en cuenta que si tenemos un divisor común b para varios números, entonces los mismos números se pueden dividir por numero opuesto, es decir, en -b . En principio, solo podemos tomar divisores positivos, entonces todos los divisores comunes también serán mayores que 0. Este enfoque también se puede utilizar, pero se puede ignorar por completo. números negativos no lo hagas.

¿Cuál es el máximo común divisor (mcd)

De acuerdo con las propiedades de la divisibilidad, si b es divisor de un entero a que no es igual a 0, entonces el módulo de b no puede ser mayor que el módulo de a, por lo que todo número distinto de 0 tiene un número finito de divisores. . Esto significa que el número de divisores comunes de varios números enteros, al menos uno de los cuales difiere de cero, también será finito, y de todo su conjunto siempre podemos seleccionar el más Número grande(Anteriormente ya hemos hablado sobre el concepto del entero más grande y más pequeño, le recomendamos que repita este material).

En un razonamiento posterior, supondremos que al menos uno del conjunto de números para los que necesita encontrar el máximo común divisor será diferente de 0. Si todos son 0, entonces cualquier número entero puede ser su divisor, y dado que hay infinitos de ellos, no podemos elegir el mayor. En otras palabras, es imposible encontrar el máximo común divisor para el conjunto de números igual a 0.

Pasamos a la formulación de la definición principal.

Definición 2

El máximo común divisor de varios números es el entero más grande que divide a todos esos números.

Por escrito, el máximo común divisor se suele denotar con la abreviatura GCD. Para dos números, se puede escribir como mcd (a, b) .

Ejemplo 2

¿Cuál es un ejemplo de GCD para dos enteros? Por ejemplo, para 6 y -15 sería 3. Justifiquemos esto. Primero, escribimos todos los divisores de seis: ± 6, ± 3, ± 1, y luego todos los divisores de quince: ± 15, ± 5, ± 3 y ± 1. Después de eso, elegimos los comunes: estos son − 3 , − 1 , 1 y 3 . De estos, debe elegir el número más grande. Esto será 3.

Para tres o más números, la definición del máximo común divisor será prácticamente la misma.

Definición 3

El máximo común divisor de tres o más números es el entero más grande que divide todos esos números al mismo tiempo.

Para los números a 1 , a 2 , … , an el divisor se denota convenientemente como MCD (a 1 , a 2 , … , a n) . El valor del divisor en sí se escribe como GCD (a 1 , a 2 , … , a n) = b .

Ejemplo 3

Estos son ejemplos del máximo común divisor de varios números enteros: 12 , - 8 , 52 , 16 . Será igual a cuatro, lo que significa que podemos escribir que mcd (12, - 8, 52, 16) = 4.

Puedes verificar la exactitud de esta declaración escribiendo todos los divisores de estos números y luego eligiendo el mayor de ellos.

En la práctica, a menudo hay casos en los que el máximo común divisor es igual a uno de los números. Esto sucede cuando todos los demás números se pueden dividir por un número dado (en el primer párrafo del artículo dimos la prueba de esta afirmación).

Ejemplo 4

Entonces, el máximo común divisor de los números 60, 15 y - 45 es 15, ya que quince es divisible no solo por 60 y - 45, sino también por sí mismo, y no hay mayor divisor para todos estos números.

Los números coprimos son un caso especial. Son números enteros con un máximo común divisor de 1.

Principales propiedades de GCD y el algoritmo de Euclides

El máximo común divisor tiene algunas propiedades características. Los formulamos en forma de teoremas y demostramos cada uno de ellos.

Tenga en cuenta que estas propiedades están formuladas para números enteros mayores que cero, y solo consideramos divisores positivos.

Definición 4

Los números a y b tienen el máximo común divisor igual a mcd para b y a , es decir, mcd (a , b) = mcd (b , a) . Cambiar los lugares de los números no afecta el resultado final.

Esta propiedad se deriva de la definición misma de GCD y no necesita demostración.

Definición 5

Si el número a se puede dividir por el número b, entonces el conjunto de divisores comunes de estos dos números será similar al conjunto de divisores del número b, es decir, mcd (a, b) = b.

Probemos esta afirmación.

Prueba 1

Si los números a y b tienen divisores comunes, cualquiera de ellos se puede dividir entre ellos. Al mismo tiempo, si a es un múltiplo de b, entonces cualquier divisor de b también será divisor de a, ya que la divisibilidad tiene una propiedad como la transitividad. Por lo tanto, cualquier divisor b será común para los números a y b. Esto prueba que si podemos dividir a por b, entonces el conjunto de todos los divisores de ambos números coincide con el conjunto de divisores de un número b. Y dado que el máximo divisor de cualquier número es el propio número, entonces el máximo común divisor de los números a y b también será igual a b, es decir, mcd(a, b) = b. Si a = b , entonces mcd (a , b) = mcd (a , a) = mcd (b , b) = a = b , por ejemplo, mcd (132 , 132) = 132 .

Usando esta propiedad, podemos encontrar el máximo común divisor de dos números si uno de ellos se puede dividir por el otro. Tal divisor es igual a uno de estos dos números por los cuales se puede dividir el segundo número. Por ejemplo, mcd (8, 24) = 8, porque 24 es múltiplo de ocho.

Definición 6 Prueba 2

Intentemos demostrar esta propiedad. Tenemos inicialmente la igualdad a = b q + c , y cualquier divisor común de a y b también dividirá a c , lo que se explica por la propiedad de divisibilidad correspondiente. Por lo tanto, cualquier divisor común de b y c dividirá a . Esto significa que el conjunto de divisores comunes a y b coincidirá con el conjunto de divisores b y c, incluido el mayor de ellos, por lo que se cumple la igualdad mcd (a, b) = mcd (b, c).

Definición 7

La siguiente propiedad se llama algoritmo de Euclides. Con él, puedes calcular el máximo común divisor de dos números, así como probar otras propiedades de MCD.

Antes de formular la propiedad, te aconsejamos que repitas el teorema que demostramos en el artículo sobre la división con resto. Según él, el número divisible a se puede representar como b q + r, y aquí b es un divisor, q es un número entero (también se le llama cociente incompleto), y r es un resto que satisface la condición 0 ≤ r ≤ b.

Digamos que tenemos dos números enteros mayores que 0 para los cuales se cumplirán las siguientes igualdades:

un = segundo q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Estas igualdades terminan cuando r k + 1 se vuelve igual a 0 . Esto definitivamente sucederá, ya que la secuencia b > r 1 > r 2 > r 3 , … es una serie de números enteros decrecientes, que puede incluir solo un número finito de ellos. Por lo tanto, r k es el máximo común divisor de a y b , es decir, r k = mcd (a , b) .

En primer lugar, debemos demostrar que r k es un divisor común de los números a y b, y después de eso, que r k no es solo un divisor, sino el máximo común divisor de los dos números dados.

Veamos la lista de igualdades de arriba, de abajo hacia arriba. Según la última igualdad,
r k − 1 se puede dividir por r k . Con base en este hecho, así como en la anterior propiedad demostrada del máximo común divisor, se puede argumentar que r k − 2 se puede dividir por r k , ya que
r k − 1 es divisible por r k y r k es divisible por r k .

La tercera igualdad desde abajo nos permite concluir que r k − 3 se puede dividir entre r k , y así sucesivamente. La segunda desde abajo es que b es divisible por r k , y la primera es que a es divisible por r k . De todo esto concluimos que r k es un divisor común de a y b .

Ahora demostremos que r k = mcd (a , b) . ¿Que necesito hacer? Muestre que cualquier divisor común de a y b dividirá a r k . Lo denotaremos r 0 .

Veamos la misma lista de igualdades, pero de arriba a abajo. En base a la propiedad anterior, podemos concluir que r 1 es divisible por r 0 , lo que significa que según la segunda igualdad, r 2 es divisible por r 0 . Bajamos por todas las igualdades y de la última concluimos que r k es divisible por r 0 . Por lo tanto, r k = mcd (a , b) .

Habiendo considerado esta propiedad, concluimos que el conjunto de divisores comunes de a y b es similar al conjunto de divisores del mcd de estos números. Esta afirmación, que es un corolario del algoritmo de Euclides, nos permitirá calcular todos los divisores comunes de dos números dados.

Pasemos a otras propiedades.

Definición 8

Si a y b son números enteros distintos de 0, entonces debe haber otros dos números enteros u 0 y v 0 para los cuales la igualdad mcd (a , b) = a · u 0 + b · v 0 será válida.

La igualdad dada en el enunciado de la propiedad es una representación lineal del máximo común divisor de a y b . Se llama razón de Bezout, y los números u 0 y v 0 se llaman coeficientes de Bezout.

Prueba 3

Probemos esta propiedad. Anotamos la sucesión de igualdades según el algoritmo de Euclides:

un = segundo q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

La primera igualdad nos dice que r 1 = a − b · q 1 . Denote 1 = s 1 y − q 1 = t 1 y reescriba esta igualdad como r 1 = s 1 · a + t 1 · b . Aquí los números s 1 y t 1 serán números enteros. La segunda igualdad nos permite concluir que r 2 = b − r 1 q 2 = b − (s 1 a + t 1 b) q 2 = − s 1 q 2 a + (1 − t 1 q 2) b . Denote − s 1 q 2 = s 2 y 1 − t 1 q 2 = t 2 y reescriba la igualdad como r 2 = s 2 a + t 2 b , donde s 2 y t 2 también serán números enteros. Esto se debe a que la suma de los números enteros, su producto y la diferencia también son números enteros. Exactamente de la misma manera, obtenemos de la tercera igualdad r 3 = s 3 · a + t 3 · b , de la siguiente r 4 = s 4 · a + t 4 · b, etc. Finalmente, concluimos que r k = s k a + t k b para los enteros s k y t k . Como r k \u003d GCD (a, b) , denotamos s k \u003d u 0 y t k \u003d v 0. Como resultado, podemos obtener una representación lineal de GCD en la forma requerida: GCD (a, b) \u003d a tu 0 + b v 0.

Definición 9

mcd (m a, m b) = m mcd (a, b) para cualquier valor natural m.

Prueba 4

Esta propiedad se puede justificar de la siguiente manera. Multiplique por el número m ambos lados de cada igualdad en el algoritmo de Euclides y obtenemos que mcd (m a , m b) = m r k , y r k es mcd (a , b) . Por lo tanto, mcd (m a, m b) = m gcd (a, b) . Es esta propiedad del máximo común divisor la que se usa al encontrar el MCD por el método de factorización.

Definición 10

Si los números a y b tienen un divisor común p , entonces mcd (a: p , b: p) = mcd (a , b) : p . En el caso cuando p = mcd (a , b) obtenemos mcd (a: mcd (a , b) , b: mcd (a , b) = 1, por lo tanto, los números a: mcd (a , b) y b : mcd (a , b) son coprimos.

Como a = p (a: p) y b = p (b: p) , entonces, en base a la propiedad anterior, podemos crear igualdades de la forma mcd (a , b) = mcd (p (a: p) , p (b: p)) = p MCD (a: p, b: p) , entre los cuales habrá una prueba propiedad dada. Usamos esta afirmación cuando damos fracciones comunes a la forma irreductible.

Definición 11

El máximo común divisor a 1 , a 2 , … , a k será el número d k , que se puede encontrar calculando sucesivamente mcd (a 1 , a 2) = d 2 , mcd (d 2 , a 3) = d 3 , mcd (re 3 , un 4) = re 4 , ... , MCD (re k - 1 , un k) = re k .

Esta propiedad es útil para encontrar el máximo común divisor de tres o más números. Con él, puedes reducir esta acción a operaciones con dos números. Su base es un corolario del algoritmo de Euclides: si el conjunto de divisores comunes a 1 , a 2 y a 3 coincide con el conjunto d 2 y a 3 , entonces también coincide con los divisores d 3 . Los divisores de los números a 1 , a 2 , a 3 y a 4 coincidirán con los divisores de d 3 , lo que significa que también coincidirán con los divisores de d 4 , y así sucesivamente. Al final, obtenemos que los divisores comunes de los números a 1 , a 2 , … , a k coincidirán con los divisores de d k , y como mayor divisor el número d k será este mismo número, entonces mcd (a 1 , a 2 , … , a k) = d k .

Eso es todo lo que nos gustaría hablar sobre las propiedades del máximo común divisor.

Si nota un error en el texto, resáltelo y presione Ctrl+Enter

Este artículo es sobre encontrar el máximo común divisor (mcd) dos y más números. Primero, considera el algoritmo de Euclides, te permite encontrar el MCD de dos números. Después de eso, nos detendremos en un método que nos permita calcular el MCD de números como un producto de sus factores primos comunes. A continuación, nos ocuparemos de encontrar el máximo común divisor de tres o más números, y también daremos ejemplos de cómo calcular el MCD de números negativos.

Navegación de página.

Algoritmo de Euclides para encontrar GCD

Tenga en cuenta que si hubiéramos consultado la tabla de números primos desde el principio, habríamos descubierto que los números 661 y 113 son primos, por lo que podríamos decir inmediatamente que su máximo común divisor es 1.

Responder:

mcd(661, 113)=1 .

Hallar MCD factorizando números en factores primos

Considere otra forma de encontrar el GCD. El máximo común divisor se puede encontrar al factorizar números en factores primos. Formulemos la regla: MCD de dos enteros números positivos a y b es igual al producto de todos los factores primos comunes en las expansiones de los números a y b en factores primos.

Demos un ejemplo para explicar la regla para encontrar el MCD. Conozcamos las expansiones de los números 220 y 600 en factores primos, tienen la forma 220=2 2 5 11 y 600=2 2 2 3 5 5 . Los factores primos comunes involucrados en la expansión de los números 220 y 600 son 2 , 2 y 5 . Por lo tanto mcd(220, 600)=2 2 5=20 .

Así, si descomponemos los números a y b en factores primos y hallamos el producto de todos sus factores comunes, entonces este hallará el máximo común divisor de los números a y b.

Considere un ejemplo de encontrar el GCD de acuerdo con la regla anunciada.

Ejemplo.

Encuentra el máximo común divisor de 72 y 96.

Decisión.

Factoricemos los números 72 y 96:

Es decir, 72=2 2 2 3 3 y 96=2 2 2 2 2 3 . Los factores primos comunes son 2 , 2 , 2 y 3 . Entonces mcd(72, 96)=2 2 2 3=24 .

Responder:

mcd(72, 96)=24 .

Como conclusión de esta sección, observamos que la validez de la regla anterior para encontrar el mcd se deriva de la propiedad del máximo común divisor, que establece que MCD(m a 1 , m b 1)=m MCD(a 1 , b 1), donde m es cualquier entero positivo.

Hallar el MCD de tres o más números

Encontrar el máximo común divisor de tres o más números se puede reducir a encontrar sucesivamente el mcd de dos números. Mencionamos esto cuando estudiamos las propiedades de GCD. Allí formulamos y probamos el teorema: el máximo común divisor de varios números a 1 , a 2 , …, a k es igual al número d k , que se encuentra en el cálculo secuencial 1 , a k)=d k .

Veamos cómo se ve el proceso de encontrar el MCD de varios números considerando la solución del ejemplo.

Ejemplo.

Encuentra el máximo común divisor de los cuatro números 78 , 294 , 570 y 36 .

Decisión.

En este ejemplo, un 1 = 78, un 2 = 294, un 3 = 570, un 4 = 36.

Primero, utilizando el algoritmo de Euclides, determinamos el máximo común divisor d 2 de los dos primeros números 78 y 294 . Al dividir, obtenemos las igualdades 294=78 3+60 ; 78=60 1+18 ; 60=18 3+6 y 18=6 3 . Por lo tanto, d 2 = MCD (78, 294) = 6 .

Ahora vamos a calcular d 3 \u003d MCD (d 2, a 3) \u003d MCD (6, 570). De nuevo aplicamos el algoritmo de Euclides: 570=6·95 , por lo tanto, d 3 =MCD(6, 570)=6 .

Queda por calcular d 4 \u003d MCD (d 3, a 4) \u003d MCD (6, 36). Como 36 es divisible por 6, entonces d 4 \u003d MCD (6, 36) \u003d 6.

Por lo tanto, el máximo común divisor de los cuatro números dados es d 4 =6, es decir, mcd(78, 294, 570, 36)=6.

Responder:

mcd(78, 294, 570, 36)=6 .

Descomponer números en factores primos también te permite calcular el MCD de tres o más números. En este caso, el máximo común divisor se encuentra como el producto de todos los factores primos comunes de los números dados.

Ejemplo.

Calcula el MCD de los números del ejemplo anterior usando sus factores primos.

Decisión.

Descomponemos los números 78 , 294 , 570 y 36 en factores primos, obtenemos 78=2 3 13 , 294=2 3 7 7 , 570=2 3 5 19 , 36=2 2 3 . 3 . Los factores primos comunes de los cuatro números dados son los números 2 y 3. Por lo tanto, MCD(78, 294, 570, 36)=2 3=6.