Resumo teoria dos números

Prévia do material em texto

Teoria dos números 
 
1 
 
conjuntos 
Um conjunto é formado por objetos, de 
modo genérico chamados de elementos. 
Costuma-se indicar os conjuntos por 
letras maiúsculas e seus elementos por 
letras minúsculas de nosso alfabeto. Se 
um objeto a é elemento de um conjunto 
U, dizemos “a pertence a U” e 
denotamos essa relação por a∈ U. Caso 
contrário, dizemos que “a não pertence 
a U” e escrevemos a ∉U. 
Descrição de um conjunto: 
Comumente usam-se três procedi- 
mentos para definir um conjunto. 
‣ Descrever seus elementos por uma 
sentença. P. ex: 
- conjunto dos números reais; 
- conjunto dos planetas do sistema 
solar. 
‣ Listar seus elementos entre chaves. 
P.ex: 
- {2,4,6,8,10} 
- {0,1,2,3, ...} 
‣ Dar uma “Propriedade” que identifica 
seus elementos. P.ex: 
- {x| x é inteiro e x>2} 
- {x| x é real e 2<x<10} 
- {x| x goza da propriedade P} 
Subconjuntos 
Quando todos os elementos de um 
conjunto A qualquer pertencem a um 
outro conjunto B, diz-se, então, que A 
é um subconjunto de B, ou seja A ⊂ B 
(lê-se “A está contido em B) ou B ⊃A 
(lê-se “B contém A”) 
Observações: 
‣ Todo o conjunto A é subconjunto dele 
próprio, ou seja, A ⊂ A; 
‣ O conjunto vazio, por convenção, é 
subconjunto de qualquer conjunto, ou 
seja, φ ⊂A. 
Interseção e união (e , ou) 
A interseção de dois conjuntos, A e B, 
é o conjunto indicado por A ∩ B e 
definido pela proprie. “X ∈ A e X ∈ B”. 
Portanto: 
 
 
 
A união de dois conjuntos, A e B, é o 
conjunto indicado por A ∪ B, e definido 
pela propriedade “X ∈ A ou X ∈ B”. 
Portanto: 
 
 
2 
 
Diferença de conjuntos: A – B 
A-B é formado pelos elementos que 
estão em A e não estão em B. 
 
 
 
 
Produto cartesiano 
Dados os conjuntos A e B, chama-se 
produto cartesiano A com B, ao conjunto 
AxB, formado por todos os pares 
ordenados (x,y), onde x é elemento de A e 
y é elemento de B, ou seja: 
 
Número de subconjuntos de um conjunto: 
Se um conjunto A possuir n elementos, 
então existirão 2n subconjuntos de A. 
Indução matemática 
Princípio do menor número inteiro 
Seja L um subconjunto não vazio de Z. 
Dizemos que L é limitado inferiormente 
se existe um número a ∈ Z tal que a≤ x, 
qualquer que seja o elemento x ∈ L. 
Todo elemento a ∈ Z que cumpre essa 
condição chama-se limite inferior de L. 
Obviamente, se um inteiro a é limite 
inferior de L, então todo inteiro menor 
que a também o é. Um limite inferior de 
L que pertença a esse conjunto chama-
se mínimo de L. 
Se L é um subconjunto de Z (não vazio e 
limitado inferiormente), então L possui 
um mínimo. Por exemplo, o conjunto dos 
 números inteiros positivos é limitado 
inferiormente e seu mínimo é o número 0 
Princípio de Indução Matemática: 
Dado um subconjunto S do conjunto dos 
números naturais (N), tal que 1 
pertence a S e sempre que um número n 
pertence a S, o número n + 1 também 
pertence a S, tem-se que S = N 
 Esta simples propriedade fornece 
uma das mais poderosas técnicas de 
demonstração em Matemática :a 
demonstração por indução. 
Suponha que seja dada uma sentença 
matemática P(n) que dependa de uma 
variável natural n, a qual se torna 
verdadeira ou falsa quando 
substituímos n por um número natural 
dado qualquer. Tais sentenças serão 
ditas sentenças abertas definidas 
sobre o conjunto dos naturais. 
Primeiro principio de indução: 
Seja P(n) uma função proposicional 
cujo universo é o conjunto dos inteiros 
maiores que ou iguais a um inteiro dado 
a. Suponhamos que se consiga provar o 
seguinte: 
(i) P(a) é verdadeira 
(ii) Se r ≥ a e p(r) é verdadeira, 
então p(r+1) também é 
verdadeira. 
Então P(n) é verdadeira para todo 
n ≥a. 
Demonstração: 
Seja L =}x ∈ Z | x ≥ a e p(x) é falsa
Se mostramos que L=φ, o princípio 
3 
 
