aula02_2010

Prévia do material em texto

A´lgebra A - Aula 02
Teorema da fatorac¸a˜o u´nica,
Propriedade fundamental dos primos, nu´meros
primos
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Teorema da fatorac¸a˜o u´nica
I p e´ primo: p 6= 1 e os u´nicos divisores de p sa˜o p e 1.
I Nu´mero (diferente de 1) na˜o primo = composto.
I Teorema da fatorac¸a˜o u´nica: Dado um inteiro positivo
n ≥ 2 podemos sempre escreveˆ-lo, de maneira u´nica, na forma:
n = pe11 . . . . .p
ek
k
onde 1 < p1 < p2 < . . . < pk sa˜o nu´meros primos e e1, . . . , ek
sa˜o inteiros positivos (multiplicidades).
Existeˆncia da fatorac¸a˜o
Algoritmo ingeˆnuo: Dado n ≥ 2 inteiro positivo, tente dividir n
por cada um dos inteiros de 2 a n − 1. Se algum desses inteiros
(digamos k) dividir n, enta˜o achamos um fator de n.
Perguntas:
1. k e´ primo ou composto?
2. Quando se deve parar a busca? Em n − 1?
Existeˆncia da fatorac¸a˜o
Respostas:
1. k e´ primo. Se k composto, k = a.b com 1 < a, b < k . Mas
k|n, enta˜o existe c inteiro tal que n = k.c. Logo,
n = a.b.c
ABSURDO! Logo, k e´ primo.
2. Podemos parar o algoritmo em
√
n. De fato, n = k .c ou
c = nk . Como k e´ o menor fator de n, k ≤ c . Logo, k ≤ nk ou
seja, k2 ≤ n→ k ≤ √n.
Algoritmo de fatorac¸a˜o
Etapa 1. F = 2;
Etapa 2. Se n/F e´ inteiro, escreva “F fator de n” e pare;
Etapa 3. Incremente F de uma unidade; Se F >
√
n escreva “n e´
primo” e pare; se na˜o, volte para a Etapa 2.
Existeˆncia da fatorac¸a˜o
I Algoritmo acima: acha todos os fatores primos de n.
I n→ q1. Pro´ximo passo: nq1 → q2 A seguir, nq1.q2 → q3
I Paramos em nq1.q2.....qs−1 = qs , com qs primo.
I Observe que q1 ≤ q2 ≤ . . . ≤ qs−1 ≤ qs e
n >
n
q1
>
n
q1.q2
> . . . >
n
q1.q2. . . . .qs
> 0,
ou seja, o algoritmo sempre termina.
I Exemplo: n = 450 = 2.3.3.5.5
Eficieˆncia do algoritmo ingeˆnuo de fatorac¸a˜o
I Algoritmo simples mas muito ineficiente!
I Exemplo n primo com 100 ou mais algarismos. Logo,
n ≥ 10100 e portanto √n ≥ 1050. Logo sera˜o 1050 loops para
determinar que n e´ primo. Se o computador executa 1010
diviso˜es/s, levaremos 10
50
1010
= 1040 segundos, ou seja, 1031
anos... Tempo estimado de existeˆncia do universo: 1011 anos!
I Algoritmo bom para nu´meros pequenos.
I Na˜o existe (atualmente) algoritmo de fatorac¸a˜o eficiente para
todos os inteiros.
I Na˜o se sabe se tal algoritmo na˜o existe ou se na˜o fomos
espertos o suficiente para inventa´-lo...
Fatorac¸a˜o por Fermat
I Eficiente quando n tem um fator primo na˜o muito menor que√
n.
I Ide´ia: tentar achar nu´meros inteiros positivos x e y tais que
n = x2 − y 2.
I Caso mais fa´cil: n = r 2 (x = r e y = 0).
I Se y > 0, enta˜o
x =
√
n + y 2 >
√
n
Notac¸a˜o: escrevemos [r ] como a parte inteira do nu´mero real r .
Algoritmo de Fermat
I Etapa 1: Fac¸a x = [
√
n]; se n = x2, pare.
I Etapa 2: Incremente x de uma unidade e calcule
y =
√
x2 − n.
I Etapa 3: Repita a etapa 2 ate´ encontrar um valor inteiro para
y , ou ate´ que x = n+12 . No primeiro caso, n tem fatores x + y
e x − y ; no segundo, n e´ primo.
Exemplo
n = 1342127. Temos que x = 1158. Mas
x2 = 11582 = 1340964 < 1342127
Logo, passamos a incrementar x ate´ que√
x2 − n
seja inteiro ou x = n+12 , que nesse caso vale 671064:
x
√
x2 − n
1159 33, 97
1160 58, 93
1161 76, 11
1162 90, 09
1163 102, 18
1164 113
Logo, x = 1164 e y = 113. Os fatores procurados sa˜o
x + y = 1277 e x − y = 1051.
Algoritmo de Fermat
Demonstrac¸a˜o: se n e´ primo, enta˜o o u´nico valor poss´ıvel para x e´
x = n+12 .
x e y sa˜o inteiros positivos tais que n = x2 − y 2. Ou seja,
n = (x − y)(x + y)
Como estamos supondo n primo, temos que x − y = 1 e
x + y = n. Logo,
x =
1 + n
2
e y =
n − 1
2
como quer´ıamos.
Obs: RSA - Se p e q sa˜o muito pro´ximos, enta˜o n = p.q e´
facilmente fatora´vel pelo algoritmo de Fermat.
Propriedade fundamental dos primos
Lema: Sejam a, b, c inteiros positivos e suponhamos que a e b
sa˜o primos entre si. Enta˜o:
1. Se b divide o produto a.c enta˜o b divide c .
2. Se a e b dividem c enta˜o o produto a.b divide c.
Propriedade fundamental dos primos
1. mdc(a, b) = 1. Pelo Algoritmo euclideano estendido, existem
α e β tais que
α.a + β.b = 1
Enta˜o,
α.a.c + β.b.c = c
Como b divide a.c pela hipo´tese (1) e como b divide β.b.c,
enta˜o b divide c.
2. Se a divide c , enta˜o c = at. Mas b tambe´m divide c . Como
mdc(a, b) = 1, pela afirmac¸a˜o (1), b divide t. Logo, t = b.k
para algum inteiro k e portanto,
c = a.t = a.b.k
Propriedade fundamental dos primos
Podemos usar o lema acima para provar se seguinte propriedade:
Propriedade fundamental dos primos: Seja p um primo e a e b
inteiros positivos. Se p divide o produto a.b, enta˜o p divide a ou p
divide b.
A demonstrac¸a˜o fica como exerc´ıcio (fac¸am!).
Unicidade
Seja n o menor inteiro positivo que admite duas fatorac¸o˜es
distintas. Podemos escrever:
n = pe11 . . . . .p
ek
k = q
r1
1 . . . . .q
rs
s
onde p1 < p2 < . . . < pk e q1 < q2 < . . . < qs sa˜o primos e
e1, . . . , ek , r1, . . . , rs sa˜o inteiros positivos.
Como p1 divide n, pela propriedade fundamental dos primos p1
deve dividir um dos fatores do produto da direita. Mas um primo
so´ pode dividir outro se forem iguais. Enta˜o p1 = qj para algum j
entre 1 e s. Logo,
n = pe11 . . . . .p
ek
k = q
r1
1 . . . . .q
rj
j . . . . .q
rs
s
= qr11 . . . . .p
rj
1 . . . . .q
rs
s
Unicidade
Podemos enta˜o cancelar p1 que aparece em ambos os lados da
equac¸a˜o, obtendo
m = pe1−11 . . . . .p
ek
k = q
r1
1 . . . . .p
rj−1
1 . . . . .q
rs
s
onde m e´ um nu´mero menor que n que apresenta duas fatorac¸o˜es
distintas. ABSURDO pois isso contraria a minimalidade de n.
Exerc´ıcios propostos - Cap´ıtulo 2
1. Prove a propriedade fundamental dos primos.
2. Demonstre que, se p e´ um nu´mero primo, enta˜o
√
p e´ um
nu´mero irracional.
3. Livro texto: 2, 4, 5, 8, 11, 12.
Nu´meros primos
Ate´ agora:
I propriedades ba´sicas dos nu´meros inteiros;
I dois algoritmos fundamentais;
Nessa aula, discutiremos me´todos ingeˆnuos para encontrar primos.
Fo´rmulas Polinomiais
Considere o polinoˆmio:
f (x) = an.x
n + an−1.xn−1 + . . .+ a1.x + a0
onde an, an−1, . . . , a1, a0 sa˜o nu´meros inteiros e que satisfaz a
condic¸a˜o:
f (m) e´ primo, para todo inteiro positivo m
Exemplo
Seja f (x) = x2 + 1 Logo,
x f (x)
1 2
2 5
3 10
4 17
...
8 65
9 82
Fo´rmulas Polinomiais
Teorema: Dado um polinoˆmio f (x) com coeficientes inteiros,
existe uma infinidade de inteiros positivos m tais que f (m) e´
composto.
Prova: Consideraremos f do tipo:
f (x) = a.x2 + b.x + c
Podemos supor a > 0. Suponhamos que exista m tal que
f (m) = p onde p e´ primo. Calculando f (m + hp):
f (m + hp) = a(m + hp)2 + b(m + hp) + c
= (am2 + bm + c) + p(2amh + aph2 + bh)
= p(1 + 2amh + aph2 + bh)
Basta tomarmos:
h >
−b − 2am
a.p
Conclusa˜o: na˜o existe uma fo´rmula polinomial (em uma
varia´vel) para primos.
Fo´rmulas exponenciais: nu´meros de Mersenne
I Nu´meros de Mersenne: M(n) = 2n − 1
I Nu´meros perfeitos: sa˜o iguais a` metade da soma de seus
divisores. Ex: 6 = 12/2 e 12 = 1 + 2 + 3 + 6
I Nenhum primo e´ perfeito.
I Resultado: 2n−1.(2n − 1) e´ perfeito se 2n − 1 e´ primo.
I Outro resultado: Todo nu´mero perfeito par possui a forma
acima. Ex: 6 = 22−1(22 − 1)
I O que na˜o se sabe: se existem nu´meros perfeitos ı´mpares.
I Pergunta: Quais sa˜o os nu´meros de Mersenne primos?
Exemplos: quando n = 2, 3, 5, 7, 13, 17, 19, 31, 61.... Observe
que os expoentes sa˜o todos primos, mas nem todos primos
fazem parte dessa lista. Por exemplo,
M(11) = 2047 = 23.89
Fo´rmulas exponenciais: nu´meros de Fermat
I Nu´meros de Fermat: F (n) = 22
n
+ 1
I Exemplos de nu´meros de Fermat primos: n = 0, 1, 2, 3, 4.
F (5) = 18446744073709551617 e´ composto!
I Poucos primos de Fermat sa˜o conhecidos.Ate´ hoje, na˜o se
descobriu nenhum F (n) primo com n ≥ 5.
Fo´rmulas fatoriais
p# e´ o produto de todos os primos menores ou iguais a p. Ex:
5# = 2.3.5 = 30
Se p e q sa˜o primos sucessivos, enta˜o
p# = q#.p
Estaremos interessados nos nu´merosda forma p# + 1. Embora
p# + 1 nem sempre seja primo (Ex. 13# + 1 = 30031 = 59.509),
podemos mostrar que na˜o tem nenhum fator primo menor ou igual
a p. Desta forma, temos um algoritmo para calcular primo.
Pergunta: qual e´ o problema de tal algoritmo?
Observac¸a˜o final: p# + 1 quase nunca e´ primo!
Infinidade de primos
Teorema: Existe uma infinidade de primos
Prova:
Digamos que exista uma quantidade finita de primos:
{p1, p2, . . . , pk}
Podemos supor que esses primos esta˜o ordenados, de modo que pk
e´ o maior deles. Considere o nu´mero p#k + 1. Como vimos, esse
nu´mero possui fator primo maior que pk . ABSURDO!
Crivo de Erato´stenes
O crivo de Erato´stenes e´ o mais antigo dos me´todos para encontrar
primos.
Etapa 1: Listamos os nu´meros ı´mpares de 3 a n.
Etapa 2: Procure o primeiro nu´mero k da lista. Risque os demais
nu´meros da lista, de k em k .
Etapa 3: Repita a etapa 2 ate´ chegar em n.
Observac¸o˜es:
1. Podemos parar em
√
n...
2. Podemos comec¸ara riscar a partir de k2...
Crivo de Erato´stenes revisado
Etapa 1: Crie um vetor v de n−12 posic¸o˜es, preenchidas com o valor 1;
fac¸a P = 3.
Etapa 2: Se P2 > n, escreva os nu´meros 2j + 1 para os quais a j-e´sima
entrada de v e´ 1 e pare;
Etapa 3: Se a posic¸a˜o (P−1)2 de v esta´ preenchida com 0 incremente P
de 2 e volte a` Etapa 2.
Etapa 4: Atribua o valor P2 a uma nova varia´vel T ; substitua por zero
o valor da posic¸a˜o (T−1)2 e incremente T de 2P; repita ate´
que T > n; incremente P de 2 e volte a` Etapa 2.
Exerc´ıcios propostos - Cap´ıtulo 3
1. Entenda e implemente o algoritmo da pag 65 do livro texto.
2. Livro texto: 1, 3 a 7, 8 e 10.