Slides Teoria dos Números Parte II UNIP

Prévia do material em texto

Unidade II
TEORIA DOS NÚMEROS
Prof. Gastón A. C. Henriquez
Os diferentes tipos de 
demonstração
 Método das ciências naturais: “indução 
empírica”.
Na matemática:
1. Para provar que uma afirmação é falsa, 
basta encontrar um contraexemplo.basta encontrar um contraexemplo.
2. Para provar que uma afirmação é 
verdadeira, é necessário verificá-la para 
todas as situações em que ela se aplica.
Validade de um teorema matemático
 Portanto, a validade de um teorema 
matemático se estabelece de forma 
diferente. Uma afirmação ser verdadeira 
em um grande número de situações 
particulares não permite afirmar que ela 
seja válida A indução matemática é umseja válida. A indução matemática é um 
princípio postulado por Peano, que 
resolve tal problema para os números 
naturais, ou seja, se uma propriedade é 
verificada para o zero e sempre verificada 
para um número natural n, também podepara um número natural n, também pode 
ser verificada para seu sucessor n+1; 
então, a propriedade é verificada para 
todos os números naturais. 
Princípio da indução completa
 Seja p um número inteiro dado, 
suponhamos que seja feita uma 
afirmação a respeito de cada número 
inteiro n ≥ p, de forma que:
1. A afirmação seja válida para n = p.
2. Se a afirmação é válida para algum 
inteiro n = k, então também é válida para 
n = k + 1.
 Então, a afirmação é válida para todo 
inteiro n ≥ p.inteiro n ≥ p.
Exemplo
Observe que: 
 1 = 12
 1 + 3 = 4 = 22
 1 + 3 + 5 = 9 = 32
 1 + 3 + 5 + 7 = 16 = 42
Vamos demonstrar que a soma dos n
primeiros números ímpares positivos é 
igual a n2.
Continuação do exemplo
 Lembremos que um número ímpar 
positivo pode ser escrito na forma 2n – 1.
Sendo assim: 
 o primeiro ímpar positivo é 1 = 2.1 – 1
 o segundo ímpar positivo é 3 = 2 2 1 o segundo ímpar positivo é 3 = 2.2 – 1
 o terceiro ímpar positivo é 5 = 2.3 – 1
 e assim por diante.
Então, queremos demonstrar que:
 1 + 3 + 5 + + (2n 1) = n2 1 + 3 + 5 + ... + (2n – 1) = n2.
Demonstração
1. A afirmação é válida para n = 1, pois 
1 = 12.
2. Vamos mostrar que, se a afirmação for 
válida para n = k, então também será 
válida para n = k+1.
De fato, se 1+3+5+...+ (2k – 1) = k2, então:
1+3+5+ ... +(2k–1)+[2(k+1)-1] = k2+ [2(k+1)-1] 
1+3+5+ ... +(2k–1)+[2(k+1)-1] = k2+ 2k+2-1 
1+3+5+ ... +(2k–1)+[2(k+1)-1] = k2+ 2k+1 
1+3+5+ ... +(2k–1)+[2(k+1)-1] = (k+1)2
c.q.d.
Princípio forte da indução
Seja m um número natural e A o conjunto 
de todos os naturais maiores ou iguais a m, 
ou seja, A = {m, m+1, m+2, ...}, vamos 
considerar uma propriedade P(n) sobre 
números naturais tal que:
I. P(m) é verdadeira.
II. Se P(r) é verdadeira para todo r tal que 
m ≤ r ≤ k, então P(k+1) é verdadeira.
 Então, P(n) é verdadeira para todo n
pertencente ao conjunto A.pertencente ao conjunto A.
Cuidado!
 Lembrete: é preciso ter cuidado com o 
princípio de indução matemática, que 
exige que se provem duas proposições 
separadamente.
Exemplo
Seja a sequência (a1, a2, a3, ...) definida da 
seguinte forma:
 a1 = 1, a2 = 3, an = an-1 + an-2, para n ≥ 3, ou 
seja, a sequência é (1, 3, 4, 7, 11, 18, ...), 
queremos demonstrar que, para cada n, 
vale a desigualdade: an < (7/4)n
Demonstração
1. Para n = 1, temos a1 = 1 < (7/4)1
2. Para n = 2, temos a2 = 3 < (7/4)2
3. Seja k ≥ 2, vamos supor que a afirmação 
seja válida para todo inteiro positivo 
menor ou igual a k. Queremos provarmenor ou igual a k. Queremos provar 
que ak+1 < (7/4)k+1.
Continuação da demonstração (I)
 Da hipótese, como supusemos a 
afirmação válida para todo inteiro 
positivo menor ou igual a k, temos que:
1. ak< (7/4)k
2. ak 1<(7/4)k-12. ak-1 (7/4)
Logo, ak + ak-1 < (7/4)k + (7/4)k+1
Pela definição da sequência: 
ak+1 = ak + ak-1 .
Continuação da demonstração (II)
 Portanto, ak+1< (7/4)k + (7/4)k-1 = 
