| De: | [EMAIL PROTECTED] |
| Para: | obm-l@mat.puc-rio.br |
| Cópia: |
| Data: | Tue, 26 Sep 2006 17:56:35 -0300 |
| Assunto: | [obm-l] Número de Carmichael |
> Olá pessoal, gostaria que alguém demonstrasse pra mim ou me indicasse onde
> posso encontrar a demonstração do seguinte fato:
>
> Se t é tal que 6t+1, 12t+1 e 18t+1 são todos primos, então o seu produto é
> um número de Carmichael.
>
n = (6t+1)(12t+1)(18t+1) é obviamente composto.
n - 1 = 1296t^3 + 396t^2 + 36t == 0 (mod 36t)
Seja a um inteiro primo com n.
Então a é primo com 6t+1, 12t+1 e 18t+1.
Pequeno Fermat ==>
a^(6t) == 1 (mod 6t+1) ==> a^(36t) == 1 (mod 6t+1)
a^(12t) == 1 (mod 12t+1) ==> a^(36t) == 1 (mod 12t+1)
a^(18t) == 1 (mod 18t+1) ==> a^(36t) == 1 (mod 18t+1)
Logo, a^(36t) == 1 (mod n)
Como 36t divide n-1, temos a^(n-1) == 1 (mod n)
Como n é composto, n é um número de Carmichael.
[]s,
Claudio.
