aula07_2010

Prévia do material em texto

A´lgebra A - Aula 07
Pseudoprimos
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Pseudoprimos
Teorema de Fermat: se p e´ primo enta˜o ap ≡ a (mod p) para todo
a inteiro.
Ou seja, se existe b tal que bn 6≡ b (mod n) enta˜o n e´ composto.
Suponhamos n ı´mpar.
Observe que podemos tomar 1 < b < n − 1, uma vez que qualquer
inteiro e´ congruente a um inteiro no intervalo de 0 a n − 1 e
bn ≡ b (mod n) trivialmente para b = 0, 1, n − 1
Pseudoprimos
Teste de Fermat: Se n, b sa˜o nu´meros inteiros, n > 0 e
1 < b < n − 1, tais que bn−1 6≡ 1 (mod n), enta˜o n e´ composto.
O nu´mero b e´ conhecido como uma testemunha do fato de n ser
composto.
Com o teste acima, podemos determinar se um nu´mero e´
composto ou na˜o sem fatora´-lo!
Exemplo
Vimos que
R(n) =
10n − 1
9
= 11111 . . . 1︸ ︷︷ ︸
n vezes
e´ composto se n e´ composto. Mas e se n e´ primo?
Utilizando o teste de Fermat, vemos que, por exemplo,
2R(229)−1
tem um resto que na˜o e´ congruente a 1 mo´dulo R(229). Logo
R(229) na˜o e´ primo.
Pseudoprimos
Pergunta: o teste de Fermat e´ um procedimento de decisa˜o?
Resposta: n composto ⇒ existe p primo, 1 < p < n − 1 tal que
p|n. Logo, mdc(p, n) = p 6= 1 e portanto p na˜o e´ invers´ıvel
mo´dulo n. Desta forma, pn−1 6≡ 1 (mod n).
E´ claro que esse na˜o e´ um me´todo eficiente para testar primalidade
uma vez que e´ um me´todo de exausta˜o.
Outra pergunta: se n e´ um nu´mero ı´mpar tal que
bn−1 ≡ 1 (mod n)
para algum 1 < b < n − 1 enta˜o n e´ primo?
Pseudoprimos
Resposta : na˜o. Exemplo: 2340 ≡ 1 (mod 341) mas 341 = 11.31
na˜o e´ primo!
Pseudoprimo n para a base b: nu´mero ı´mpar e composto tal que
bn−1 ≡ 1 (mod n)
Exemplo: Existem 50.847.534 primos entre 1 e 109; existem
apenas 5597 pseudoprimos na base 2 e 1272 pseudoprimos para as
bases 2 e 3.
Nu´meros de Carmichael
Vimos que na˜o existem nu´meros que sejam pseudoprimos para
todas as bases. Mas pode ocorrer que um nu´mero composto n seja
pseudoprimo para todas as bases b tais que mdc(b, n) = 1.
Dizemos que um nu´mero composto ı´mpar e´ um nu´mero de
Carmichael se
bn ≡ b (mod n) para todo 1 < b < n − 1.
Exemplo
O menor nu´mero de Carmichael e´ 561. Para provar isso no la´pis,
precisar´ıamos verificar que
b561 ≡ b (mod 561) para todo b = 2, . . . , 559
Mas observe que 561 = 3.11.17. Logo se mostrarmos que
b561 − b
e´ divis´ıvel por 3, 11 e 17 enta˜o temos que
561|b561 − b.
Exemplo
Verificando que b561 ≡ b (mod 17):
I Se 17|b enta˜o b561 ≡ b ≡ 0 (mod 17)
I Se 17 6 | b enta˜o b16 ≡ 1 (mod 17). Logo,
b561 ≡ (b16)35.b ≡ b (mod 17)
Observac¸o˜es importantes:
1. O resto da divisa˜o de 561 por 2, 10 e 16 e´ 1.
2. 561 e´ um produto de primos distintos!
Nu´meros de Carmichael
Teorema de Korselt: Um inteiro positivo ı´mpar n e´ um nu´mero
de Carmichael se, e somente se, cada fator primo p de n satisfaz as
seguintes condic¸o˜es:
1. p2 na˜o divide n;
2. p − 1 divide n − 1.
Nu´meros de Carmichael
Prova: (⇐) Seja p um fator primo de n. Vamos provar que (1) e
(2) implicam:
bn ≡ b (mod p) ∀b ∈ Z
De fato, se b e´ divis´ıvel por p enta˜o ambos os membros da
equivaleˆncia sa˜o congruentes a zero. Se na˜o, pelo teorema de
Fermat temos:
bp−1 ≡ 1 (mod p)
Pela condic¸a˜o (2) do teorema, n − 1 = (p − 1).q para algum q.
Logo,
bn ≡ (bp−1)q.b ≡ b (mod p).
Por (1), temos que n = p1 . . . pk com p1 < p2 < . . . < pk . Logo,
bn ≡ b (mod n)
Nu´meros de Carmichael
(⇒) Seja n um nu´mero de Carmichael e suponhamos que exista p
primo tal que p2|n. Escolha b = p. Enta˜o:
pn − p = p(pn−1 − 1)
Mas p na˜o divide pn−1 − 1, logo p2 na˜o pode dividir pn − p.
Portanto, n na˜o pode dividir pn − p. Em outras palavras, pn 6≡ p
(mod n). Absurdo.
Restante da demonstrac¸a˜o: cap´ıtulo 10...
Nu´meros de Carmichael
Observac¸o˜es:
I Para verificar que um nu´mero e´ de Carmichael usando o
teorema acima necessitamos fatora´-lo...
I Muitos nu´meros de Carmichael possuem fatores primos
pequenos!
I Existem infinitos nu´meros de Carmichael.
I Entre 1 e 109 existem 50.847.534 primos e 646 nu´meros de
Carmichael.