Upload
duongtruc
View
223
Download
0
Embed Size (px)
Citation preview
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Teoria de Numeros ComputacionalLCC
M. Lurdes TeixeiraDMA-ECUM
2◦ semestre de 2011/2012
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Teoria de Numeros e uma area da Matematica cujo objetivo eestudar propriedades dos numeros inteiros relacionadas coma divisibilidade, tais como: paridade, primalidade, fatorizacao,multiplicatividade, aditividade, etc..
Aplicacoes recentes ...
em computacao e em tecnologias de informacao.
Areas atuais de aplicacao:
Fısica, Quımica, Biologia, Computacao, Criptografia, Comuni-cacao Digital, Musica, ...
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Temas centrais
Primalidade e Fatorizacao
Aritmetica Modular
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Definicao
Dados numeros inteiros a e b diz-se que b divide a se existek inteiro tal que a = b · k . Em tal caso escreve-se b | a, casocontrario escreve-se b - a.
Definicao
Um numero inteiro p > 1 diz-se um numero primo se os unicosdivisores inteiros positivos sao 1 e p. Se p nao e primo entao pdiz-se um numero composto.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Exemplo 1 - Algoritmo da divisao
Proposicao
Dados numeros inteiros a e b com b 6= 0 existem e sao unicosos inteiros q e r tais que 0 ≤ r < |b| e
a = b · q + r .
Graficamente ...
caso a > 0 e b > 0
− − − − −|0
|a
|b
|2b
|3b · · ·
|qb
|(q + 1)b
caso a > 0 e b < 0
− − − − −|0
|a
|−b
|−2b
|−3b · · ·
|qb
|(q − 1)b
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
caso a < 0 e b > 0
− − − − −|a
|0
|−b
|−2b
|−3b· · ·
|(q + 1)b
|qb
caso a < 0 e b < 0
− − − − −|a
|0
|b
|2b
|3b· · ·
|(q − 1)b
|qb
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Definicao
Sejam a, b e m inteiros. Diz-se que a e congruente com bmodulo m se m | a− b.
Facilmente se verifica que se a e congruente modulo m com b,entao o resto da divisao de a por m e igual ao resto da divisaode b por m.
Notacao:Se a e congruente com b modulo m escreve-sea ≡ b(mod m).a mod m representa o resto da divisao de a por m.A expressao a 6≡ b(mod m) significa que m - a− b.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Proposicao
Seja m um inteiro. A relacao congruente modulo m definida noconjunto dos numeros inteiros e uma relacao de equivalencia.
Proposicao
Sejam a, b, c, d e m inteiros. Se a ≡ b (mod m) e c ≡d (mod m), entao
1 a + c ≡ b + d (mod m);2 ac ≡ bd (mod m).
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Exemplo 2 - Algoritmo de Euclides
Definicao
Dados a e b inteiros nao ambos nulos, chama-se maximo divi-sor comum de a e b ao maior inteiro que divide a e b, o qual serepresenta por m.d.c.(a,b).
Proposicao
Dados a e b inteiros, se q e r sao inteiros tais que a = b ·q + r ,entao m.d.c.(a,b) = m.d.c.(b, r).
O algoritmo de Euclides tem por objetivo o calculo do m.d.c. dedois inteiros e baseia-se na proposicao anterior.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
486 = 2× 218+50→ m.d.c.(486,218)=m.d.c.(218,50)218 = 4× 50 +18→ =m.d.c.(50,18)
50 = 2× 18 +14→ =m.d.c.(18,14)18 = 1× 14 +4 → =m.d.c.(14,4)14 = 3× 4 +2 → =m.d.c.(4,2)
4 = 2× 2 +0 → =m.d.c.(2,0)=2
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Algoritmo de EuclidesEntrada: a e b.
1 x = a, y = b.2 Se y = 0, entao m.d.c.(a,b) = x e terminar.3 r ← resto da divisao de x por y ,
x ← y ,y ← r ,
voltar a 2.Saıda: m.d.c.(a,b).
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Definicao
Dados a e b inteiros nao nulos, chama-se mınimo multiplo co-mum de a e b ao menor inteiro positivo que e divisıvel por a epor b, o qual se representa por m.m.c.(a,b).
Funcoes uteis no Mathematica:Quotient, QuotientRemainder, Mod, Divisible, GCD, LCM.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Exemplo 3 - Algoritmo de Euclides estendido
Teorema - Igualdade de Bezout
Dados a e b inteiros nao ambos nulos, seja d = m.d.c.(a,b).Entao, existem inteiros x e y tais que
d = ax + by .
O algoritmo de Euclides estendido tem por objetivo o calculodo m.d.c. de dois inteiros a e b, bem como de inteiros x e yreferidos na igualdade de Bezout.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
m.d.c.(486,218) = 2
486 = 2× 218+50 → = 486× 48 + 218× (−107)
218 = 4× 50 +18 →...
50 = 2× 18 +14 →18 = 1× 14 +4 → = 14− 3× (18− 14× 1)14 = 3× 4 +2 → 2 = 14− 3× 4
4 = 2× 2 +0
x = 48 y = −107
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Considere-se a equacao linear nas incognitas x e y ,
486x + 218y = 2.
Pelo exposto existe pelo menos uma solucao que e
x = 48 e y = −107.
Em geral, qualquer par do tipo
(48 + k218
2,−107− k
4862
)
e solucao da equacao.
Funcoes uteis no Mathematica:ExtendedGCD, FindInstance, Reduce
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
A sequencia de restos calculada no algoritmo de Euclides e dotipo:
r−2 = ar−1 = b
ri = ri−2 − qi · ri−1 para i ≥ 0,
o que permite concluir que
r−2 = a · 1+b · 0r−1 = a · 0+b · 1e que
seri =a · s + b · t ,ri+1 =a · s′ + b · t ′,
entaori+2 =a · (s − qi+2s′) + b · (t − qi+2t ′).
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Algoritmo de Euclides estendidoEntrada: a e b.
1 r = a, s = 1, t = 0,r1 = b, s′ = 0, t ′ = 1.
2 Se r1 = 0, entao m.d.c.(a,b) = r1, x = s′, y = t ′, terminar.3 q ← quociente da divisao entre r e r1,
r2← resto da divisao entre r e r1.4 Se r2 = 0, entao m.d.c.(a,b) = r1, x = s′, y = t ′, terminar.5 nr1 ← r2, ns ← s − qs′, nt ← t − qt ′,
r ← r1, s ← s′, t ← t ′,r1 ← nr1, s′ ← ns, t ← nt .
6 Voltar a 2.Saıda: m.d.c.(a,b), x , y .
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Alguns Algoritmos Basicos
Exercıcios1 Resolva as seguintes equacoes diofantinas:
1 144x + 34y = 20,2 39x + 51y = 7,3 63x − 37y = 3,4 119x − 29y = 8.
2 Quantas solucoes positivas existem para a equacao144x + 34y = 20?
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Fatorizacao em primos
Teorema Fundamental da AritmeticaTodo o numero inteiro n maior do que 1 escreve-se de formaunica como produto de numeros primos, a menos da ordemdos fatores.
Fatorizacao de n > 1 em primos:
n = pe11 · · · · · p
ekk
onde k ≥ 1, pi representa um numero primo e ei ∈ N paraqualquer 1 ≤ i ≤ k .
ProblemaComo calcular a fatorizacao em numeros primos de um numerointeiro maior do que 1 ?
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Fatorizacao em primos
Algoritmo de fatorizacao por ensaios de divisao sucessivos
Entrada: n.
1 f = (), d = 2.
2 Se n = 1, entao terminar.
3 Se d - n, entao d ← d + 1.
4 Se d | n, entao
q ← quociente da divisao de n por d ,f ← f · (d), n← q.
5 Voltar a 2.
Saıda: f lista ordenada dos divisores primos.
ExercıcioTeste o algoritmo para n = 2,5,16,121,1650.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Fatorizacao em primos
Dois pontos fracos do algoritmo:
tentativas de divisao por numeros nao primos acerca dosquais ja ha informacao suficiente para concluir que naodividem n,se n e primo sao efetuadas divisoes por todos os primosmenores do que n.
Proposicao
Um numero inteiro n > 2 e um numero composto se e so se edivisıvel por um numero primo menor ou igual a
√n.
Como melhorar?1 escolher os divisores de entre uma lista de numeros
primos;2 procurar fatores inferiores a
√n.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Fatorizacao em primos
O crivo de Eratostenes e uma lista que contem todos osnumeros primos menores do que um dado numero inteiron > 2.
Algoritmo de construcao do crivoEntrada: n > 2.
1 P = (pi)i = (2,3,4,5,6,7, . . . ,n), i = 1.2 Se pi >
√n, entao terminar.
3 P ← sequencia que resulta de P por se retirar oselementos da forma kpi para 2 ≤ K ≤ n
pi.
4 i ← i + 1, voltar a 2..Saıda: lista ordenada P dos numeros primos menores ouiguais a n.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Fatorizacao em primos
ExercıcioTestar o algoritmo para n = 28.
P = (2,3,4,5,6, . . . ,28)
final da 1a iteracao - P = (2,3,5, . . . ,2n + 1, . . . ,25,27);final da 2a iteracao - P = (2,3,5,7,11,13,17,19,23,25);final da 3a iteracao - P = (2,3,5,7,11,13,17,19,23).
O processo termina na 3a iteracao, dado que√
28 ' 5,29.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Fatorizacao em primos
Algoritmo de fatorizacao por ensaios de divisao sucessivos
Entrada: n > 2 e P = (pi)i≤m uma lista de primos.
1 f = (), e = 0, i = 1, d = p1.
2 Se d >√
n, entao f ← f · ({n,1}) e terminar.
3 Se d |n, entaoe← e + 1, n← quociente da divisao de n por d , repetir 3..
4 Se e 6= 0, entao f ← f · ({d ,e}).5 Se n = 1, entao terminar.
6 i ← i + 1.
7 Se i ≤ |P|, entao d ← pi , e = 0, voltar a 2..
8 Terminar com mensagem de que f pode nao ser a listacompleta de fatores primos de n.
Saıda: f lista ordenada dos menores divisores primos e respetivosexpoentes que ocorrem na fatorizacao de n.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Fatorizacao em primos
ExercıcioTeste o algoritmo paran = 2,11,121,122,1650,2346,11858,22374.
Funcoes uteis no Mathematica:FactorInteger, Divisors, PrimeQ, Prime, NextPrime.
ExercıciosSejam m e n inteiros positivos.
1 Mostre que se m nao e um quadrado perfeito, entao√
m eirracional.
2 Determine em que condicoes m1n e racional.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Metodo de fatorizacao de Fermat
O metodo de fatorizacao de Fermat baseia-se na represen-tacao de um numero ımpar composto como sendo a diferencade dois quadrados:
n = p · q ⇔ n =
(p + q
2
)︸ ︷︷ ︸
a
2 −(
p − q2
)︸ ︷︷ ︸
b
2 ⇔ n = a2 − b2
Como p e q sao ımpares entao p+q2 , p−q
2 ∈ Z.
Notar que conhecer p e q e equivalente a conhecer a e b.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Metodo de fatorizacao de Fermat
Para a partir de um inteiro ımpar n determinar os valores de ae b nas condicoes acima deve proceder-se da seguinte forma:
1 Escolher para valor inicial de a o menor inteiro tal quea2 − n ≥ 0.
2 Incrementar sucessivamente o valor de a ate que a2 − n2
seja um quadrado perfeito.
Assim,a + b e o menor fator de n maior ou igual a
√n.
a− b e o maior fator de n menor ou igual a√
n.
|0
|√n
|a + b
|a− b
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Metodo de fatorizacao de Fermat
Exemplos
1 Seja n = 2401= 492. n e ımpar e a primeira escolha para aseria a = 49 e resultava o valor para b2 = 0 que e um quadradoperfeito. Logo
p = a + 0 = 49 e q = a− 0 = 49.
2 Seja n = 2303= 47 · 49. n e ımpar e a primeira escolha para aseria a = 48 e resultava o valor para b2 = 1 que e um quadradoperfeito. Logo
p = a + 1 = 49 e q = a− 1 = 47.
3 Seja n = 2352= 48 · 49. n e par, pelo que por divisoes suces-sivas de n por 2 obtem-se n = 24 · 147 e a primeira escolhapara a seria a = 13 e resultava o valor para a2 − n = 22 quenao e um quadrado perfeito. Na etapa seguinte considera-sea = 14 e resultava o valor para b2 = a2 − n = 49 que e umquadrado perfeito. Logo
p = a + 7 = 21 e q = a− 7 = 7,e obtem-se a fatorizacao n = 24 · 7 · 21.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Metodo de fatorizacao de Fermat
Algoritmo de fatorizacao de Fermat
Entrada: n > 2 e max .
1 r ← 0.
2 Enquanto n mod 2 = 0 fazer
n← n2 , r ← r + 1.
3 i ← 1, a← p√
nq, b2← a2 − n.
4 Enquanto√
b2 6∈ N0 e i ≤ max , fazer
a← a + 1, b2← a2 − n, i ← i + 1.
5 p ← a +√
b2, q ← a−√
b2.
Saıda: 2r , p e q.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Metodo de fatorizacao de Fermat
Notas1 Um quadrado perfeito tem como algarismo das unidades
0, 1, 4, 5, 6 ou 9.2 Conhecendo a2 pode calcular-se (a + 1)2 acrescentando
2a + 1.3 No caso geral o algoritmo efetua um numero de itera-
coes igual ap + q
2︸ ︷︷ ︸a
− p√
nq+ 1.
4 O caso em que o algoritmo atinge um numero maximo depassos ocorre quando n e primo. Em tal caso o numerode passos e de n+1
2 − p√
nq+ 1.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Metodo de fatorizacao de Fermat
Exercıcios
1 Mostre que o ultimo dıgito de um quadrado perfeito e 0, 1, 4, 5,6 ou 9.
2 Mostre que:
1 se a e inteiro par entao a2 ≡ 0 (mod 4),2 se a e inteiro ımpar entao a2 ≡ 1 (mod 4),3 se a e inteiro ımpar entao a2 ≡ 1 (mod 8).
3 Determine os restos possıveis de um quadrado perfeito quandodividido por 16.
4 Utilizando o metodo de fatorizacao de Fermat fatorize osnumeros: 143, 145, 517, 43, 101, 2279, 4697.
5 Mostre que se n mod 4 = 2 entao n nao pode ser escrito comouma diferenca de quadrados.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Metodo de fatorizacao de Fermat
Exercıcios1 Implemente no Mathematica o metodo de fatorizacao de
Fermat acrescentando alguns melhoramentos.2 Determine fatores dos numeros
11413,8051,11021,3200399,408508091,25345192.
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Metodo de fatorizacao de Fermat
Para melhorar o desempenho deste metodo e usual combina-locom outros metodos. A situacao mais elementar e combinar como metodo dos ensaios de divisoes sucessivas.
Exemplo
n = 2345678917
Entao o valor inicial para a seria 48433. Aplicando o metodo defatorizacao de Fermat obtem-se sucessivamente
a 48433 48434 48435 48436 . . .b2 76572 173439 270308 367179 . . .
a− b 48156.2 48017.5 47915.1 47830.01 . . .a + b 48709.7 48849.5 48952.9 49041.95 . . .
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC
Introducao Divisibilidade e Numeros Primos Distribuicao dos Numeros Primos
Metodo de fatorizacao de Fermat
a 48433 48434 48435 48436 . . .
b2 76572 173439 270308 367179 . . .a− b 48156.2 48017.5 47915.1 47830.01 . . .a + b 48709.7 48849.5 48952.9 49041.95 . . .
|0
|√n
|a + b
|a− b
M. Lurdes Teixeira DMA-ECUM Teoria de Numeros Computacional LCC