Máximo Divisor Comum

MA14 - Aritmética
Unidade 5
Algoritmo de Euclides
(Máximo Divisor Comum)
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o domı́nio do assunto.
O material completo a ser estudado encontra-se no
Capı́tulo 5 - Seção 5.1
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 2/19
Divisor Comum
Sejam a e b dois inteiros, distintos ou não. Um número inteiro d
será dito um divisor comum de a e b se d|a e d|b.
Por exemplo, os números ±1, ±2, ±3 e ±6 são os divisores
comuns de 12 e 18.
A definição a seguir foi essencialmente dada por Euclides nos
Elementos e se constitui em um dos pilares da sua aritmética.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 3/19
Definição: Máximo Divisor Comum
Um número inteiro d > 0 é um máximo divisor comum (mdc) de
dois inteiros a e b se possuir as seguintes propriedades:
i) d é um divisor comum de a e de b, e
ii) d é divisı́vel por todo divisor comum de a e b.
Exemplo
O máximo divisor comum de 12 e 18 é 6.
A condição (ii) acima pode ser reenunciada como segue:
ii0 ) Se c é um divisor comum de a e b, então c|d.
Em particular, se d e d 0 são dois mdc de um mesmo par de
números, então d | d 0 e d 0 | d, o que, juntamente com as
condições d ≥ 0 e d 0 ≥ 0 implicam d = d 0 .
Ou seja, quando existe, o mdc de dois números é único.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 4/19
Veremos mais adiante que sempre existe o mdc de dois números
inteiros a e b e o denotaremos por (a, b).
Como o mdc de a e b não depende da ordem em que a e b são
tomados, temos que
(a, b) = (b, a).
Em alguns casos particulares, é facil verificar a existência do mdc.
Por exemplo, se a é um número inteiro tem-se claramente que
(0, a) = |a|,
(1, a) = 1
e
(a, a) = |a|.
Mais geralmente, para todo b ∈ Z, temos que
a|b ⇐⇒ (a, b) = |a|.
(1)
Observação
Sejam a, b ∈ Z. Tem-se que (a, b) = 0 ⇐⇒ a = b = 0.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 5/19
A demonstração da existência do mdc de qualquer par de números
inteiros, não ambos nulos, é bem mais sutil.
Se d > 0 é um mdc de a e b não nulos e c é um divisor comum
desses números, então c divide d e, consequentemente, |c| divide
d. Portanto, c 6 |c| 6 d.
Isto mostra que, efetivamente, quando existe, o máximo divisor
comum de dois números, não ambos nulos, é o maior dentre todos
os divisores comuns desses números.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 6/19
Poderı́amos, como se faz usualmente no Ensino Fundamental,
definir o máximo divisor comum de dois números a e b, não ambos
nulos, como o maior elemento do conjunto de todos os divisores
comuns desses números, o que de imediato garantiria a sua
existência.
De qualquer modo, seria necessário provar a propriedade (ii) da
definição de mdc, pois é ela que possibilita provar os resultados
subsequentes, e não o fato do mdc ser o maior dos divisores
comuns.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 7/19
Observe que dados a, b ∈ Z, se existir o mdc (a, b) de a e b, então
(a, b) = (−a, b) = (a, −b) = (−a, −b).
Assim, para efeito do cálculo do mdc de dois números, podemos
supô-los não negativos.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 8/19
Resultado fundamental para o Algoritmo de Euclides
Para provar a existência do máximo divisor comum de dois inteiros
não negativos, Euclides utiliza, essencialmente, o resultado abaixo.
Lema
Sejam a, b, n ∈ Z. Se existe (a, b − na), então (a, b) existe e
(a, b) = (a, b − na).
O Lema é efetivo para calcular mdc, conforme veremos nos
exemplos a seguir, e será fundamental para estabelecermos o
algoritmo de Euclides, que permitirá, com muita eficiência, calcular
o mdc de dois números naturais quaisquer.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 9/19
Exercı́cio
Vamos determinar o máximo divisor comum de 96525 e 90, usando
o Lema.
Solução
(90, 96 525)
PROFMAT - SBM
=
=
=
=
=
=
=
=
(90, 96 525 − 90 × 1 000) = (90, 96 525 − 90 000)
(90, 6 525)
(90, 6 525 − 70 × 90) = (90, 6 525 − 6 300)
(90, 225)
(90, 225 − 2 × 90) = (90, 225 − 180)
(90, 45)
(45, 90)
45.
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 10/19
Exemplo 1
Dados a ∈ Z com a 6= 1 e m ∈ N, temos que
m
a −1
,
a
−
1
= (a − 1, m).
a−1
Solução
A igualdade acima é trivialmente verificada se m = 1. Suponhamos
que m > 2. Chamando de d o primeiro membro da igualdade,
temos que
d = (am−1 + am−2 + · · · + a + 1, a − 1) =
(am−1 − 1) + (am−2 − 1) + · · · + (a − 1) + m, a − 1 .
Como
a − 1|(am−1 − 1) + (am−2 − 1) + · · · + (a − 1),
segue-se, para algum n ∈ N, que
(am−1 − 1) + (am−2 − 1) + · · · + (a − 1) = n(a − 1).
Portanto, pelo Lema anterior tem-se que
d = (n(a − 1) + m, a − 1) = (a − 1, n(a − 1) + m) = (a − 1, m).
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 11/19
Exemplo 2
Determinemos os valores de a ∈ Z e n ∈ N para os quais a + 1
divide a2n + 1.
Solução
Note inicialmente que
a + 1|a2n + 1 ⇐⇒ (a + 1, a2n + 1) = |a + 1|.
Como a2n + 1 = (a2n − 1) + 2, e a + 1|a2n − 1, segue-se do Lema
anterior, para todo n, que
(a + 1, a2n + 1) = (a + 1, (a2n − 1) + 2) = (a + 1, 2).
Portanto, a + 1|a2n + 1, para algum n ∈ N, se, e somente se,
|a + 1| = (a + 1, 2), o que ocorre se, e somente se, a = 0, a = 1,
a = −2 ou a = −3 e n qualquer.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 12/19
Exemplo 3
Vamos, neste exemplo, determinar os valores de a ∈ Z e n ∈ N
para os quais a + 1 divide a2n+1 − 1.
Solução
Note que
(a + 1, a2n+1 − 1) = (a + 1, a(a2n − 1) + a − 1) = (a + 1, a − 1).
Portanto, a + 1|a2n+1 − 1, para algum n ∈ N, se, e somente se,
|a +1| = (a +1, a2n+1 −1) = (a +1, a −1) = (a +1, −2) = (a +1, 2)
o que ocorre se, e somente se, a = 0, a = 1, a = −2 ou a = −3 e
n qualquer.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 13/19
Algoritmo de Euclides
Prova construtiva da existência do mdc dada por Euclides.
Dados a, b ∈ N, podemos supor a 6 b. Se a = 1 ou a = b, ou
ainda a|b, já vimos que (a, b) = a. Suponhamos, então, que
1 < a < b e que a 6 | b. Logo, pela divisão euclidiana, podemos
escrever
b = aq1 + r1 , com 0 < r1 < a.
Temos duas possibilidades:
a) r1 |a, e, em tal caso, por (1) e pelo Lema,
r1 = (a, r1 ) = (a, b − q1 a) = (a, b),
e termina o algoritmo, ou
b) r1 6 | a, e, em tal caso, podemos efetuar a divisão de a por r1 ,
obtendo
a = r1 q2 + r2 , com 0 < r2 < r1 .
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 14/19
Novamente, temos duas possibilidades:
a0 ) r2 |r1 , e, em tal caso, novamente, por (1) e pelo Lema de
Euclides,
r2 = (r1 , r2 ) = (r1 , a − q2 r1 ) = (r1 , a) = (b − q1 a, a) = (b, a) = (a, b),
e paramos, pois termina o algoritmo, ou
b0 ) r2 6 | r1 , e, em tal caso, podemos efetuar a divisão de r1 por r2 ,
obtendo
r1 = r2 q3 + r3 , com 0 < r3 < r2 .
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 15/19
Este procedimento não pode continuar indefinidamente, pois
terı́amos uma sequência de números naturais
a > r1 > r2 > · · · ,
que não possui menor elemento, o que não é possı́vel pela
Propriedade da Boa Ordenação.
Logo, para algum n, temos que rn |rn−1 , o que implica que
(a, b) = rn .
O algoritmo acima pode ser sintetizado e realizado na prática,
como mostramos a seguir.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 16/19
Inicialmente, efetuamos a divisão
b = aq1 + r1
e colocamos os números envolvidos
no diagrama ao lado.
Continuamos efetuando a divisão
a = r1 q2 + r2
e colocamos os números envolvidos
no diagrama ao lado.
b
r1
b
r1
q1
a
q1 q2
a r1
r2
Prosseguindo, enquanto for possı́vel (até que para algum n > 2
rn | rn−1 ), teremos
b
r1
PROFMAT - SBM
q1 q2 q3 · · ·
a r1 r2 · · ·
r2 r3 r4 · · ·
qn−1 qn
qn+1
rn−2 rn−1 rn = (a, b)
rn
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 17/19
Exemplo 4
Calculemos o mdc de 372 e 162:
2
3 2 1 2
372 162 48 18 12 6
48 18 12 6
Observe que, no exemplo acima, o Algoritmo de Euclides nos
fornece:
6 = 18 − 1 · 12
12 = 48 − 2 · 18
18 = 162 − 3 · 48
48 = 372 − 2 · 162
Donde se segue que
6 = 18 − 1 · 12 = 18 − 1 · (48 − 2 · 18) = 3 · 18 − 48 =
3 · (162 − 3 · 48) − 48 = 3 · 162 − 10 · 48 =
3 · 162 − 10 · (372 − 2 · 162) = 23 · 162 − 10 · 372.
Temos, então, que
(372, 162) = 6 = 23 · 162 + (−10) · 372.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 18/19
Note que conseguimos, através do uso do Algoritmo de Euclides de
trás para frente, escrever 6 = (372, 162) como múltiplo de 162
mais um múltiplo de 372.
O Algoritmo de Euclides nos fornece, portanto, um meio prático de
escrever o mdc de dois números como soma de dois múltiplos dos
números em questão. Esta é uma propriedade geral do mdc que
redemonstraremos com todo rigor na próxima seção.
Quando utilizarmos o Algoritmo de Euclides para expressar (a, b)
na forma ma + nb, com m, n ∈ Z, nos referiremos a ele como
Algoritmo de Euclides Estendido.
PROFMAT - SBM
Aritmética - Unidade 5 - Máximo Divisor Comum
slide 19/19