= (7/4)k-1((7/4) +1) = (7/4)k-1.(11/4)
Como (11/4) < (7/4)2, temos:
ak+1 < (7/4)k-1.(7/4)2 = (7/4)k+1,
como queríamos demonstrar.
Sobre os dois métodos
 Ambos usam recorrência.
 Ambos necessitam de uma afirmação 
que é válida inicialmente.
 No primeiro modo, mostramos que, se a 
afirmação é válida para um inteiro k,afirmação é válida para um inteiro k, 
também é válida para k+1.
 No segundo modo, mostramos que, se a 
afirmação é válida para todo inteiro 
menor ou igual a k (e maior do que o 
valor para o qual inicialmente é válida),valor para o qual inicialmente é válida), 
então é válida para k+1.
Interatividade
O princípio da indução completa demonstra 
afirmações matemáticas:
a) Através de um grande número de 
exemplos.
b) Através de contraexemplos.b) Através de contraexemplos.
c) Provando que tal afirmação é válida em 
um caso inicial e depois provando que, se 
for válida para um número qualquer, 
também o será para seu sucessor.
d) Verificando se as afirmações sãod) Verificando se as afirmações são 
aplicáveis na vida prática.
e) Negando as afirmações contrárias.
Múltiplos e divisores
Exemplo 1: 
Seja M(12) o conjunto de todos os múltiplos 
de 12:
 M(12) = {..., -36, -24, -12, 0, 12, 24, 36, ...}
Exemplo 2:Exemplo 2: 
Seja D(12) o conjunto de todos os divisores 
de 12:
 D(12) = {-1, 1, -2, 2, -3, 3, -4, 4, -6, 6, -12, 
12}
Ao escrevermos a igualdade 12 = 2 6Ao escrevermos a igualdade 12 = 2.6, 
estamos dizendo que:
1. 12 é múltiplo de 2 e de 6.
2. 2 e 6 são divisores de 12.
3. 12 é divisível por 2 e por 6.
Propriedades e notação
 Os múltiplos de um inteiro m são 
escritos na forma k.m, em que k é inteiro.
Propriedades dos múltiplos:
1. km + pm = (k + p)m (a soma de dois 
múltiplos de m também é múltipla de m).múltiplos de m também é múltipla de m).
2. (km).(pm) = (kmp)m (o produto de dois 
múltiplos de m também é múltiplo de m).
Notação para divisores:
 Se k é um divisor de q, dizemos que k 
divide q e usamos a notação: k ׀ q.
Mais propriedades
 Qualquer inteiro m é divisor de zero, pois 
0 = 0.m (observe que zero não é divisor 
de nenhum número).
 1 divide todo número inteiro m, pois m = 
m.1
 Todo inteiro m divide a si mesmo (m׀m), 
pois m = m.1
Para quaisquer p, q e r inteiros, temos:
 Se p׀q e q׀p, então p=q.
 Se p׀q e q׀r, então p׀r.
 Se p׀q e p׀r, então p׀(qx + ry), quaisquer 
que sejam os inteiros x e y.
Números primos
 Um número é primo se o conjunto de 
seus divisores é {-1, 1, -p, p}
Observações:
1. Números que não são primos são 
compostos.compostos.
2. Os números 2 e -2 são os únicos pares 
que são primos.
3. -1 e 1 não são primos.
4. Se o maior divisor comum entre dois 
números é 1, dizemos que esses 
números são primos entre si ou 
relativamente primos.
A divisão euclidiana
Considere o exemplo:
Dividindo-se 11 por 4, obtemos quociente 2 
e resto 3. Sendo assim, podemos escrever 
a igualdade:
 11 = 2.4 + 311 2.4 3
Dividindo-se um inteiro a por outro inteiro 
não nulo b, obtemos quociente q e resto r, 
então escrevemos a igualdade:
a = q.b + r (com b diferente de zero e r<b)
 Se r = 0, a divisão é exata e q e b são 
divisores de a.
Exemplo
 Dividindo-se um inteiro n por 5, obtém-se 
resto 1, mas dividindo-se n por 6, o 
quociente diminui em uma unidade e a 
divisão fica exata. Determine o número n.
Resolução:
 Na divisão por 5, vamos obter quociente 
q e resto 1, e na divisão por 6 vamos 
obter quociente (q-1) e resto 0; assim:
 n = 5q + 1 (I)
 n = 6(q 1) (II) n = 6(q-1) (II)
Igualando-se as equações I e II, obtemos: 
 q = 7 e n = 36. 
Interatividade
O quociente e o resto na divisão euclidiana 
de a por b em que a = -124 e b = 18 são, 
respectivamente:
a) q = -7 e r = 18
b) q = 7 e r = 18b) q 7 e r 18
c) q = -7 e r = 2
d) q = -7 e r = 17
e) q = -7 e r = 0
Representação de inteirosem uma base
 Exemplo: 257 = 2.100 + 5.10 + 7.1 =
= 2.102 + 5.101 + 7.100
 Teorema: Sejam a e b números naturais, 