estará justificado. Para isso vamos 
raciocinar por redução ao absurdo. 
Suponhamos então que L=φ. Então, uma 
vez que L é limitado inferiormente (a é 
um limite inferior), L possui um mínimo l0. 
Como p(a) é verdadeira, é claro que 
l0 > a e, então, l0 – 1 ≥ a. 
Por outro lado, p(l0 – 1) é verdadeira, 
já que l0 – 1 está fora de L. Então, 
levando em conta a hipótese (ii), p((l0 – 
1) +1) = p(l0 ) é verdadeira. Mas isso é 
absurdo, pois l0 está em L. # 
Como imagem para ilustrar o primeiro 
principio de indução, costuma-se usar o 
efeito dominó. Suponhamos uma fileira 
infinita de pedrinhas de dominó. Se a 
primeira pedra tomba para frente, e o 
fato de uma pedra tombar faz com que 
a da frente tombe também, então 
todas as pedrinhas tombarão. 
Segundo princípio de indução: 
Seja P(n) uma função proposicional 
cujo universo é o conjunto dos inteiros 
maiores que ou iguais a um inteiro dado 
a. Suponhamos que se consiga provar o 
seguinte: 
(i) P(a) é verdadeira. 
(ii) Se r ≥a e p(k) é verdadeira e para 
todo k tal que a ≤ k < r, então p(r) 
também é verdadeira. 
Então p(n) é verdadeira para todo 
n ≥a. 
A demonstração desse princípio é 
análoga à do primeiro. 
Critérios de divisibilidade 
Quando perguntamos se um dado 
número b é divisível por um número a, 
podemos pensar que estamos 
perguntando se o resto da divisão de b 
por a é igual a zero. 
– Um número é divisível por 2 quando é 
par. 
– Um número é divisível por 3 quando a 
soma dos seus algarismos é divisível por 
3. 
– Um número é divisível por 4 quando o 
número formado pelos seus dois últimos 
algarismos é divisível por 4. 
– Um número é divisível por 5 quando 
terminar em 0 ou 5 
– Será divisível por 6 quando é divisível 
por 2 e 3 ao mesmo tempo. 
– Será divisível por 9 quando a soma dos 
seus algarismos é divisível por 9 
– É divisível por 10 quando termina em 0 
Algoritmo euclidiano 
O algoritmo euclidiano, que trata- 
remos aqui, estabelece uma “divisão 
com resto” e é a base da aritmética 
teórica (teoria dos números). Seu nome 
deriva do fato de Euclides o haver 
usado em seus elementos para 
determinar o máximo divisor comum de 
dois números positivos. 
Máximo divisor comum (M.D.C.) 
O máximo divisor comum corresponde 
ao maior número divisível entre dois ou mais 
números inteiros. 
Definição 1: Sejam a e b dois números 
inteiros. Um elemento d ∈ Z se diz 
4 
 
máximo divisor comum de a e b se cumpre 
as seguintes condições: 
(i) d ≥ 0 
(ii) d | a e d | b 
(iii) se d’ é um numero inteiro tal que 
d’ | a e d’ | b, então d’ | d (ou seja, 
todo divisor comum a a e b 
também é divisor de d) 
Propriedades do MDC 
– Se d e d, são máximos divisores 
comuns de a e b, então d = d 1 (de 
fato, devido à definição, d | d 1 e d 1| 
d. Como se trata de números 
positivos, isso só é possível se d = d 1. 
Fica garantido então, que dado um 
par de inteiros não pode ter mais de 
um máximo divisor comum) 
– O número zero é o máximo divisor 
comum de a = 0 e b = 0 
– Quando fatoramos dois ou mais 
números, o MDC deles é o produto dos 
fatores comuns a eles. 
– Se d é o máximo divisor comum de a e 
b, então d também é o mdc de -a e b, 
a e -b e -a e -b. (basta lembrar que 
todo divisor de x é divisor de -x, e 
vice-versa) 
 
