[obm-l] Re:[obm-l] Número de Carmichael

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

 

De:	owner-obm-l@mat.puc-rio.br

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.