Teoria dos numeros

Prévia do material em texto

- -1
TEORIA DOS NÚMEROS
INTEIROS, PRINCÍPIO DA INDUÇÃO FINITA, 
ALGORITMO DA DIVISÃO E DIVISIBILIDADE
- -2
Olá!
O princípio da Indução Finita exerce papel preponderante nas demonstrações dos Teoremas, que são de grande
importância no estudo da Matemática Superior. Através do princípio da Indução Finita, podemos desenvolver
algoritmos que facilitarão a resolução de vários problemas no estudo da Matemática, bem como de outras
ciências.
Ao final desta aula, o aluno será capaz de:
1- Conceituar o princípio da Indução Finita;
2- Identificar e determinar a aplicação do Princípio da Indução Finita.
1 Indução Matemática
Seja P(n) uma proposição associada a cada inteiro positivo n e que satisfaz às duas seguintes condições:
p(1) é verdadeira;
para todo inteiro positivo K, se P(K) é verdadeira, então P(K+1) também é verdadeira.
Nestas condições, a proposição P(n) é verdadeira para todo inteiro positivo n.
Exemplos:
Demonstrar a proposição:
P(n):1+3+5+...+(2n-1) = n2, para todo n pertencente ao conjunto dos números naturais.
Demonstração:
P(1) é verdadeira, visto que 1=12.
A hipótese de indução é que a proposição:
P(k):1+3+5+...+(2k-1)=k2, k pertencente ao conjunto dos números naturais é verdadeira.
Adicionando 2k+1 a ambos os membros desta igualdade, obtemos:
1+3+5+.....+(2k-1)+(2k+1) =k2+(2k+1) =(k+1)2
E isto significa que a proposição p (k+1) é verdadeira.
Logo, pelo “Teorema da indução matemática”, a proposição P(n) é verdadeira para todo inteiro positivo n.
- -3
Demonstrar a proposição:
P(n): 3 |(22n-1), para todo número natural n.
Demonstração:
P(1) é verdadeira, visto que 3|(22-1).
A hipótese de indução é que a proposição:
P(K):3|(22k-1), k pertencente ao conjunto dos números naturais, é verdadeira. Portanto:
22k -1 =3q, com q inteiro.
O que implica:
22(k+1)-1 =22k+2 =22k.22 -1 =4.22k-1=
=4.22k -4+4-1 =4(22k-1)+3=
=4.3q +3 =3(4q+1)
Isto é, a proposição p(k+1) é verdadeira. Logo, pelo “Teorema da indução matemática”, a proposição P(n) é
verdadeira para todo inteiro positivo n.
Uma interessante digressão:
Usando indução, nos “provamos” a seguinte proposição:
Toda pessoa é do mesmo sexo.
Demonstração:
Seja P(n): Todos em um conjunto de n pessoas são do mesmo sexo. Claramente, P(1) é verdadeira. Seja K um
inteiro positivo tal que P(K) é verdadeira; que significa todos no conjunto de k pessoas são do mesmo sexo.
Para mostrar que P(k+1) é verdadeira, considere o conjunto A ={a1,a2,.....,ak+1} de k+1 pessoas. Partindo o
conjunto A em dois subconjuntos de A,B={a1,a2,.....,ak} e C={a2,a3,......,ak}.
Fique ligado
Nota: Quando adicionamos uma quantidade finita de inteiros ímpares positivos consecutivos,
encontramos para soma um número quadrado perfeito:
1+3=22
1+3+5=32
1+3+5+7=42
1+3+5+7+9=52
- -4
Desde que B e C apresentam k elementos, pela hipótese, todos os elementos de B são do mesmo sexo e todos os
elementos em C são do mesmo sexo.
Desde que B e C são subconjuntos de A, todas as pessoas em B U C devem ser do mesmo sexo; o que significa que
todas as pessoas de A têm o mesmo sexo.
Portanto, por indução, P(n) é verdadeira para todo inteiro positivo n.
2 Divisibilidade
Definição: Sejam a e b dois inteiros, com a ≠0.
Diz-se que a divide b se e somente se existe um inteiro q tal que b=aq.
Com a notação “a|b” indica-se que a≠0 divide b e, portanto, a notação “a b” significa que a≠0 não divide b.
A relação a divide b denomina-se relação de divisibilidade em z.
Exemplos:
a) 10|50, pois 50=10.5
b) -2|18, pois 18=(-2)(-9)
c) 8|16, pois 16 =8.(2)
3 Teorema
Se a ≠0 , então a |0 e a|a. Demonstração: De fato: 0=a.0 e a=a.1
1|b para qualquer b De fato: b=1.b
Se a|b , então a|bc para qualquer c. Demonstração: Se a|b, então existe um inteiro q tal que b=a.q. Multiplicando
ambos os membros da equação por c, temos: bc = aqc Como q e c são inteiros, o produto qc é inteiro. Logo, existe
um inteiro k (k=qc) que, multiplicado por a, é igual a bc. Portanto, a|bc.
Fique ligado
Nota: Claramente a afirmação que todas as pessoas são do mesmo sexo é falsa. Você pode
encontrar a falha na “demonstração”?
- -5
Se a|b e b|c , então a|c. Demonstração: Se a |b, então existe um inteiro r, tal que b = a.r. (1); Se b|c então existe um
inteiro s, tal que c = b.s (2). Substituindo (1) em (2), temos: c=b.s=(a.r).s=a.(rs) Como r e s são inteiros, então rs é
inteiro. Portanto, existe um inteiro k (k=rs) tal que c=ak , portanto, a|c.
Se a |c e a|c, então a |(bx+cy) para qualquer x e y. Demonstração: Se a |b então existe um inteiro q, tal que b=a.q
(1); Se a |c então existe um inteiro r, tal que c = a.r (2). Multiplicando a equação (1) por x e a equação (2) por y e
somando, temos: bx+cy =aqx+ary=a(qx+ry), como qx e ry são ambos inteiros, a soma é inteira. Então, existe um
inteiro k (k=qx+ry) tal que bx+cy = ak, portanto a|(bx+cy).
Se a|b, com b≠0, então |a| ≤ |b|. Demonstração: aIb , b≠0 , então existe um inteiro q≠0 tal que b = aq e IbI = IaI IbI
como q≠0 , segue-se que I qI ≥1 e , portanto IbI≥I Ai
3.1 Algoritmo da divisão
Teorema: Se a e b são dois números inteiros, com b > 0, então existem e são únicos os inteiros q e r que
satisfazem às condições:
a=bq+r e 0 ≤r<b
Exemplo:
Achar o quociente q e o resto r na divisão de a=59 por b=-14 que satisfazem às condições do algoritmo da divisão.
Efetuando a divisão usual dos valores absolutos de a e b, obtemos:
59=14.4+3
O que implica:
59=(-14)(-4)+3 e 0≤3 |-14|
Logo, o quociente q=-4 e o resto r=3
Achar o quociente q e o resto r na divisão de a=-79 por 11 que satisfazem às condições do
algoritmo da divisão.
Efetuando a divisão usual dos valores absolutos de a e b obtemos:
79=11.7+2
O que implica:
-79=11(-7)-2
Como o termo r =-2 <0 não satisfaz à condição de 0 ≤r<11, somando e subtraindo o valor 11 de b ao segundo
membro da igualdade anterior, obtemos:
-79=11(-7)-11+11-2=11(-8)+9
Com 0≤9<11. Logo, o quociente q =-8 e o resto r =9.
- -6
O que vem na próxima aula
Na próxima aula trataremos dos conceitos de Máximo Divisor Comum e Mínimo Múltiplo Comum.
CONCLUSÃO
Nesta aula, você:
• Aprendeu o princípio da Indução Finita;
• Relembrou conceitos dos números inteiros;
• Desenvolveu novas técnicas para a resolução de problemas
•
•
•
	Olá!
	1 Indução Matemática
	2 Divisibilidade
	3 Teorema
	3.1 Algoritmo da divisão
	O que vem na próxima aula
	CONCLUSÃO