Universidade Federal do Rio de Janeiro

Instituto de Matemática
Prof. Tulio Gentil

Álgebra I - Números Inteiros

Aula 08 - Máximo divisor comum e Mínimo múltiplo comum

1 Ideais e Máximo divisor comum

Um subconjunto não-vazio J de Z é dito ser um ideal de Z se:
i) α, β ∈ J implica que α + β ∈ J;
ii) α ∈ J e n ∈ Z implica que nα ∈ Z.
Exemplo 1.1. a) Os conjuntos Z e {0} são ideais de Z, chamados ideais triviais de
Z.
b) Dado m ∈ Z, denotaremos por mZ o conjunto consistindo de todos os múltiplos de
m, isto é,
mZ = {mx |x ∈ Z}.
Pode-se mostrar que mZ é um ideal de Z e além disso, todo ideal de Z é da forma
mZ para algum inteiro não negativo m.
Vamos assumir aqui que a, b são números inteiros não nulos. Um inteiro c é dito ser
divisor comum de a e b se c|a e c|b. O conjunto D(a, b) de todos os divisores de a e b
é não vazio (1 ∈ D(a, b) e é limitado superiormente, pois para c ∈ D(a, b) c ≤ |a| (já
que a ̸= 0). Pelo Princípio da Boa Ordem, D(a, b) admite elemento máximo, o qual é
chamado de máximo divisor comum de a e b e é denotado por
mdc(a, b) = max D(a, b).
Teorema 1.2. (Bezout) Sejam a, b ∈ Z e d = mdc(a, b). Então existem r, s ∈ Z tais que
d = ra + sb.
Demonstração. Defina o conjunto
J = {xa + yb | x, y ∈ Z}.
Mostraremos que J é um ideal de Z.
i) Sejam α, β ∈ J, então existem x1 , x2 , y1 , y2 ∈ Z tais que
α = x1 a + y1 b, β = x2 a + y2 b.
Assim,
α + β = (x1 + x2 )a + (y1 + y2 )b ∈ J.
 ii) Sejam α ∈ J e n ∈ Z, então
α = xa + yb
e
nα = (nx)a + (ny)b ∈ J.

Assim, pelo Exemplo 1.1, temos que existe um inteiro x0 tal que J = x0 Z. Afirmamos
que x0 = d = mdc(a, b) = d. De fato, note que a ∈ J, pois a = a · 1 + b · 0. Logo, x0 |a
e analogamente x0 |b. Portanto, x0 ∈ D(a, b). Além disso, como x0 ∈ J, x0 = ra + sb,
onde r, s ∈ Z. Finalmente, precisamos mostrar que x0 é o máximo de D(a, b). Seja
d′ ∈ D(a, b). Como d′ |a e d′ |b, então d′ |ra + sb, ou seja, d′ |x0 e, portanto, |d′ | ≤ |x0 | = x0
e x0 é o maior divisor de a e b.

Teorema 1.3. Sejam a, b ∈ Z. Um inteiro positivo d é o máximo divisor comum de a e

b se, e somente se as seguintes condições são verificadas:

i) d|a e d|b

ii) Se d′ |a e d′ |b então d′ |d.

Demonstração. Seja d = mdc(a, b). Então, pela definição a condição i) é satisfeita, e na

demonstração do Teorema de Bezout, mostramos que a condição ii) é também verificada.
Reciprocamente, se d ∈ Z verifica a condição i), então d ∈ D(a, b). A condição ii)
afirma que se d′ ∈ D(a, b), então d′ |d e portanto d′ ≤ d, donde d é o maior elemento de
D(a, b).

Proposição 1.4. Sejam a, b ∈ Z, d = mdc(a, b) e 0 ̸= c ∈ Z. Então:

i) mdc(ac, bc) = d|c|.

ii) Se c|a e c|b, então mdc(a/c, b/c) = d/|c|.

Demonstração. Exercício.

Teorema 1.5. (Euclides) Sejam a, b, c ∈ Z tais que a|bc. Se mdc(a, b) = 1, então a|c.

Demonstração. Como mdc(a, b) = 1, pela Proposição 1.4, mdc(ac, bc) = |c|. Note que
a|ac e por hipótese a|bc, e usando o item ii) do Teorema 1.3, temos a||c|. Portanto,
a|c.
Dizemos que dois inteiros não nulos a e b são relativamente primos se mdc(a, b) = 1.
Assim, o Teorema de Euclides pode ser enunciado da seguinte maneira: Sejam a e b
inteiros relativamente primos e c outro inteiro tal que a|bc, então a|c.
Vamos, a seguir, construir um método para calcular o mdc entre dois números inteiros.

