Algebra A - Aula 02Teorema da fatoracao unica,

Propriedade fundamental dos primos, numerosprimos

Elaine Pimentel

Departamento de Matematica, UFMG, Brazil

2o Semestre - 2010

Teorema da fatoracao unica

I p e primo: p 6= 1 e os unicos divisores de p sao p e 1.

I Numero (diferente de 1) nao primo = composto.

I Teorema da fatoracao unica: Dado um inteiro positivon ≥ 2 podemos sempre escreve-lo, de maneira unica, na forma:

n = pe11 . . . . .p

ekk

onde 1 < p1 < p2 < . . . < pk sao numeros primos e e1, . . . , eksao inteiros positivos (multiplicidades).

Existencia da fatoracao

Algoritmo ingenuo: Dado n ≥ 2 inteiro positivo, tente dividir npor cada um dos inteiros de 2 a n − 1. Se algum desses inteiros(digamos k) dividir n, entao achamos um fator de n.Perguntas:

1. k e primo ou composto?

2. Quando se deve parar a busca? Em n − 1?

Existencia da fatoracao

Respostas:

1. k e primo. Se k composto, k = a.b com 1 < a, b < k . Mask|n, entao 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 ouc = n

k . Como k e o menor fator de n, k ≤ c . Logo, k ≤ nk ou

seja, k2 ≤ n→ k ≤√

n.

Algoritmo de fatoracao

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 nao, volte para a Etapa 2.

Existencia da fatoracao

I Algoritmo acima: acha todos os fatores primos de n.

I n→ q1. Proximo passo: nq1→ q2 A seguir, n

q1.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

Eficiencia do algoritmo ingenuo de fatoracao

I Algoritmo simples mas muito ineficiente!

I Exemplo n primo com 100 ou mais algarismos. Logo,n ≥ 10100 e portanto

√n ≥ 1050. Logo serao 1050 loops para

determinar que n e primo. Se o computador executa 1010

divisoes/s, levaremos 1050

1010 = 1040 segundos, ou seja, 1031

anos... Tempo estimado de existencia do universo: 1011 anos!

I Algoritmo bom para numeros pequenos.

I Nao existe (atualmente) algoritmo de fatoracao eficiente paratodos os inteiros.

I Nao se sabe se tal algoritmo nao existe ou se nao fomosespertos o suficiente para inventa-lo...

Fatoracao por Fermat

I Eficiente quando n tem um fator primo nao muito menor que√n.

I Ideia: tentar achar numeros inteiros positivos x e y tais quen = x2 − y 2.

I Caso mais facil: n = r 2 (x = r e y = 0).

I Se y > 0, entaox =

√n + y 2 >

√n

Notacao: escrevemos [r ] como a parte inteira do numero real r .

Algoritmo de Fermat

I Etapa 1: Faca x = [√

n]; se n = x2, pare.

I Etapa 2: Incremente x de uma unidade e calculey =√

x2 − n.

I Etapa 3: Repita a etapa 2 ate encontrar um valor inteiro paray , ou ate que x = n+1

2 . No primeiro caso, n tem fatores x + ye x − y ; no segundo, n e primo.

Exemplon = 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 − n1159 33, 971160 58, 931161 76, 111162 90, 091163 102, 181164 113

Logo, x = 1164 e y = 113. Os fatores procurados saox + y = 1277 e x − y = 1051.

Algoritmo de Fermat

Demonstracao: se n e primo, entao o unico valor possıvel para x ex = n+1

2 .x e y sao 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 ex + y = n. Logo,

x =1 + n

2e y =

n − 1

2

como querıamos.Obs: RSA - Se p e q sao muito proximos, entao n = p.q efacilmente fatoravel pelo algoritmo de Fermat.

Propriedade fundamental dos primos

Lema: Sejam a, b, c inteiros positivos e suponhamos que a e bsao primos entre si. Entao:

1. Se b divide o produto a.c entao b divide c .

2. Se a e b dividem c entao 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

Entao,α.a.c + β.b.c = c

Como b divide a.c pela hipotese (1) e como b divide β.b.c,entao b divide c.

2. Se a divide c , entao c = at. Mas b tambem divide c . Comomdc(a, b) = 1, pela afirmacao (1), b divide t. Logo, t = b.kpara 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 binteiros positivos. Se p divide o produto a.b, entao p divide a ou pdivide b.A demonstracao fica como exercıcio (facam!).

Unicidade

Seja n o menor inteiro positivo que admite duas fatoracoesdistintas. Podemos escrever:

n = pe11 . . . . .p

ekk = qr1

1 . . . . .qrss

onde p1 < p2 < . . . < pk e q1 < q2 < . . . < qs sao primos ee1, . . . , ek , r1, . . . , rs sao inteiros positivos.Como p1 divide n, pela propriedade fundamental dos primos p1