Obviamente, a definição de m.d.c. de 
dois números inteiros não garante por 
si só sua existência. A intuição nos diz 
que isso é verdade, mas a rigor, é 
preciso demonstrar que é. A seguinte 
demonstração se justifica princi-
palmente porque garante a 
possibilidade de exprimir de maneira 
aritmética o m.d.c. de a e b como uma 
soma envolvendo esses elementos. 
Proposição 1: Para quaisquer inteiros 
a e b , existem inteiros x0 e y0 tais que 
d = ax0 + by0 é o máximo divisor comum 
de a e b. 
Demonstração: Levando em conta a 
última propriedade imediata, 
relacionada acima, podemos nos ater 
ao caso em a > 0 e b > 0 
Consideremos o conjunto L=}ax0 + by0| 
x, y ∈ Z L possui elementos 
estritamente positivos, por exemplo 
a+b, obtido ao se fazer x=y=1. Seja d 
o menor entre todos os elementos 
estritamente positivos de L. Portanto 
d= ax0 + by0, para conveniente 
elementos x0, y0 ∈ Z. Mostremos que dé 
o m.d.c. de a e b. 
De fato: (i) Obviamente d ≥ 0 ; (ii) 
Apliquemos o algoritmo euclidiano a a 
e d, o que é possível, pois 
d > 0 : a = dq + r(0 ≥ r < d). 
 Mas, como já vimos, d= ax0 + by0 e, 
então: 
a = (ax0 + by0 ) q + r 
Daí, por transposições algébricas 
convenientes, 
r = a(1-qx0) + b(-qy0) 
O que mostra que r é um elemento de 
L. Então, r não pode ser estritamente 
positivo, pois é menor que d (= mínimo de 
L). Logo, r=0 e, portanto, a=dq. Ou 
seja, d|a. 
De maneira análoga se demonstra 
que d | b. ; (iii) Se d’ | a e d’ | b, então 
d’| d, uma vez que d= ax0 + by0 # 
5 
 
 
Proposição 2: Para que os inteiros 
a e b sejam primos entre si, é 
necessário e suficiente que se possam 
encontrar x0, y0 ∈ Z tais que 
ax0 + by0 = 1 
Demonstração: Se a e b são primos 
entre si, então a proposição 1 
garante a existência do par de 
elementos x0, y0 conforme o enunciado. 
Reciprocamente, suponhamos que se 
possam encontrar x0, y0 ∈ Z tais que 
ax0 + by0 = 1. Então qualquer divisor 
de a e b é também divisor de 1. Logo, 
os únicos divisores comuns aos 
elementos de a e b são +1 e -1. De 
onde o m.d.c. de a e b é 1. # 
Corolário: se a e b são inteiros não 
simultâneos nulos e se d = mdc(a,b), 
então mdc(a/d, b/d) = 1. 
Demonstração: é só trabalhar com 
a identidade de Bezout para a e b. 
Como d=mdc(a,b), então existem 
inteiros x0 e y0 tais que ax0 + by0 = d. 
Daí (dividindo ambos os membros por 
d): 
(a/d)x0 + (b/d)y0 = 1 
Então, por causa da proposição, a/d 
e b/d são primos entre si. # 
Proposição 3: Se a e b são inteiros 
primos entre si e a | bc, então a | c. 
 Demonstração: Devido à proposição 
anterior, ax0 + by0 = 1, para 
convenientes inteiros x0 e y0. 
Multiplicando-se os dois membros 
dessa igualdade por c: 
(ac)x0 + (bc)y0 = c 
Como a divide a, então a divide 
(ac)x0; e, como a divide bc (por hipó-
tese), então divide (bc)y0. Logo, a 
divide a soma (ac)x0 + (bc)y0. Ou 
seja, a divide c, como queríamos 
provar. # 
Proposição 4: Sejam a e b inteiros 
primos entre si. Se a | c e b | c, então 
ab | c. 
Demonstração: Consideramos uma 
identidade de Bezout para a e b : 
ax0 + by0 = 1 
Multiplicando-se ambos os membros 
dessa igualdade por c: 
(ac)x0 + (bc)y0 = c 
Como a |a eb |c, então ab | ac e 
portanto, ab | (ac)x0. De maneira 
análoga, demonstra-se que ab | (bc)y0. 
Logo, ab | [(ac)x0 + (bc)y0], ou seja, 
ab | c. # 
Exercício: 
Prove que mdc(a, mdc(b,c)) = mdc(a,b,c): 
Resolução: Seja d = mdc(a,b,c) e provemos 
que d= mdc(a, mdc(b,c)). (i) d ≥ 0, pela 
definição de mdc. (ii) Como d | a,d | b e d | c, 
por hipótese, então d | a e d| mdc(b,c) visto 
que todo divisor de b e c é divisor do máximo 
divisor comum desses números. (iii) Seja d’ um 
divisor de a e de mdc(b,c) ; então d’ | a, d’ | 
b e d’ | c e portanto, divide o máximo divisor 
comum desses números, ou seja, divide d. #