Máximo común divisor: Diferenzas entre revisións
→Aplicacións: Arranxos |
→Propiedades: Arranxos |
||
Liña 98: | Liña 98: | ||
== Propiedades == |
== Propiedades == |
||
1. Se <math>\ \operatorname{mcd}(a,b)=d</math> entón <math>\ \operatorname{mcd} \left(\frac{a}{d}, \frac{b}{d}\right)= 1 </math> |
|||
1. Se |
|||
2. Se <math>\ m</math> é un enteiro, <math>\ \operatorname{mcd}(ma,mb)= |m|\cdot \operatorname{mcd}(a,b)</math> |
|||
3. Se <math>\ p</math> é un número primo, entón <math>\ \operatorname{mcd}(p,m)=p</math> o bien <math>\ \operatorname{mcd}(m,p)=1</math> |
|||
mcd |
|||
4. Se <math>d=\operatorname{mcd}(m,n),\ m=d'm'',\ n=d'n'',\ \operatorname{mcd}(m'',n'')=1</math>, entón <math>\ d=d' </math> |
|||
|
|||
5. Se <math>\ d'</math> é un divisor común de <math>\ m</math> e <math>\ n</math>, entón <math>d'\mid \operatorname{mcd}(m,n)</math> |
|||
( |
|||
6. Se <math>\ m=nq+r</math>, entón <math>\operatorname{mcd}(m,n)=\operatorname{mcd}(n,r)</math> |
|||
a , |
|||
7. Se <math>\ m=p_1^{\alpha_1}\cdots p_k^{\alpha_k}\;\, \mathrm y \;\, n=p_1^{\beta_1}\cdots p_k^{\beta_k},\;\, \alpha_i, \beta_i\geq 0, \;\, i=1,...,k</math>, entón <math> \operatorname{mcd}(m,n)=p_1^{\operatorname{min}(\alpha_1,\beta_1)}\cdots p_k ^ {\operatorname{min} (\alpha_k, \beta_k)} </math> Esta ú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. |
|||
b |
|||
) |
|||
= |
|||
<math /> |
|||
{\<math />ispl<math />ystyle \ \operatorname {<math />} (a,<math />)=d} |
|||
entón |
|||
mcd |
|||
<math /> |
|||
( |
|||
a |
|||
d , |
|||
b |
|||
d |
|||
) |
|||
= |
|||
<math /> |
|||
{\displaystyle \ \operatorname {<math /><nowiki>} \left({\frac {a}{d}},{\frac {b}{d}}\right)=1}</nowiki><math /> |
|||
2. Si |
|||
m |
|||
{<math />} |
|||
é un enteiro, |
|||
<math />cd |
|||
|
|||
( |
|||
<math /> |
|||
<math /> , |
|||
<math /> |
|||
b |
|||
) |
|||
= |
|||
<nowiki>|</nowiki> |
|||
m |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
( |
|||
a , |
|||
<math /> |
|||
) |
|||
{\displaystyle \ \operatorname {mcd} (ma,mb)=|m|\cdot \operatorname {<math />} (a,b)}<math /> |
|||
3. Si |
|||
p |
|||
{<math />} |
|||
é un número primo, entón |
|||
mcd |
|||
|
|||
( |
|||
<math /> |
|||
, |
|||
m |
|||
) |
|||
= |
|||
p |
|||
{\displaystyle \ \operatorname {<math />} (p,m)=p} |
|||
ou ben |
|||
mcd |
|||
<math /> |
|||
( |
|||
m |
|||
, |
|||
p |
|||
) |
|||
= |
|||
<math /> |
|||
{\displaystyle \ \operatorname {<math />} (m,p)=1}<math /> |
|||
4. Se |
|||
d |
|||
= |
|||
mc<math /> |
|||
|
|||
( |
|||
<math /> |
|||
, |
|||
n |
|||
) |
|||
, |
|||
<math /> |
|||
= |
|||
<math /> |
|||
′ |
|||
<math /> |
|||
″ |
|||
, |
|||
<math /> |
|||
= |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
, |
|||
mc<math /> |
|||
<math /> |
|||
( |
|||
m |
|||
<math /> |
|||
, |
|||
<math /> |
|||
<math /> |
|||
) |
|||
= |
|||
<math /> |
|||
{<math /> d=\operatorname {mcd} (m,n),\ m=d'm<nowiki>''</nowiki>,\ n=d'n<nowiki>''</nowiki>,\ \operatorname {<math />} (m<nowiki>''</nowiki>,n<nowiki>''</nowiki>)=1} |
|||
, entón |
|||
d |
|||
= |
|||
d |
|||
<math /> |
|||
{\displaystyle \ d=d'}<math /> |
|||
5. Si |
|||
d |
|||
′ |
|||
{\<math />isplaystyle \ d'} |
|||
é un divisor comú<math />n de |
|||
<math /> |
|||
{\displaystyle \ <math />} |
|||
e |
|||
<math /> |
|||
{<math />} |
|||
, entón |
|||
d |
|||
<math /> |
|||
<math /> |
|||
mcd |
|||
<math /> |
|||
( |
|||
m |
|||
, |
|||
n |
|||
) |
|||
{\displaystyle d'\mid \operatorname {<math />} (m,n)} |
|||
[[Xeometría|Xeometricamente]], 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). |
|||
6. Se |
|||
m |
|||
= |
|||
n |
|||
<math /> |
|||
<math /> |
|||
r |
|||
{<math /> \ <math />=<math />q+<math />} |
|||
, e<math />tón |
|||
mcd |
|||
|
|||
( |
|||
m |
|||
, |
|||
n |
|||
) |
|||
= |
|||
<math /> |
|||
<math /> |
|||
( |
|||
n |
|||
, |
|||
r |
|||
) |
|||
{\displaystyle \operatorname {mcd} (m,n)=\operatorname {<math />} (n,r)}<math /> |
|||
7. Se |
|||
<math /> |
|||
= |
|||
p |
|||
1 |
|||
α |
|||
<math /> |
|||
⋯ |
|||
<math /> |
|||
k |
|||
<math /> |
|||
<math /> |
|||
e |
|||
<math /> |
|||
= |
|||
<math /> |
|||
<math /> |
|||
β |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
, |
|||
<math /> |
|||
<math /> |
|||
, |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
<math /> |
|||
, |
|||
i |
|||
= |
|||
<math /> |
|||
, |
|||
. |
|||
. |
|||
. |
|||
, |
|||
<math /> |
|||
{\displaystyl<math /><nowiki> \ 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:</nowiki> |
|||
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. |
|||
[[Xeometría|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 === |
=== Proposicións === |
Revisión como estaba o 26 de maio de 2017 ás 20:02
Esta páxina ou sección está a editarse nestes intres. Para evitar posibles conflitos de edición, non edites esta páxina ou sección mentres vexas esta mensaxe. Revisa o historial de edicións para saber quen traballa nela. O usuario Jglamela (conversa · contribucións) realizou a última edición na páxina hai 6 anos. O tempo máximo de presenza deste marcador é dun mes dende a última edición do usuario que o puxo; pasado ese tempo debe retirarse. |
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:
- d é divisor común dos números a e b e
- 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: .[3][4]
Propiedades
1. Se entón 2. Se é un enteiro, 3. Se é un número primo, entón o bien 4. Se , entón 5. Se é un divisor común de e , entón 6. Se , entón 7. Se , entón Esta ú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.
Xeometricamente, 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
- Para calquera par de números enteiros a≠0, b≠0, existe un único mcd d ≥ 1.[5]
- 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
- 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).
- 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]
- Cando un número a é coprimo cos números m e n, tamén o é co produto mn.
- (a, b) é divisor de (a, bc)[7]
- t(a, b) = (ta, tb) para todo t enteiro[8]
- Se (m, b)= 1 entón (am, b)= (a, b)[9]
- Se (m, b)= 1, (am, n) = 1 entón (am, bn) = (a, b)
- Para todo x, (a, b)= (b, a) = (a, -b) = (a, b + ax)[10]
- Por definición, (0, 0) = 0;[11] deste xeito o mcd defínese en todo ℤ×ℤ.
- (a, b) = b se e só se b|a, (ou sexa se a é múltiplo de b).
- Se (a, b)= D, entón (an, bn) = Dn[12]
- 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]
- [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 ℤ×ℤ 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, pois o 1 é divisor de todos os enteiros, ou ben xenera os elementeos de ℤ.
Aplicacións
O mcd emprégase para simplificar fraccións. Por exemplo, para simplificar a fracción 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 .
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 .
O mcd e o algoritmo de Euclides empréganse na resolución de ecuacións diofánticas lineares con dúas incógnitas[17] e para desenvolver un número racional en fraccións continuas.[18]
Notas
- ↑ Belski e Kaluzhin, División inexacta (1997). Editorial Científica, Lima; páx.10
- ↑ Ibídem, páx. 10
- ↑ Vinogradov: Fundamentos de la teoría de números, editorial Mir.
- ↑ Castellet, Álgebra lineal y geometría, tema I.
- ↑ Ibídem, páx. 11
- ↑ Ibídem, páx. 13
- ↑ Vorobiov: Números de Fibonacci, Editorial Mir, Moscova (1974)
- ↑ Enzo Gentile, Aritmética elemental, ediciones OEA
- ↑ Gentile: Aritmética elemental OEA
- ↑ Niven e Zuckerman: Teoría de los números
- ↑ Gentile: Aritmética elemental
- ↑ Santillana: "Aritmética razonada", Lima
- ↑ Kostrikin: Introducción al álgebra, Editorial Mir, Moscú (1974)
- ↑ Pódese comprobar tendo en conta que (a/d, b/d)= 1, d=MCD
- ↑ Cotlar-Sadosky: Introducción al álgebra. Eudeba, BS.
- ↑ Gentile: Ibídem
- ↑ Ibídem páx. 17 y 20
- ↑ Gentile: Aritmética elemental OEA (1987)
Véxase tamén
Bibliografía
- Andrews, George E. (1994) [1971]. Number Theory. Dover. ISBN 9780486682525.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp. 856–862.
- Hardy, G. H.; Wright, E. M. (1979). An Introduction to the Theory of Numbers (Fifth ed.). Oxford: Oxford University Press. ISBN 978-0-19-853171-5.
- Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.2: The Greatest Common Divisor, pp. 333–356.
- Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77171950.
- Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 71081766.
- Saunders MacLane e Garrett Birkhoff. A Survey of Modern Algebra, Fourth Edition. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1–7: "The Euclidean Algorithm."