Máximo común divisor: Diferenzas entre revisións

Contido eliminado Contido engadido
Jglamela (conversa | contribucións)
Creada como tradución da páxina "Máximo común divisor"
(Sen diferenzas.)

Revisión como estaba o 26 de maio de 2017 ás 19:39

En matemáticas, o máximo común divisor (MCD) de dous ou máis números enteiros é o maior número enteiro que os divide sen deixar resto.

Definicións

Se a e b son números enteiros distintos de cero e se o número c é tal que c|a e á súa vez c|b, este número c denomínase divisor común dos números a e b.[1] Cómpre observar que dous números enteiros calquera teñen divisores comúns; cando os únicos divisores comúns dos números a e b son 1 e -1, eses números chámanse primos entre si.

Un número enteiro d chámase máximo común divisor (MCD) dos números a e b cando:

  1. d é divisor común dos números a e b e
  2. d é divisible por calquera outro divisor común dos números a e b.

Exemplo:

12 é o mcd de 36 e 60. Pois 12|36 e 12|60; á súa vez 12 é divisible por 1, -1, 2, -2, 3, -3, 4, -4, 6, -6, 12 e -12 que son divisores comúns de 36 e 60.[2]

Cálculo do máximo divisor común

O tres métodos máis utilizados para o cálculo do máximo divisor común de dous números son:

Por descomposición en factores primos

O máximo común divisor de dous números pode calcularse determinando a descomposición en factores primos dos dous números e tomando os factores comúns elevados á menor potencia, o produto dos cales será o MCD.

Exemplo: para calcular o máximo común divisor de 48 e de 60 obtense da súa factorización en factores primos.

 



O MCD son os factores comúns co seu menor expoñente, isto é:

Na práctica, este método só é operativo para números pequenos levando en xeral demasiado tempo calcular a descomposición en factores primos de dous números calquera.

Algoritmo de Euclides

Un método máis eficiente é o algoritmo de Euclides, que emprega o algoritmo da división xunto co feito de que o MCD de dous números tamén divide o resto obtido de dividir o maior entre o máis pequeno.

Exemplo 1:

Se se divide 60 entre 48 dando un cociente de 1 e un resto de 12, o MCD será polo tanto divisor de 12. Despois divídese 48 entre 12 dando un resto de 0, o que significa que 12 é o MCD. Formalmente pode describirse como:

Exemplo 2:

O MCD de 42 e 56 é 14. En efecto:

operando:

Co mínimo múltiplo común

O máximo divisor común tamén pode ser calculado empregando o mínimo común múltiplo. Se a e b son distintos de cero, entón o máximo divisor común de a e b obtense mediante a seguinte fórmula, que involucra o mínimo múltiplo común de a e b:

MCD de tres ou máis números

O máximo común divisor de tres ou máis números pódese definir recursivamente empregando o método:

        

mcd ⁡ ( a , b , c ) = ( a ,

( , c ) ) {\displaystyle \ \operatorname {mcd} (a,b,c)=\operatorname {mcd} (a,\operatorname {} (b,c))} .[3][4]

Propiedades

1. Se

        

mcd ⁡ ( a , b ) =

{\isplystyle \ \operatorname {} (a,)=d} entón

        

mcd

( a d , b d ) =

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

2. Si

        

m {} é un enteiro,

        

cd ⁡ ( ,

b ) = | m

( a ,

) {\displaystyle \ \operatorname {mcd} (ma,mb)=|m|\cdot \operatorname {} (a,b)}

3. Si

        

p {} é un número primo, entón

        

mcd ⁡ ( , m ) = p {\displaystyle \ \operatorname {} (p,m)=p} ou ben

        

mcd ( m , p ) =

{\displaystyle \ \operatorname {} (m,p)=1}

4. Se d = mc ⁡ ( , n ) ,

        

=

″ ,

        

=

,

        

mc ( m

,

) =

{ d=\operatorname {mcd} (m,n),\ m=d'm'',\ n=d'n'',\ \operatorname {} (m'',n'')=1} , entón d = d

