4_aula_divisibilidade

Prévia do material em texto

Divisibilidade
Haniel Barbosa
IMD0013 − Elementos de Matemática para Computação
BTI − Tecnologia da Informação — Bacharelado
IMD − Instituto Metrópole Digital
2013
Haniel Barbosa Divisibilidade
Sumário
Haniel Barbosa Divisibilidade
Introdução
Dados dois inteiros, você pode somá-los, subtraí-los ou
multiplicá-los que o resultado será sempre um inteiro.
O mesmo não se aplica à divisão.
Tem-se um valor inteiro em 12/4, mas não em 13/5, que requer
a saída deste domínio.
Para se continuar trabalhando com inteiros a divisão deve
resultar em dois valores — quociente e resto.
Assim, 13/5 nos daria como resultado o quociente 2 e o resto 3.
13 = 5 · 2 + 3
Haniel Barbosa Divisibilidade
Introdução
Dados dois inteiros, você pode somá-los, subtraí-los ou
multiplicá-los que o resultado será sempre um inteiro.
O mesmo não se aplica à divisão.
Tem-se um valor inteiro em 12/4, mas não em 13/5, que requer
a saída deste domínio.
Para se continuar trabalhando com inteiros a divisão deve
resultar em dois valores — quociente e resto.
Assim, 13/5 nos daria como resultado o quociente 2 e o resto 3.
13 = 5 · 2 + 320
13
-0
1-
09
Divisibilidade
Introdução
1. Teste
Teorema da Divisão
Teorema da Divisão
Dados dois inteiros a e b, sendo b > 0, existem dois inteiros
únicos, q e r, tal que a = q · b + r e 0 ≤ r < b
Haniel Barbosa Divisibilidade
Teorema da Divisão
Teorema da Divisão
Dados dois inteiros a e b, sendo b > 0, existem dois inteiros
únicos, q e r, tal que a = q · b + r e 0 ≤ r < b
20
13
-0
1-
09
Divisibilidade
Divisão
Teorema da Divisão
Prova em duas partes: primeiro que a = q · b + r e 0 ≤ r < b, depois que
q, r são, de fato, únicos.O resultado é conhecido. O foco é mostrar a
formalização deste, provando sua validade para qualquer par de inteiros que
satisfaçam a premissa.
Exemplos
Sejam a = 34 e b = 13, teríamos
34 = 2 · 13 + 8
Sendo q = 2 e r = 8, sendo 0 ≤ 8 < 13.
Sejam a = −45 e b = 7, teríamos
−45 = −7 · 7 + 4
Sendo q = −7 e r = 4, sendo 0 ≤ 4 < 7.
Haniel Barbosa Divisibilidade
Exemplos
Sejam a = 34 e b = 13, teríamos
34 = 2 · 13 + 8
Sendo q = 2 e r = 8, sendo 0 ≤ 8 < 13.
Sejam a = −45 e b = 7, teríamos
−45 = −7 · 7 + 4
Sendo q = −7 e r = 4, sendo 0 ≤ 4 < 7.
20
13
-0
1-
09
Divisibilidade
Divisão
Exemplos
Comentar sobre o resto ser um número natural que podemos obter
subtraindo de a múltiplos de b.
Div e Mod
Baseado no Teorema da Divisão definimos duas operações, div e
mod.
Assim, temos:
Div e Mod
Sejam a e b inteiros, sendo b > 0, pelo Teorema da Divisão,
há um único par de números q e r tal que a = q · b + r e
0 ≤ r < b. As operações div e mod são definidas como
a div b = q a mod b = r
Haniel Barbosa Divisibilidade
Div e Mod
Baseado no Teorema da Divisão definimos duas operações, div e
mod.
Assim, temos:
Div e Mod
Sejam a e b inteiros, sendo b > 0, pelo Teorema da Divisão,
há um único par de números q e r tal que a = q · b + r e
0 ≤ r < b. As operações div e mod são definidas como
a div b = q a mod b = r20
13
-0
1-
09
Divisibilidade
Divisão
Div e Mod
Recuperar exemplos anteriores, que podem estar no quadro, para mostrar o
uso de div e mod.
Teorema da Divisão
Teorema Geral da Divisão
Dados dois inteiros a e b, sendo b 6= 0, existem dois inteiros
únicos, q e r, tal que a = q · b + r e 0 ≤ r < |b|
Haniel Barbosa Divisibilidade
Teorema da Divisão
Teorema Geral da Divisão
Dados dois inteiros a e b, sendo b 6= 0, existem dois inteiros
únicos, q e r, tal que a = q · b + r e 0 ≤ r < |b|
20
13
-0
1-
09
Divisibilidade
Divisão
Teorema da Divisão
• Estende o anterior ao diminuir a restrição do divisor para qualquer
valor diferente de zero. Assim, o valor absoluto deste torna-se o
delimitador do resto.
• Talvez seja melhor deixar a demonstração deste para os exercícios
teóricos, se não sua própria menção.
Divisibilidade
Utilizando o Teorema da Divisão somos capazes de definir a
propriedade de divisibilidade entre inteiros, um dos conceitos
centrais em Teoria dos Números.
Propriedade que caracteriza o fato de 12 ser divisível por 4 mas
não por 5.
Assim, definimos:
Divisibilidade
Se a divisão de a por b produz um resto tal que r = 0, então
dizemos que a é divisível por b. Portanto, a é divisível por
b se e somente se, sendo b 6= 0, existe um inteiro q tal que
a = q · b.
A notação utilizada é b | a, significando “a é divisível por b”.
Haniel Barbosa Divisibilidade
Divisibilidade
Utilizando o Teorema da Divisão somos capazes de definir a
propriedade de divisibilidade entre inteiros, um dos conceitos
centrais em Teoria dos Números.
Propriedade que caracteriza o fato de 12 ser divisível por 4 mas
não por 5.
Assim, definimos:
Divisibilidade
Se a divisão de a por b produz um resto tal que r = 0, então
dizemos que a é divisível por b. Portanto, a é divisível por
b se e somente se, sendo b 6= 0, existe um inteiro q tal que
a = q · b.
A notação utilizada é b | a, significando “a é divisível por b”.
20
13
-0
1-
09
Divisibilidade
Divisibilidade
Divisibilidade
• Deixar claro que divisibilidade é uma propriedade, uma relação entre
dois inteiros (a | b), sendo ela verdadeira ou falsa. Portanto
completamente diferente da operação de divisão (a/b), que resulta em
um número racional, uma notação para estes.
• Dependendo do andamento da aula falar sobre números primos? Um
número primo é aquele que, sendo maior do que 1, satisfaz a
propriedade de divisibilidade somente quando tem 1 ou ele mesmo
como divisor.
• Citar que b | a lê-se também como “b é divisor de a.
• Citar que a negação da propriedade é representado por b - a.
Exemplos
Em que casos a propriedade de divisibilidade é satisfeita?
1. 0 | 7
2. 9 | 0
3. 0 | 0
4. 1 | 1
5. 7 | 44
6. 7 | (−42)
7. (−7) | 49
8. (−7) | (−56)
9. 2708 | 569401
10. 2n | n2, sendo n ∈ Z
11. 1 | n, sendo n ∈ Z
12. n | n, sendo n ∈ Z
Haniel Barbosa Divisibilidade
Exemplos
Em que casos a propriedade de divisibilidade é satisfeita?
1. 0 | 7
2. 9 | 0
3. 0 | 0
4. 1 | 1
5. 7 | 44
6. 7 | (−42)
7. (−7) | 49
8. (−7) | (−56)
9. 2708 | 569401
10. 2n | n2, sendo n ∈ Z
11. 1 | n, sendo n ∈ Z
12. n | n, sendo n ∈ Z
20
13
-0
1-
09
Divisibilidade
Divisibilidade
Exemplos
1. Não pode ter zero como divisor (definição).
2. 0 é dividido por qualquer inteiro.
3. Não pode ter zero como divisor.
4. Usar para mostrar que não é preciso calcular, basta atentar ao fato de
que um par não divide um ímpar.
5. Pode ser mostrado com indução sobre o valor de n.
6. 1 divide qualquer inteiro.
7. Sendo n qualquer inteiro pode ele também ser zero.
Propriedades de divisibilidade
Propriedades
Sejam a, b, c e d inteiros, temos:
1. a | 0, a | a
2. a | 1 sse |a| = 1
3. Se a | b e c | d, então a · c | b · d, sendo c 6= 0
4. Se a | b e b | c, então a | c, sendo b 6= 0
5. a | b e b | a sse a = |b|
6. Se a | b e b 6= 0, então |a| ≤ |b|
7. Se a | b e b | c, então a | (b · x + c · y), para quaisquer
inteiros x, y
Haniel Barbosa Divisibilidade
Propriedades de divisibilidade
Propriedades
Sejam a, b, c e d inteiros, temos:
1. a | 0, a | a
2. a | 1 sse |a| = 1
3. Se a | b e c | d, então a · c | b · d, sendo c 6= 0
4. Se a | b e b | c, então a | c, sendo b 6= 0
5. a | b e b | a sse a = |b|
6. Se a | b e b 6= 0, então |a| ≤ |b|
7. Se a | b e b | c, então a | (b · x + c · y), para quaisquer
inteiros x, y
20
13
-0
1-
09
Divisibilidade
Divisibilidade
Propriedades de divisibilidade
Provar uma ou duas. A 1 recupera casos dos exemplos anteriores. A 4 puxa
transitividade, etc.
Perguntas?
Haniel Barbosa Divisibilidade
	Divisão
	Divisibilidade