Mostrar código-fonte de Máximo divisor comum

{{Reciclagem|data=janeiro de 2022}}
[[Ficheiro:MCD Insiemi.png|miniaturadaimagem|Máximo Divisor Comum]]
O '''máximo divisor comum''' (abreviadamente, '''MDC''') entre dois ou mais [[números reais]] é o maior número real que é [[factorização|fator]] de tais números.<ref name="viana.71" group="nota">Vianna (1914), [[s:Elementos de Arithmetica/Capítulo 2#Item 83|p. 71]].</ref> Por exemplo, os divisores comuns de <math>12</math> e <math>18</math> são <math>1,2,3</math> e <math>6</math>, logo <math>mdc(12,18)=6</math>. A definição abrange qualquer número de termos, por exemplo <math>mdc(10,15,25,30) = 5</math>. Com esta notação, dizemos que dois números inteiros <math>a</math> e <math>b</math> são primos entre si , se e somente se <math>mdc(a, b) = 1</math>. Em alguns casos nós denotamos o mdc entre dois números simplesmente por <math>(a,b)</math>.

No contexto da [[teoria dos anéis]], um '''máximo divisor comum''' é definido de forma análoga: ele é um elemento <math>m</math> que divide <math>a</math> e <math>b</math>, e tal que qualquer outro divisor <math>x</math> comum de <math>a</math> e <math>b</math> é um divisor de <math>m</math>. Nem sempre existe um máximo divisor comum, e nem sempre ele é único.

== Propriedades ==

# Se <math>b > 0</math> e é um divisor de <math>a</math>, então <math>mdc(a, b) = b</math>.{{nota de rodapé|Vianna (1914), [[s:Elementos de Arithmetica/Capítulo 2#Item 84|p. 72]].}}
# Todo número que for divisor comum de <math>a</math> e <math>b</math> também é um divisor de <math>mdc(a,b)</math>;
# Considerando que todos os números são fatores de <math>0</math> (pois <math>0=0.a</math> para qualquer <math>a</math> inteiro) então <math>mdc(a,0)=|a|</math>;
# Se <math>m</math> é um inteiro não negativo então <math>mdc(m.a,m.b)=m.mdc(a,b)</math>;
# Se <math>mdc(a,b)=1</math> então <math>mdc(a.b,c)=mdc(a,c).mdc(b,c)</math>;
# <math>mdc(a,b)=mdc(b,a)</math>;
# <math>mdc(-a,b)=mdc(a,-b)=mdc(-a,-b)=mdc(a,b)</math>;
# Se <math>a</math> é um inteiro positivo então <math>mdc(a,a)=a</math>;
# Calcular o máximo divisor comum é uma operação [[associativa]]: <math>mdc(a,mdc(b,c))=mdc(mdc(a,b),c) = mdc(a,b,c)</math>;
# Tem-se . <math>mdc(a,b).mmc(a,b) = ab</math>, onde <math>mmc(a,b)</math> representa o [[mínimo múltiplo comum]];
# O máximo divisor comum e o mínimo múltiplo comum verificam as seguintes propriedades [[distributiva]]s:
#:<math>mdc(a, mmc(b,c))=mmc(mdc(a,b),mdc(a,c))</math>
#:<math>mmc(a,mdc(b,c))=mdc(mmc(a,b), mmc(a,c))</math>;
#:<math>mdc(ca,cb) = c.mdc(a,b)</math>;
#Se <math>p</math> é um número primo <math>mdc(p,a)=p</math> ou <math>mdc(p,a)=1</math>;
# ([[Identidade de Bézout]]) Se <math>d = mdc(a,b)</math>, então existem inteiros <math>x</math> e <math>y</math> tais que <math>d = ax + by</math>;
# Se <math>ax + by = 1</math>, então <math>mdc(a,b) = 1</math>;
# Se <math>c > 0</math> e <math>a</math> e <math>b</math> são divisíveis por <math>c</math> então: <math>mdc(\frac{a}{c},\frac{b}{c}) = \frac{1}{c} mdc(a, b)</math>;
# Se <math>a</math> e <math>b</math> são inteiros e <math>a = q*b + r</math> onde <math>q</math> e <math>r</math> são inteiros, então: <math>mdc(a,b) = mdc(b, r)</math>.

== Determinação do máximo divisor comum ==

Há duas formas de determinar o máximo divisor comum de dois números:

# A primeira é fatorar os números e a partir daí, pegar os fatores comuns a todos números e deixá-los com o menor expoente que o fator analisado apresentar entre todos os números.{{nota de rodapé|Vianna (1914), [[s:Elementos de Arithmetica/Capítulo 2#Item 89|p. 77]].}}
# Exemplo:
#: Achemos o <math>MDC</math> de <math>30</math> e <math>12</math>. Note que: <math>30 = 2 \times 3 \times 5</math> e <math>12=3 \times 2^2</math>, então <math>(30,12) = 2 \times 3 </math>  (fatores comuns aos números e o menor expoente do fator. No caso do <math>2</math> tínhamos expoentes <math>1</math> e <math>2</math>, mas pegamos o menor, daí ficou só <math>2</math> e não <math>2</math> ao quadrado).
# A segunda consiste em escrever os dois números, separados por um traço vertical; em seguida, compara-se os números, e em baixo do maior deles coloca-se a diferença entre os dois. Agora compara-se o último número que se escreveu, com o que ficou na outra coluna, repetindo-se o processo até que se obtenha igualdade entre os números nas duas colunas, que é o resultado procurado.{{nota de rodapé|Vianna (1914), [[s:Elementos de Arithmetica/Capítulo 2#Item 85|p. 73]].}}

=== Algoritmo de Euclides ===

{{artigo principal|[[Algoritmo de Euclides]]}}

O algoritmo de Euclides consiste em efectuar divisões sucessivas entre dois números até obter resto zero. O máximo divisor comum entre os dois números iniciais é o último resto diferente de zero obtido. Este método não requer qualquer [[factorização]].{{nota de rodapé|Vianna (1914), [[s:Elementos de Arithmetica/Capítulo 2#Item 84|p. 72-74]].}}

== Ver também ==

{{div col}}
* [[Fatorização]]
* [[Número primo]]
* [[Algoritmo de Euclides]]
* [[Mínimo múltiplo comum]]
* [[Números primos entre si]]
* [[Algoritmo de Euclides]]
* [[Algoritmo de Euclides estendido]]

{{div col end}}

{{notas}}

{{Referências}}
* {{Citar livro|nome=João José Luiz|sobrenome=Vianna|título=[[s:Elementos de Arithmetica|Elementos de Arithmetica]]|edição=15|local=Rio de Janeiro|editora=Francisco Alves|ano=1914}}

== Bibliografia ==

# Jaime Evaristo, '''Introdução à Álgebra com aplicações à Ciência da Computação''', UFAL, ISBN 8-571-77058-1.
# Jaime Evaristo, '''Introdução à álgebra abstrata''', UFAL, 1999 ISBN 8-571-77125-1.
# Mary Jane Sterling, '''Álgebra I Para Leigos''', Alta Books Editora, 2013 ISBN 8-576-08256-X
# Taiane Vieira, Roberto Giugliani, '''Matemática Discreta''' - 3ed: Coleção Schaum, Bookman Editora, 2013 ISBN 8-565-83778-5
# Slavin, Keith R. (2008). '''"Q-Binomials and the Greatest Common Divisor"''' [http://www.integers-ejcnt.org/vol8.html Ver Artigo]. Integers Electronic Journal of Combinatorial Number Theory (University of West Georgia, Charles University in Prague) 8: A5.
# Schramm, Wolfgang (2008). '''"The Fourier transform of functions of the greatest common divisor"''' [http://www.integers-ejcnt.org/vol8.html Ver Artigo]. Integers Electronic Journal of Combinatorial Number Theory (University of West Georgia, Charles University in Prague) 8: A50. 
# Knuth, Donald E.; Graham, R. L.; Patashnik, O. (March 1994). '''Concrete Mathematics: A Foundation for Computer Science'''. Addison-Wesley. ISBN 0-201-55802-5. {{en}}
# Nymann, J. E. (1972). '''"On the probability that k positive integers are relatively prime"'''. Journal of Number Theory 4 (5): 469–473. {{DOI|10.1016/0022-314X(72)90038-8}}. {{en}}
# Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). '''"On the probability that the values of m polynomials have a given g.c.d."'''. Journal of Number Theory 26 (3): 237–245. {{DOI|10.1016/0022-314X(87)90081-3}} {{en}}.
# Chor, B.; Goldreich, O. (1990). '''"An improved parallel algorithm for integer GCD"'''. Algorithmica 5 (1–4): 1–10. {{DOI|10.1007/BF01840374}}.
# Andreescu, T; Feng, Z., 104 Number Theory Problems from Training of the USA IMO Team, Australian Mathematics Trust

== Ligações externas ==
{{Wikilivros|Teoria de números|Máximo divisor comum}}
{{Wikisource|Elementos de Arithmetica|Elementos de Arithmetica}}

* [http://www.leonel.profusehost.net/maxdivc.htm Calculadora on-line do máximo divisor comum de dois ou mais números inteiros.]
* [http://gcd.awardspace.com/index_pr.php A calculadora on-line GCD. (4 métodos)]

{{esboço-matemática}}
{{Controle de autoridade}}
{{Portal3|Matemática}}

{{DEFAULTSORT:Maximo Divisor Comum}}
[[Categoria:Teoria dos números]]