[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Olimpíadas ao redor do mundo....



É isso aí. A mesma solução, só que em linguagem de congruências.
 
De fato, com congruências fica até mais fácil mostrar o seguinte:
 
Para todo inteiro a > 2, existe um primo p tal que:
1 + 2a + 3a^2 + ... + pa^(p-1) é composto (e múltiplo de p).
 
Será que pra a = 2 também vale?
 
Um abraço,
Claudio.
 
 
----- Original Message -----
Sent: Thursday, May 29, 2003 3:02 PM
Subject: [obm-l] Re: [obm-l] Re: [obm-l] Olimpíadas ao redor do mundo....

Cláudio, eu tive a mesma idéia que você, mas havia expressado de outra forma...
 
seja p um primo tal que a ~ 1 (mod p)
 
a menos de a = 2, esse primo existe, basta pegar um primo que divida a - 1 (como vc bem notou, esse primo existe sempre para a > 2).
 
agora note que
1 + a + ... + a^(p-1) ~ 1 + 1 + ... + 1 = p ~ 0 (mod p)
ou seja p divide o somatório, como sabemos que p < 1 + a + ... + a^(p-1), temos que o número é composto.
 
 
[ ]'s
----- Original Message -----
Sent: Thursday, May 29, 2003 12:58 PM
Subject: [obm-l] Re: [obm-l] Olimpíadas ao redor do mundo....

E aí rapaziada!! Tudo bem??
Alguém ai tem disposição para pensar nesse???
   Mostre que para todo inteiro a>1, existe um número primo p tal que 1+a+a^2+...+a^(n-1) é composto.
      Valeu.....
               Crom
 
*****
 
Oi, Crom:
 
Imagino que você queira dizer 1 + a + ... + a^(p-1) é composto.
 
Se esse for o caso, teremos:
 
a = 2 ==> 1 + 2 + 2^2 + ... + 2^10 = 2^11 -1 = 23*89 ==> composto.
 
Agora, seja a um inteiro qualquer >= 3.
 
Seja p o menor primo que divide a - 1 (como a - 1 >= 2, a existência de um tal primo estará assegurada - foi por isso que eu separei o caso a = 2).
Então, p também irá dividir a^2 - 1, a^3 - 1, ..., a^(p-1) - 1.
 
Só que:
(a - 1) + (a^2 - 1) + ... + (a^(p-1) - 1) =
(1 - 1) + (a - 1) + (a^2 - 1) + ... + (a^(p-1) - 1) =
(1 + a + a^2 + ... + a^(p-1)) - p, ou seja:
 
1 + a + .... + a^(p-1) = p + (a - 1) + (a^2 - 1) + ... + (a^(p-1) - 1)
 
Como p divide cada parcela do lado direito (e, portanto, sua soma), concluímos que p também dividirá o lado esquerdo.
 
Como p divide a - 1, teremos que p <= a - 1 < 1 + a <= 1 + a + ... + a^(p-1).
Logo, 1 + a + ... + a^(p-1) tem pelo menos um outro fator primo além de p ==>
1 + a + ... + a^(p-1) é composto.
 
Um abraço,
Claudio.