aula02
5 pág.

aula02


DisciplinaEstruturas Mat P/ Computação4 materiais131 seguidores
Pré-visualização2 páginas
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 \u2019pai da geometria\u2019. 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.
\ufffd
Exemplo 1:
\u2022 Como 3|12 e 12|48, então 3|48.
\u2022 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).
\ufffd
Teorema 1: Propriedades da Divisão
\u2022 n|n, para todo n \u2208 Z\u2217.
\u2022 Se d|n, então ad|an para qualquer a \u2208 Z\u2217.
\u2022 Se ad|an e a 6= 0, então d|n.
\u2022 1|n para todo n \u2208 Z.
1
\u2022 n|0 para todo n \u2208 Z.
\u2022 Se d|n e n 6= 0, então |d| \u2264 |n|.
\u2022 Se d|n e n|d, então |d| = |n|.
\u2022 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.
\ufffd
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 \u2019Princípio de
Arquimedes\u2019): 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 \u2264 a < (q + 1)b
e para b < 0,
qb \u2264 a < (q \u2212 1)b.
Exemplo 2:
\u2022 Se a = 17 e b = 2, então fazendo q = 8, temos 8× 2 \u2264 17 < 9× 2.
\u2022 Se a = 8 e b = \u22121, então fazendo q =, temos (\u22128)× (\u22121) \u2264 8 < (\u22129)× (\u22121).
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 \u2264 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 \u2264 a < (q + 1)b.
Com isso, temos que 0 \u2264 a \u2212 qb e a \u2212 qb < b. Desta forma, definindo o número r = a \u2212 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 \u2264 r1 < b. Disto temos
qb+ r\u2212 (q1b+ r1) = 0, ou seja, b(q\u2212 q1) = r1\u2212 r. Logo, b|(r1\u2212 r). Como r1 < b e r < b, temos que |r1\u2212 r| < b,
e, portanto, como b|(r1 \u2212 r) devemos ter r1 \u2212 r = 0. Portanto, r1 = r e consequentemente q1 = q.
\ufffd
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 \u2264 r < |b|.
Exemplo 3:
\u2022 Se a = 4 e b = \u221215, então \u221215 = 4(\u22124) + 1, com q = \u22124 e r = 1.
\u2022 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 \u2208 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\u2212 qc,
ou seja, r = a\u2212 q(n0a+m0b), e portanto, r = (1\u2212 qn0)a+ (\u2212qm0)b. Desta forma, mostramos que r \u2208 B, pois
(1\u2212 qn0) e (\u2212qm0) 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 \u2264 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.
\ufffd
Temos como conseqüência deste teorema alguns resultados importantes.
Proposição 3:
Dados a, b \u2208 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).
\ufffd
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.
\ufffd
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\u2212 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).
\ufffd
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 \u2264 rj+2 < rj+1, para j = 0, 1, 2, · ·