deve dividir um dos fatores do produto da direita. Mas um primoso pode dividir outro se forem iguais. Entao p1 = qj para algum jentre 1 e s. Logo,

n = pe11 . . . . .p

ekk = qr1

1 . . . . .qrjj . . . . .q

rss

= qr11 . . . . .p

rj1 . . . . .q

rss

Unicidade

Podemos entao cancelar p1 que aparece em ambos os lados daequacao, obtendo

m = pe1−11 . . . . .pek

k = qr11 . . . . .p

rj−11 . . . . .qrs

s

onde m e um numero menor que n que apresenta duas fatoracoesdistintas. 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 numero primo, entao√

p e umnumero irracional.

3. Livro texto: 2, 4, 5, 8, 11, 12.

Numeros primos

Ate agora:

I propriedades basicas dos numeros inteiros;

I dois algoritmos fundamentais;

Nessa aula, discutiremos metodos ingenuos para encontrar primos.

Formulas PolinomiaisConsidere o polinomio:

f (x) = an.xn + an−1.x

n−1 + . . .+ a1.x + a0

onde an, an−1, . . . , a1, a0 sao numeros inteiros e que satisfaz acondicao:

f (m) e primo, para todo inteiro positivo m

Exemplo

Seja f (x) = x2 + 1 Logo,

x f (x)1 22 53 104 17

...8 659 82

Formulas PolinomiaisTeorema: Dado um polinomio f (x) com coeficientes inteiros,existe uma infinidade de inteiros positivos m tais que f (m) ecomposto.Prova: Consideraremos f do tipo:

f (x) = a.x2 + b.x + c

Podemos supor a > 0. Suponhamos que exista m tal quef (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

Conclusao: nao existe uma formula polinomial (em umavariavel) para primos.

Formulas exponenciais: numeros de Mersenne

I Numeros de Mersenne: M(n) = 2n − 1

I Numeros perfeitos: sao iguais a metade da soma de seusdivisores. 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 numero perfeito par possui a formaacima. Ex: 6 = 22−1(22 − 1)

I O que nao se sabe: se existem numeros perfeitos ımpares.

I Pergunta: Quais sao os numeros de Mersenne primos?Exemplos: quando n = 2, 3, 5, 7, 13, 17, 19, 31, 61.... Observeque os expoentes sao todos primos, mas nem todos primosfazem parte dessa lista. Por exemplo,

M(11) = 2047 = 23.89

Formulas exponenciais: numeros de Fermat

I Numeros de Fermat: F (n) = 22n + 1

I Exemplos de numeros de Fermat primos: n = 0, 1, 2, 3, 4.F (5) = 18446744073709551617 e composto!

I Poucos primos de Fermat sao conhecidos.Ate hoje, nao sedescobriu nenhum F (n) primo com n ≥ 5.

Formulas fatoriais

p# e o produto de todos os primos menores ou iguais a p. Ex:5# = 2.3.5 = 30Se p e q sao primos sucessivos, entao

p# = q#.p

Estaremos interessados nos numeros da forma p# + 1. Emborap# + 1 nem sempre seja primo (Ex. 13# + 1 = 30031 = 59.509),podemos mostrar que nao tem nenhum fator primo menor ou iguala p. Desta forma, temos um algoritmo para calcular primo.Pergunta: qual e o problema de tal algoritmo?Observacao final: p# + 1 quase nunca e primo!

Infinidade de primos

Teorema: Existe uma infinidade de primosProva:Digamos que exista uma quantidade finita de primos:

{p1, p2, . . . , pk}

Podemos supor que esses primos estao ordenados, de modo que pk

e o maior deles. Considere o numero p#k + 1. Como vimos, esse

numero possui fator primo maior que pk . ABSURDO!

Crivo de Eratostenes

O crivo de Eratostenes e o mais antigo dos metodos para encontrarprimos.

Etapa 1: Listamos os numeros ımpares de 3 a n.

Etapa 2: Procure o primeiro numero k da lista. Risque os demaisnumeros da lista, de k em k .

Etapa 3: Repita a etapa 2 ate chegar em n.

Observacoes:

1. Podemos parar em√

n...

2. Podemos comecara riscar a partir de k2...

Crivo de Eratostenes revisado

Etapa 1: Crie um vetor v de n−12 posicoes, preenchidas com o valor 1;

faca P = 3.

Etapa 2: Se P2 > n, escreva os numeros 2j + 1 para os quais a j-esimaentrada de v e 1 e pare;

Etapa 3: Se a posicao (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 variavel T ; substitua por zeroo valor da posicao (T−1)

2 e incremente T de 2P; repita ateque 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.