Como encontrar o maior divisor comum de dois números inteiros?

Calcule o máximo divisor comum (MDC) usando o algoritmo de Euclides.

O algoritmo de Euclides faz divisões sucessivas: dado \(a>b\), escreve-se \(a=b\cdot q+r\), substitui-se \((a,b)\) por \((b,r)\) e repete até obter resto zero; o último divisor não nulo é o MDC.

Exemplo:
Calcular \(MDC(30,18)\):
\(30=18\cdot1+12\)
\(18=12\cdot1+6\)
\(12=6\cdot2+0\)
Logo \(MDC(30,18)=6\).
Assim, o maior comprimento inteiro que divide ambas as medidas é 6, e os quocientes são \(30/6=5\) e \(18/6=3\).