com b não nulo e 1 < a , então, existem 
naturais r0, r1, ..., rn, tais que 
b = rn.an + rn-1.an-1 + ... + r1.a + r0 (com as 
condições de que n é natural, rn diferente 
de zero e que, para todo i, 0 ≤ ri < a). 
Essa representação é única.
Exemplo 1:
Escrever o número (110)2 na base decimal:
(110)2 = 1.22 + 1.21 + 0.20 =
= 1.4 + 1.2 + 0.1 = 4 + 2 + 0 = 6
Exemplo 2
Passar o número 21, escrito na base 
decimal, para a base binária:
 21 dividido por 2 tem quociente 10 e 
resto 1
 10 dividido por 2 tem quociente 5 e resto10 dividido por 2 tem quociente 5 e resto 
0
 5 dividido por 2 tem quociente 2 e resto 1
 2 dividido por 2 tem quociente 1 e resto 0
 1 dividido por 2 tem quociente 0 e resto 1
Copiam-se os restos na ordem inversa: 
(10101)2
Concluindo o exemplo 2:
De fato: 
(10101)2 = 1.24 + 0.23 + 1.22 + 0.21 + 1.20 = 
= 1.16 + 0.8 + 1.4 + 0.2 + 1.1 =
= 16 + 0 + 4 + 0 + 1 = 21
Interatividade
Escrevendo-se o número (11)2 na base 10, 
obtemos:
a) 2
b) 3
c) 5c) 5
d) 10
e) 11
Maior Divisor Comum – MDC
Sejam dois números inteiros a e b, sendo 
ao menos um deles diferente de zero, o 
máximo divisor comum de a e b é um 
número inteiro d tal que:
(i) d׀a e d׀b
(ii) Se c é um número inteiro tal que c׀a e 
c׀b, então c׀d.
Assim, chama-se máximo divisor comum, 
ou maior divisor comum de a e b, o maior 
dos seus divisores comuns, isto é:dos seus divisores comuns, isto é:
 MDC(a,b)=maxD(a,b)
Exemplo 1
1. Para um número inteiro dado, indicar por 
D(a) o conjunto de seus divisores e M(a) 
o conjunto de seus múltiplos: 
a) D(2) = {1, -1, 2, -2} e M(2) = {0, ±2, ±4, ±6, 
...}.
b) D(-3) = {1, -1, 3, -3} e M(-3) = {0, ±3, ±6, ±9, 
...}.
c) D(0) = Z e M(0) = {0}.
d) D(3) = {1, -1, 3, -3} e M(3) = {0, ±3, ±6, ±9, 
}...}.
e) D(1) = {1} e M(1) = Z.
Exemplo 2
Utilizando os resultados do exercício 
anterior: 
D(3) = {1, -1, 3, -3} e M(3) = {0, ±3, ±6, ±9, ...}.
D(-3) = {1, -1, 3, -3} e M(-3)={0, ±3, ±6, ±9, ...}.
D(1) = {1} e M(1) = ZD(1) = {1} e M(1) = Z
Obtém-se:
I. MDC(3, 3) = 3
II. MDC(3, -3) = 3
III MDC(1 -3) = 1III. MDC(1, -3) = 1
IV.MDC(1, 3) = 1
Mínimo Múltiplo Comum – MMC
Sejam a e b números inteiros, excluído o 
zero, o mínimo múltiplo comum de a e b é 
um número inteiro m tal que:
a׀m e b׀m 
 Se c é um número inteiro tal que a׀c eSe c é um número inteiro tal que a׀c e 
b׀c, então m׀c.
Assim, chama-se mínimo múltiplo comum 
de a e b o menor dos seus múltiplos 
positivos comuns, isto é:
MMC(a b)=minM(+)(a b)MMC(a,b)=minM(+)(a,b)
Exemplo
Em exemplo anterior, foi constatado que:
D(3) = {1, -1, 3, -3} e M(3) = {0, ±3, ±6, ±9, ...}
D(1) = {1} e M(1) = Z
Assim:
I. MDC (3, 3) = 3
II. MDC (1, 3) = 1
Congruências
Definição: 
 Seja m um número inteiro, maior do que 
1, dados dois números inteiros x e y, 
dizemos que x é côngruo a y, módulo m, 
se e somente se m dividir x-y (o que é 
representado por m׀(x-y) ). 
Exemplo
Pode-se afirmar que:
I. 152≡5(mod 7), uma vez que 7׀(152-5)
II. -152≡2(mod 7), uma vez que 7׀(-152-2)
Interatividade
 Seja A subconjunto de Z e definido como 
A = {-1, 0, 1, 2, 3...}, assinale a alternativa 
falsa:
a) Os números -1, -2, -3, ... são limites 
inferiores de A.
b) O mínimo do conjunto A é -1.
c) O subconjunto A de Z é limitado 
inferiormente.
d) O subconjunto A de Z não é limitado 
superiormentesuperiormente.
e) Os números -1, -2, -3, ... são limites 
superiores de A.
ATÉ A PRÓXIMA!