O máximo divisor comum (abreviadamente, MDC) entre dois ou mais números reais é o maior número real que é fator de tais números.[nota 1] Por exemplo, os divisores comuns de e são e , logo . A definição abrange qualquer número de termos, por exemplo . Com esta notação, dizemos que dois números inteiros e são primos entre si , se e somente se . Em alguns casos nós denotamos o mdc entre dois números simplesmente por .
No contexto da teoria dos anéis, um máximo divisor comum é definido de forma análoga: ele é um elemento que divide e , e tal que qualquer outro divisor comum de e é um divisor de . Nem sempre existe um máximo divisor comum, e nem sempre ele é único.
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 3]
Exemplo:
Achemos o de e . Note que: e , então (fatores comuns aos números e o menor expoente do fator. No caso do tínhamos expoentes e , mas pegamos o menor, daí ficou só e não 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 4]
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 5]
Slavin, Keith R. (2008). "Q-Binomials and the Greatest Common Divisor"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"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. (em inglês)
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. (em inglês)
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(em inglês).
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