Re: [obm-l] Sequencia de numeros compostos

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

 

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

Para:

obm-l@mat.puc-rio.br

Cópia:

Data:

Fri, 1 Apr 2005 19:56:12 -0300 (BRST)

Assunto:

Re: [obm-l] Sequencia de numeros compostos

> Da Eureka 18, p?gina 61:

>

> Voc? sabia?

> Que existem infinitos inteiros positivos ?mpares k tais que k.2^n+1 ?

> composto para todo n ?

> Tais inteiros k s?o chamados n?meros de Sierpinski.

>

> Exerc?cio: Prove que 78557 ? um n?mero de Sierpinski, e que existem

> infinitos n?meros de Sierpinski a partir das congru?ncias

> 78557.2^0+1=0 (mod 3)

> 78557.2^1+1=0 (mod 5)

> 78557.2^7+1=0 (mod 7)

> 78557.2^11+1=0 (mod 13)

> 78557.2^3+1=78557.2^39+1=0 (mod 73)

> 78557.2^15+1=0 (mod 19)

> 78557.2^27+1=0 (mod 37).

>

>

> Abra?os,

> Gugu

>

 

2^2 == 1 (mod 3) ==> 78557*2^(2k) + 1 == 0 (mod 3)

2^4 == 1 (mod 5) ==> 78557*2^(4k+1) + 1 == 0 (mod 5)

2^3 == 1 (mod 7) ==> 78557*2^(3k+7) + 1 == 0 (mod 7)

2^12 == 1 (mod 13) ==>  78557*2^(12k+11) + 1 == 0 (mod 13)

2^18 == 1 (mod 19) ==> 78557*2^(18k+15) + 1 == 0 (mod 19)

2^36 == 1 (mod 37) ==> 78557*2^(36k+27) + 1 == 0 (mod 37)

2^9 == 1 (mod 73) ==> 79557*2^(9k+3) + 1 == 0 (mod 73)

 

Também é verdade que todo inteiro n é da forma:

2k, 4k+1, 3k+7 (3k+1), 12k+11, 18k+15, 36k+27 ou 9k+3.

 

n é par ==> n = 2k;

 

n é ímpar ==> n = 4k+1 ou 4k+3.

n = 4k+1 está coberto.

Logo, resta tratar o caso em que n = 4k+3

 

n = 4k+3 ==> n == 3, 7, 11, 15, 19, 23, 27, 31 ou 35 (mod 36)

 

Mas sabemos que:

n = 3k+1 ==> n == 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31 ou 34 (mod 36)

n = 12k+11 ==> n == 11, 23 ou 35 (mod 36)

n = 18k+15 ==> n == 15 ou 33 (mod 36)

n = 36k+27 ==> n == 27 (mod 36)

n = 9k+3 ==> n == 3, 12, 21 ou 30 (mod 36)

Ou seja, cada um dos restos (mod 36) correspondentes a n = 4k+3 está coberto por um das cinco alternativas acima.

 

Em suma, para cada n, existe m em {3, 5, 7, 13, 19, 37, 73} tal que:

78557*2^n + 1 == 0 (mod m) ==>

para cada n, 78557*2^n + 1 é composto.

 

***

 

Seja N = 2*3*5*7*13*19*37*73

 

N é par e é tal que:

N == 0 (mod m), para todo m em {3, 5, 7, 13, 19, 37, 73} ==>

 

para todo k inteiro, kN == 0 (mod m), para cada m acima ==>

 

(78557 + kN).2^0+1=0 (mod 3)

(78557 + kN).2^1+1=0 (mod 5)

(78557 + kN).2^7+1=0 (mod 7)

(78557 + kN).2^11+1=0 (mod 13)

(78557 + kN).2^3+1= 0 (mod 73)

(78557 + kN).2^15+1=0 (mod 19)

(78557 + kN).2^27+1=0 (mod 37).

 

Logo, repetindo a análise acima, concluímos que 78557 + kN é um número de Sierpinski para todo k inteiro e positivo ==>

existe uma infinidade de tais números.

 

 

[]s,

Claudio.