Divisibilidade

Nos exemplos constatámos que o \(m.d.c.\) também é máximo para \(\trianglelefteq \) ( o que quer dizer que o \(m.d.c.\) é múltiplo de qualquer divisor comum, ou que qualquer divisor comum é divisor do máximo divisor comum).

Vamos ver que o algoritmo de Euclides dá sempre um divisor comum que é máximo para \(\trianglelefteq \):

quando temos \[\begin{array}{ccl} a & = & bq_{1}+r_{1}\\ b & = & r_{1}q_{2}+r_{2}\\ r_{1} & = & r_{2}q_{3}+r_{3}\\ r_{2} & = & r_{3}q_{4}+r_{4}\\ r_{3} & = & r_{4}q_{5} \end{array}\] os divisores comuns de \(a\) e \(b\) são os divisores de \(r_{4}\) e \(r_{4}\) é o \(m.d.c.\) de \(a\) e \(b\), como na página sobre o algoritmo de Euclides; então todos os divisores comuns de \(a\) e \(b\) são divisores do \(m.d.c.\) de \(a\) e \(b\).

É neste sentido (de máximo para \(\trianglelefteq \)) que deve ser interpretada a palavra "máximo" em "máximo divisor comum"; com este significado, faz sentido falar em máximo divisor comum em muitas outras situações.