{\displaystyle \ d=d'}

5. Si

        

d ′ {\isplaystyle \ d'} é un divisor común de

        

{\displaystyle \ } e

        

{} , entón d

mcd ( m , n ) {\displaystyle d'\mid \operatorname {} (m,n)}

6. Se

        

m = n r { \ =q+} , etón mcd ⁡ ( m , n ) = ( n , r ) {\displaystyle \operatorname {mcd} (m,n)=\operatorname {} (n,r)}

7. Se

        

= p 1 α

k

e

=

β

,

,

, i = , . . . ,

{\displaystyl \ m=p_{1}^{\alpha _{1}}\cdots p_{k}^{\alpha _{k}}\;\,\mathrm {e} \;\,n=p_{1}^{\beta _{1}}\cdots p_{k}^{\beta _{k}},\;\,\alpha _{i},\beta _{i}\geq 0,\;\,i=1,...,k} , entón:

A última propiedade indica que o máximo divisor común de dous números é o produto dos seus factores primos comúns elevados ao menor expoñente.

Xeométricamente, o máximo divisor común de a e b é o número de puntos de coordenadas enteiras que hai no segmento que une os puntos (0,0) e (a,b), excluíndo o (0,0).

Proposicións

  1. Para calquera par de números enteiros a≠0, b≠0, existe un único mcd d ≥ 1.[5]
  2. O mcd. dos números a e b pode ser representado en forma de combinación linear destes números. Isto é (a, b) = ax + by
  3. Se dous números enteiros son primos entre si, i.e. o seu mcd = 1 ou noutra notación (a,b) = 1, entón cómpre a representación ma + nb = 1 onde m e n son números enteiros (identidade de Bézout).
  4. Se a|bc e (a,b) = 1, será a|c. Noutras palabras, se un número a divide un produto doutros dous números e é coprimo cun deles, entón divide necesariamente o outro número ou factor.[6]
  5. Cando un número a é coprimo cos números m e n, tamén o é co produto mn.
  6. (a,b) é divisor de (a, bc)[7]
  7. t(a,b) = (ta, tb) para todo t enteiro[8]
  8. Se (m, b)= 1 entón (am, b)= (a, b)[9]
  9. Se (m,b)= 1, (am, n) = 1 entón (am, bn) = (a, b)
  10. Para todo x, (a, b)= (b, a) = (a, -b) = (a, b + ax)[10]
  11. " Por definición, (0, 0) = 0 ".[11] Deste xeito o mcd definiríase en todo ℤxℤ.
  12. (a, b) = b se e só se b | a, (ou sexa se a é múltiplo de b).
  13. Se (a,b)= D, entón (an, bn) = Dn[12]
  14. mZ + nZ = (m,n)Z. Sumar senllos múltiplos de dous enteiros é o mesmo que considerar os múltiplos do seu máximo común divisor.[13]
  15. ( a 2 ,
                          b ,
       
         
         
                                       )         =         (
        ,
       
                           )
         
                                             {\displaystyle (a^{2},ab,b^{2})=(a,b)^{2}}[14]

MCD como operación interna

  • O mcd pódese estruturar como unha operación en ℤ; deste xeito a calquera par de enteiros, ou sexa a un elemento de ℤxℤ asígnalle un único elemento de ℤ.
  • Para calquera par de enteiros (a,b) existe un enteiro non negativo d que é o seu máximo común divisor. Isto é a*b = (a,b) = d
  • O mcd goza da propiedade asociativa, como da propiedade conmutativa.
  • O mcd posúe un elemento identidade, o cero, de modo tal que (a, 0)= (0,a)= a[15]
  • O mcd ten un comportamento dual que o mínimo común múltiplo e aos enteiros non negativos a e b lígaos a ecuación ab = (a,b)[a,b][16]
  • Propiedade do 1: (a,1) = 1 para calquera enteiro a[17]

Aplicacións

O mcd emprégase para simplificar fraccións. Por exemplo, para simplificar a fracción

8

{\displaystyle \scriptstyle {\frac {}{60}}} calcúlase primeiro o mcd(60, 48) = 12, dividíndose o numerador e o denominador da fracción inicial por 12 para obter a fracción simplificada 4

{\displaystyle \scriptstyle {\frac {4}{5}}} .

O mcd tamén se emprega para calcular o mínimo común múltiplo de dous números. En efecto, o produto dos dous números é igual ao produto do seu máximo divisor común polo seu mínimo común múltiplo. Así, para calcular o mínimo común múltiplo de 48 e de 60, calcúlase primeiro o seu mcd, 12, sendo o seu mínimo común múltiplo

=

{\displaystyle \scriptstyle {\frac {48\cdot 60}{12}}=240} .

O mcd e o algoritmo de Euclides empréganse na resolución de ecuacións diofánticas lineares con dúas incógnitas[18]

O algoritmo de Euclides emprégase no desenvolvemento dun número racional en fracción continuada (sic)[19]

Notas

  1. «División inexacta» (1997) Belski y Kaluzhin Editorial Científica, Lima; pg.10
  2. Ibídem, pg. 10
  3. Vinogradov: Fundamentos de la teoría de números, editorial mir.
  4. Castellet, Álgebra lineal y geometría, tema I.
  5. Ibídem, pg. 11
  6. Ibídem, pg. 13
  7. Vorobiov: Números de Fibonacci, Editorial Mr, Moscú (1974)
  8. Enzo gentile, Aritmética elemental, ediciones OEA
  9. Gentile: Aritmética elemental OEA
  10. Niven y Zuckerman: Teoría de los números
  11. Gentile: Aritmética elemental
  12. Santillana: "Aritmética razonada", Lima
  13. Kostrikin: Introducción al álgebra, Editorial Mir, Moscú (1974)
  14. Se pude comprobar teniendo en cuenta que (a/d, b/d)= 1, d=MCD
  15. Cotlar- Sadosky: Introducción al álgebra Eudeba, BS.
  16. Gentile: Ibídem
  17. Pues el 1 es divisor de todo entero, o bien genera los elementos de Z
  18. Ibídem pg. 17 y 20
  19. Gentile: Aritmética elemental OEA (1987)

Ligazóns externas