7
EM_V_MAT_002
Existência e unicidade do MDC
Sejam a e b dois inteiros não simultaneamente
nulos, então mdc (a, b) existe e é único; além disso,
existem x e y tais que mdc (a, b) = ax + by, isto é, o
mdc (a, b) é uma combinação linear de a e b.
A representação do mdc (a, b) como combinação
linear de a e b não é única. Na verdade, mdc (a, b) =
d = a(x + bt) + b(y – at) para qualquer inteiro t.
Números primos entre si
Diz-se que a e b são primos entre si se, e so-
mente se, o mdc (a, b) = 1.
Ex.: são primos entre si os pares 2 e 5, 9 e 16 e
20 e 21.
Dois inteiros primos entre si admitem como
únicos divisores comuns 1 e – 1.
Teorema: Dois inteiros a e b, não simultanea-
mente nulos, são primos entre si se, e somente se,
existem inteiros x e y, tais que ax + by = 1.
Corolário: Se mdc (a,b) = d, então o mdc (a/d,
b/d) = 1.
Corolário: Se a
b e se mdc (b,c) = 1, então mdc
(a,c)=1.
Corolário: Se a c, b c e mdc (a, b) = 1, então
ab c.
Corolário: mdc (a, b)=mdc (a, c)=1 se, e somen-
te se, mdc (a, bc)=1.
Teorema de Euclides: Se a bc e mdc (a, b) =
1, então a c.
Algoritmo de Euclides
Teorema: Se a = bq + r, então mdc (a, b) =
mdc (b, r).
O algoritmo de Euclides é baseado na aplicação
repetida do lema acima e é normalmente apresentado
por intermédio do seguinte dispositivo prático:
q
1
q
2
q
3
... q
n
q
n+1
a b r
1
r
2
... r
n-1
r
n
r
1
r
2
r
3
... r
n
0
O aparecimento do resto 0 indica r
n
= mdc (a, b).
Exemplos: ``
mdc (963, 657) = 9 1 2 6 1 4
963 657 30645 36 9
30645 36 9 0
Teorema: Para todo k≠0, mcd (ka, kb)=| k| – mcd
(a,b).
MDC a partir das
decomposições canônicas
Conhecidas as decomposições canônicas de dois
inteiros positivos a e b, o mdc (a,b) é o produto dos fa-
tores primos comuns as duas decomposições tomados
com seus menores expoentes.
Exemplos: ``
588 = 2
2
. 3 . 7
2
e 936 = 2
3
. 3
2
. 13, logo mdc (588,936)
= 2
2
. 3 = 12.
Mínimo múltiplo comum
(MMC)
O conjunto de todos os múltiplos de um inteiro
qualquer a
0 indica-se por M(a), ou seja, M(a) = {x
Z tal que ax} = {aq q Z}.
Exemplos: ``
M(1) = M(–1) = Z e M (5) = {0, 5, 10, 15, 20, ...}
Sejam a e b dois inteiros não-nulos. Chama-se múltiplo
comum de a e b todo inteiro x tal que a x e b x.
M(a,b) = {x Z / a x e b x}={x Z / x M(a) e x
M(b)}
M(a,b) = M(a) M(b)
Exemplo: M(12)={12q\q
Z}={0,12,24,36,48,60,72,...}
M(18)={18q\q Z}={0,18,36,54,72,90,108,...}
M(12,18) = M(12) M(18) = {0, 36, 72, ...}
Sejam a e b dois inteiros não-nulos. Chama-se míni-
mo múltiplo comum de a e b o inteiro positivo m =
mmc(a,b) que satisfaz as condições:
(1) a m e b m
(2) se a c e bc, com c > 0, então m c.
Exemplo: ``
mmc (12,18) = 36
Corolários
mmc (a,b) ••
ab Esse material é parte integrante do Aulas Particulares on-line do IESDE BRASIL S/A,
mais informações www.aulasparticularesiesde.com.br