Lema 1.6. Sejam a, b inteiros não nulos e sejam q, r o quociente e o resto da divisão
de a por b, respectivamente. Então D(a, b) = D(b, r) e consequentemente, mdc(a, b) =
mdc(b, r).
Demonstração. Pelo algoritmo da divisão de Euclides, podemos escrever a, de maneira
única, na forma a = bq + r, onde q, r ∈ Z e 0 ≤ r < |b|.
Seja x ∈ D(a, b). Então x|a e x|b. Como r = a − bq e x divide cada um dos somandos,
temos que x|r. Logo, x ∈ D(b, r). Agora, seja x ∈ D(b, r). Como a = bq + r, segue que
x|a e portanto, x ∈ D(a, b).
Sejam a, b ∈ Z, pelo algoritmo de Euclides, existem únicos q1 , r1 ∈ Z tais que
a = bq1 + r1 , 0 ≤ r1 < |b|.
O lema anterior nos diz que se
mdc(a, b) = mdc(b, r1 ).
Usando o algoritmo de Euclides para b e r1 , temos que exitem únicos q2 , r2 ∈ Z tais que
b = r1 q2 + r2, 0 ≤ r2 < |b|
e além disso,
mdc(a, b) = mdc(b, r1 ) = mdc(r1 , r2 ).
Continuando o processo,
r1 = r2 q3 + r3, 0 ≤ r3 < r2
e
mdc(a, b) = mdc(b, r1 ) = mdc(r1 , r2 ) = mdc(r2 , r3 ).
Continuando o procedimento acima, o resto diminui a cada etapa e em algum passo a
divisão deve deixar resto zero. Se rn+1 é o primeiro resto nulo, então mdc(rn−1 , rn ) = rn
e logo, mdc(a, b) = rn , ou seja, é o último resto não nulo.
Podemos reunir essas informações no dispositivo prático abaixo:
q1 q2 q3 ··· ··· qn qn+1
a b r1 r2 ··· rn−2 rn−1 rn
r1 r2 r3 ··· ··· rn 0
Exemplo 1.7. A tabela abaixo, mostra que mdc(1128, 336) = 24.
3 2 1 4
1128 336 120 96 24
120 96 24 0
As divisões sucessivas são:

1128 = 3 · 336 + 120. (1)

336 = 2 · 120 + 96. (2)

120 = 1 · 96 + 24. (3)

96 = 4 · 24. (4)
 O par de inteiros r, s do Teorema de Bezout pode ser obtido fazendo sucessivas subs-
tituições das equações obtidas usando o algoritmo de Euclides.
Por exemplo, de (1), temos que

120 = 1128 − 3 · 336

e substituindo em (2), temos que

336 = 2(1128 − 3 · 336) + 96

e portanto,
96 = −2 · 1128 + 7 · 336.
Finalmente, em (3)

1128 − 3 · 336 = (−2 · 1128 + 7 · 336) + 24.

Portanto,
24 = 3 · 1128 − 10 · 336.
Logo, o par de inteiros r, s dado nas condições do Teorema de Bezout são r = 3 e
s = −10.

2 Mínimo múltiplo comum

Sejam a, b inteiros não nulos. Um número c ∈ Z chama-se múltiplo comum de a e b
se a|c e b|c. Indicaremos por M (a, b) o conjunto de todos os múltiplos comuns de a, b
e por M + (a, b) o conjunto de todos os múltiplos comuns positivos de a e b. Note que
M + (a, b) é um subconjunto não vazio de Z, pois |a||b| ∈ M + (a, b) e além disso, é limitado
inferiormente. Portanto, pelo Princípio da Boa Ordem, M + (a, b) tem menor elemento, o
qual é chamado de mínimo múltiplo comum de a e b e denotaremos por

mmc(a, b) = min M + (a, b).

Lema 2.1. Sejam a, b inteiros não nulos, então mmc(a, b) divide todo outro múltiplo
comum de a e b.
Demonstração. O conjunto M (a, b) é um ideal de Z. De fato, sejam α, β ∈ M (a, b).
Por definição de M (a, b), a|α e a|β; logo, a|(α + β). Analogamente, b|α + β. Agora,
sejam n ∈ Z e α ∈ M (a, b). Então, a|α e logo a|nα. Pelo Exemplo 1.1 M (a, b) = mZ
para algum inteiro não negativo m, onde m = min M + (a, b) = mmc(a, b). Assim, se
m′ ∈ M (a, b) = mZ, então então m|m′ .
Teorema 2.2. Sejam a, b inteiros positivos e m um inteiro positivo. Então, m =
mmc(a, b) se, e somente se as seguintes condições são verificadas:
i) a|m, b|m;

ii) se a|m′ e b|m′ , então m|m′ .

Demonstração. Da definição, mmc(a, b) verifica a condição i) e do lema anterior, mmc(a, b)
verifica a condição ii) do enunciado. Reciprocamente, se m verifica a condições i) e ii) do
enunciado, temos que i) implica que m ∈ M + (a, b) e ii), implica que que m ≤ |m′ . Logo,
m = mmc(a, b).

Teorema 2.3. Sejam a, b ∈ Z, d = mdc(a, b) e m = mmc(a, b). Então m · d = |a · b|, ou

seja
|a · b|
mmc(a, b) = .
mdc(a, b)
Demonstração.
Sem perda de generalidade, podemos supor a e b positivos, pois mmc(a, b) = mmc(|a|, |b|).
Seja
ab
x= .
d
Vamos mostrar que x = m e faremos isso mostrando que x verifica as condições i) e ii)
do Teorema 2.3. Como d|a e d|b, existem a1 , b1 ∈ Z tais que

a = a1 d, b = b1 d.

Pela Proposição 1.4, temos que mdc(a1 , b1 ) = mdc(a/d, b/d) = d/d = 1. Além disso,
podemos escrever x = ab1 e x = a1 b e assim a|x e b|x, e portanto, a condição i) é
satisfeita.
Agora, considere m′ ∈ Z um múltiplo comum de a e b. Como a|m′ , existe q ∈ Z tal
que m′ = aq = a1 dq. Além disso, b|m′ , i.e, b1 d|a1 dq e logo, b1 |a1 q.
Como mdc(a1 , b1 ) = 1, segue o Teorema de Euclides que b1 |q e logo q = b1 c para algum
c ∈ Z, e substituindo na expressão de m′ , segue que m′ = a1 db1 c, ou seja, m′ = xc e logo,
x|m′ . Portanto, x verifica a condição ii).

Exemplo 2.4.
1128 · 336 379008
mmc(1128, 336) = = = 15792.
mdc(1128, 336) 24