Estruturas Matemáticas para Computação - Divisibilidade

Prévia do material em texto

Estruturas Matemáticas para Computação
Divisibilidade - Aula 02
Vinicius Rispoli
29 de outubro de 2012
1 Divisibilidade
A noção de divisibilidade entre números naturais já era traçada na antiguidade, essa noção é tão antiga quanto
Euclides de Alexandria (300 a.C.), conhecido também como o ’pai da geometria’. Euclides é o autor do
livro Os Elementos, o segundo livro mais reproduzido na história, só perde para a bíblia. Os Elementos de
Euclides trazem a fundamentação da geometrica plana euclidiana que conhecemos hoje e nesta época as oper-
ações como a divisibilidade, por exemplo, eram executadas de forma geométrica. No livro VII dos Elementos,
Euclides traz o seu famoso algoritmo de divisão, que é utilizado por nós até hoje.
Definição 1: Divisibilidade
Se a e b são número inteiros, dizemos que a divide b, denotando por a|b, se existir um inteiro c tal que b = ac.
Se a não divide b escrevemos a - b.
Proposição 1:
Se a, b e c são inteiros, e temos que a|b e b|c, então a|c.
Demonstração. Como a|b e b|c, então existem números inteiros k1 e k2 tal que b = ak1 e c = bk2. Substituindo
o valor de b na equação c = bk2 teremos c = ak1k2. O que implica que a|c.
�
Exemplo 1:
• Como 3|12 e 12|48, então 3|48.
• Como não existe um número inteiro c satisfazendo 15 = 4 · c, então 4 - 15.
Existem outras propriedades importantes da divisão que serão colocadas como proposição daqui em diante.
Proposição 2:
Sejam a, b, c,m e n números inteiros tais que c|a e c|b, então c|(ma+mb).
Demonstração. Como c|a e c|b, então existem k1 e k2 números inteiros tais que a = k1c e b = k2c.
Multiplicando, respectivamente, a primeira e a segunda equação por m e n, temos ma = mk1c e nb = nk2c.
Somando-se membro a membro as duas últimas equações obtemos ma+ nb = (mk1 + nk2)c, o que nos diz que
c|(ma+ nb).
�
Teorema 1: Propriedades da Divisão
• n|n, para todo n ∈ Z∗.
• Se d|n, então ad|an para qualquer a ∈ Z∗.
• Se ad|an e a 6= 0, então d|n.
• 1|n para todo n ∈ Z.
1
• n|0 para todo n ∈ Z.
• Se d|n e n 6= 0, então |d| ≤ |n|.
• Se d|n e n|d, então |d| = |n|.
• Se d|n e d 6= 0, então (n/d)|n.
Demonstração. As demonstrações são bem simples e serão deixadas como exercício.
�
Antes de introduzirmos o Algoritmo da Divisão de Euclides, enuciamos o chamado Teorema de
Eudoxius (este teorema costuma ser atribuído erroneamente a Arquimedes e chamado de ’Princípio de
Arquimedes’): dados a e b número inteiros com b 6= 0, então a é um múltiplo de b ou se encontra entre dois
múltiplos consecutivos de b, isto é, correspondendo a cada par de inteiros a e b 6= 0 existe um inteiro q tal que,
para b > 0,
qb ≤ a < (q + 1)b
e para b < 0,
qb ≤ a < (q − 1)b.
Exemplo 2:
• Se a = 17 e b = 2, então fazendo q = 8, temos 8× 2 ≤ 17 < 9× 2.
• Se a = 8 e b = −1, então fazendo q =, temos (−8)× (−1) ≤ 8 < (−9)× (−1).
Teorema 2: Algoritmo da Divisão
Dados dois números inteiros a e b, b > 0, existe um único par de números inteiros q e r tais que
a = qb+ r,
sendo 0 ≤ r < b. O número q é chamado de quociente e r o resto da divisão de a por b.
Demonstração. Pelo Teorema de Eudoxius, como b > 0, sabemos que existe q satisfazendo:
qb ≤ a < (q + 1)b.
Com isso, temos que 0 ≤ a − qb e a − qb < b. Desta forma, definindo o número r = a − qb garantimos a
existência de q e r. Falta apenas mostrar a unicidade. E para tal considere q1 e r1 outro par de quociente
e resto, respectivamente, que satisfaz os números a e b. Isto é, a = q1b + r1 com 0 ≤ r1 < b. Disto temos
qb+ r− (q1b+ r1) = 0, ou seja, b(q− q1) = r1− r. Logo, b|(r1− r). Como r1 < b e r < b, temos que |r1− r| < b,
e, portanto, como b|(r1 − r) devemos ter r1 − r = 0. Portanto, r1 = r e consequentemente q1 = q.
�
Embora no enunciado do teorema foi colocada a restrição b > 0, isto não é realmente necessário. Esta
restrição foi colocada apenas para facilitar a demonstração. O teorema na sua forma mais geral pode ser escrito
como: dados dois números inteiros a e b, b 6= 0, existe um único par de inteiros q e r tais que a = qb + r com
0 ≤ r < |b|.
Exemplo 3:
• Se a = 4 e b = −15, então −15 = 4(−4) + 1, com q = −4 e r = 1.
• Se a = 19 e b = 13, então 13 = 0.19 + 13 com q = 0 e r = 13.
2 O Máximo Divisor Comum
O Máximo Divisor Comum, ou mdc, de dois números inteiros a e b (a ou b diferente de zero), denotado por
(a, b), é o maior número inteiro que divide a e b.
Teorema 3:
Seja d o máximo divisor comum de a e b, então existem dois números inteiros n0 em0 tais que d = n0a+m0b.
Demonstração. Seja B o conjunto de todas as combinações lineares {na+mb} sendo m,n ∈ Z. Escolha m0
e n0 tal que o número c = n0a+m0b seja o menor inteiro positivo do conjunto B. Suponha que o número c - a,
2
então pelo algoritmo da divisão de Euclides existem q e r tal que a = qc+ r com 0 < r < c. Assim, r = a− qc,
ou seja, r = a− q(n0a+m0b), e portanto, r = (1− qn0)a+ (−qm0)b. Desta forma, mostramos que r ∈ B, pois
(1− qn0) e (−qm0) são números inteiros. Como r é positivo e menor que c, temos uma contradição, pois c é o
menor inteiro positivo que pertence ao conjunto B. Portanto, c|a e de forma totalmente análoga se mostra que
c|b.
Considere agora d = (a, b), então existem números inteiros k1 e k2 tais que a = k1d e b = k2d. Como
c = n0a +m0b, então podemos reescrever essa equação como sendo c = (n0k1 +m0k2), o que implica que d|c.
Consequentemente, temos que d ≤ c. Como d é o máximo divisor comum entre a e b, e c é o menor divisor
pertencente no conjunto B, então d = c. Portanto, d = n0a+m0b.
�
Temos como conseqüência deste teorema alguns resultados importantes.
Proposição 3:
Dados a, b ∈ Z, com a ou b não nulo, então para todo inteiro positivo t, temos (ta, tb) = t(a, b).
Demonstração. Pelo teorema anterior, sabemos que existem m e n inteiros, tal que (ta, tb) é o menor valor
da combinação linear mta + ntb. Ou seja, (ta, tb) = t(ma + nb). Suponha que ma + nb 6= (a, b), isto é, m
e n não minimizam a combinação linear, então existem m0 e n0 tais que m0a + n0b = (a, b) < ma + nb. O
que significa que o número (ta, tb) não é o mínimo da combinação linear mta + ntb. Isto é uma contradição.
Portanto, ma+ nb = (a, b) e consequentemente, (ta, tb) = t(a, b).
�
Definição 2:
Dois números inteiros a e b são ditos relativamente primos quando (a, b) = 1.
Teorema 4:
Sejam a, b, c números inteiros tais que a|bc e a e b são relativamente primos, então a|c.
Demonstração. Como a e b são relativamente primos, então (a, b) = 1. Além disso, existem dois números
inteiros m e n tais que ma+ nb = 1. Multiplicando esta última equação por c, temos m(ac) +m(cb) = c. Como
a|ac e por hipótese a|bc, então como a divide a soma, então a|c.
�
Teorema 5:
Se a e b são números inteiros e a = qb+ r onde q e r são inteiros, então (a, b) = (b, r).
Demonstração. Da relação a = qb+ r podemos concluir que todo divisor de b e r é também um divisor de
a. Esta mesma relação reescrita na forma r = a− qb indica que todo divisor de a e b também é um divisor de
r. Logo o conjunto dos divisores comuns de a e b também é o conjunto dos divisores comuns de b e r, o que
garante que (a, b) = (b, r).
�
Tendo em vista o grande resultado obtido no Teorema 5, iremos nos utilizar dele para obtermos o máximo
divisor comum de dois números inteiros. Considere a = 1126 e b = 522, a divisão de a por b resulta em
1126 = 2× 522 + 82,
em que q = 2 e r = 82. Do resultado do teorema anterior, sabemos que (1126, 522) = (522, 82). Então fazendo
a divisão de 522 por 82, temos
522 = 6× 82 + 30,
em que q = 6 e r = 30. Novamente, como resultado do Teorema 5, temos que (522, 82) = (82, 30) e
consequentemente (1126, 522) = (82, 30). Assim, repetindo este procedimento obtemos
82 = 2× 30 + 22
30 = 1× 22 + 8
22 = 2× 8 + 6
8 = 1× 6 + 2
6 = 3× 2 + 0.
3
Dá ultima equação obtemos que (6, 2) = 2 e pelo Teorema 5 podemos concluir que (1126, 522) = (6, 2) = 2.
Teorema 6: O Algoritmo de Euclides
Sejam r0 = a e r1 = b inteiros não-negativos com b 6= 0. Se o algoritmo da divisão for aplicado sucessivamente
para se obter
rj = qj+1rj+1 + rj+2,
com 0 ≤ rj+2 < rj+1, para j = 0, 1, 2, · ·· , n− 1 e rn+1 = 0 então (a, b) = rn, o último resto não nulo.
Demonstração. Utilizando a ideia do exemplo anterior temos já um esboço de como será a nossa demon-
stração. Inicialmente, faça a divisão de r0 = a por r1 = b, obtendo r0 = q1r1 + r2, em seguinda dividimos r1
por r2, obtendo r1 = q2r2 + r3 e assim, sucessivamente, até a obtenção do resto rn+1 = 0. Como a cada passo
o resto é sempre menor do que o do passo anterior, e estamos lidando com números inteiros positivos, é claro
que após um número finito de aplicações teremos o resto nulo
Como conseqüência das divisões sucessivas temos a seqüência de equações:
r0 = q1r1 + r2, 0 < r2 < r1
r1 = q2r2 + r3, 0 < r3 < r2
...
rn−2 = qn−1rn−1 + rn, 0 < rn < rn−1
rn−1 = qnrn + 0.
A última equação nos diz que, pelo Teorema 5, que o máximo divisor comum de rn e rn−1 é rn. A penúltima,
que este número é igual a (rn−1, rn−2) e, prosseguindo desta maneira teremos, por repetidas aplicações do
Teorema 5, a seqüência:
rn = (rn−1, rn) = · · · = (r1, r2) = (r0, r1) = (a, b).
Portanto, o máximo divisor comum de a e b é o último resto não nulo da seqüência de divisões descrita.
�
3 Exercícios
1. Dado que (a, b) = g, prove que se c é um divisor comum dos números inteiros a e b, sem que sejam os dois
nulos, então (a/c, b/c) = g/c.
2. Mostre que para cada c ∈ Z, e quaisquer a, b ∈ Z, sem que sejam os dois nulos, (a, b) = (b, a) = (a,−b) =
(a, b+ ac).
3. Mostre que c|a e c|b se, e somente se, c|(a, b).
4. Considere a, b, c ∈ Z∗, mostre que o máximo divisor comum destes números pode ser escrito na forma
am+ bn+ cp para alguns m,n, p ∈ Z.
5. Determine o máximo divisor comum para os pares
(a) a = 22, b = 55.
(b) a = 15, b = 113.
(c) a = 542, b = 234
(d) a = 9652 e b = 252
6. Utilize o algorítmo de Euclides para escrever (1485, 1745) na forma 1485u+ 1745v.
7. (Desafio) A seqüência recursiva Fn = Fn−1 + Fn−2, n > 2, F1 = 1 e F2 = 1 é conhecida como seqüência
de Fibonacci. Mostre que se m,n ∈ N com n|m, então Fn|Fm, sendo Fk o k-ésimo número de Fibonacci.
Além disto, use esse resultado para provar que para qualquer m,n ∈ N, (Fn, Fm) = F(n,m). Obs.: Sendo
g =
1 +
√
5
2
e g =
1−√5
2
a razão áurea, mostre que o n-ésimo número de Fibonacci Fn pode ser escrito
como sendo Fn =
gn − gn√
5
. Essa representação dos números de Fibonacci é conhecida como Fórmula de
Binet.
4
4 Referências
• Mollin, R. A., Fundamental Number Theory With Applications. Second Edition. Chapman &
Hall. Calgary, Canada, 2008.
• Santos, J. P. O., Introdução à Teoria dos Números. Terceira Edição. Coleção Matemática Univer-
sitária. IMPA, Rio de Janeiro, Brasil, 2011.
5