Continuando a série de Teoria dos Números Visual, o tópico agora é o MDC.
O máximo divisor de comum de dois números a e b é o maior inteiro que divide a e b, sendo ambos diferentes de zero. Denota-se o mdc por (a,b).
Exemplo visual. Sejam a = 16 e b = 12. O mdc será d = 4, pois é o máximo de colunas que a base da composição pode ter para dividir tanto as pedrinhas de a quanto de b.
Utilizando o mesmo exemplo, 8 não é o mdc (12, 16), pois embora divida 16, vai deixar resto ao dividir 12 – é como se não conseguíssimos colocar todas as pedrinhas igualmente distribuídas em 8 colunas.
Seja d = mdc(a,b), então existem inteiros n e m tais que d = n*a + m*b.
Uma prova informal: se d|a e d|b, d|(m*a + n*b), conforme resultado já mostrado anteriormente, isso para qualquer m e n inteiros (positivo, negativo, zero). Ou seja, algum caso particular m0 e n0 vai dar a menor soma positiva possível c = m0*a + n0*b, e como d|( m0*a + n0*b), então d|c. Além disso, como c é a menor soma positiva possível, c = d.
Exemplo: 4 = 16*1 + 12*(-1)
Para uma prova mais formal, vide referência no final do texto.
O máximo divisor comum d de a e b é o divisor positivo de a e b o qual é divisível por todo divisor comum.
O mdc é o maior divisor comum, porém, isso não quer dizer que não haja outros divisores comuns. Se houver, esse divisor vai dividir o mdc.
Ex. 2 é divisor comum de 16 e 12, porém, não é o maior divisor comum.
E notar que 2 | 4, ou seja, um divisor comum de 16 e 12 vai dividir o mdc.
Para todo inteiro positivo t, (ta,tb) = t(a,b).
Exemplo visual:
Se c>0 e a e b são divisíveis por c, então, (a/c,b/c) = (a,b)/c.
É basicamente similar à proposição anterior, porém dividindo ao invés de multiplicar.
Exemplo visual:
mdc(12,16) =4
2|12 e 2|16
mdc(12/2,16/2) =4/2 =2
Para uma prova mais formal, vide referência abaixo.
Referência: Introdução à Teoria dos Números, José Plínio de Oliveira Santos, Instituto Nacional de Matemática Pura e Aplicada.
Veja também:
Forgotten Lore - Ideias Técnicas com uma pitada de filosofia.