Re: é o chato novamente

["José Paulo Carneiro" <jpcarneiro@xxxxxxxxxxxxxxx>]

Basta observar que 2 eh congruo de -1 modulo 3.
Entao 2^n eh congruo de (-1)^n, e sua diferenca eh
congrua de 0.
JP

-----Mensagem original-----
De: Benjamin Hinrichs <hinsoft@sinos.net>
Para: obm-l <obm-l@mat.puc-rio.br>
Data: Sábado, 1 de Janeiro de 2000 19:30
Assunto: é o chato novamente


>Faz alguns dias (não saberia dizer quantos) que entrei no icq e vi que
>estava cheio de gente da lista, abrimos um chat e conversamos um pouco.
>Surgiu entretanto um problema no meio: prove que 2^n - (-1)^n  mod 3 =
>0, ou seja, que 2^n - (-1)^n é divisível por 3, dado n E N (é natural),
>n > 0.
>Sugiro que tentem provar e depois ver a minha prova que segue abaixo.
>
>Usei para isto o seguinte teorema (fácil de provar):
>a^k -1 = (a^(k-1) + a^(k-2) + ... + a^2 + a^1 + a^0)*(a - 1)
>
>Se n é par então pode ser denominado 2k (nada de 2000, parem de pensar
>no bug). Portanto 2^2k -(-1)^2k = 4^k -(1)^k = 4^k - 1 = (4^(k-1) +
>4^(k-2) + ... + 4^2 + 4^1 + 4^0)*(4 - 1) = (4^(k-1) + 4^(k-2) + ... +
>4^2 + 4^1 + 4^0)*3 (o que é divisível por 3)
>Se n é ímpar então ele pode ser escrito da forma 2k + 1. Portanto
>2^(2k+1) -(-1)^(2k+1) = 2*2^2k -(-1)*(-1)^2k = 2*4^k + 1 = 4^k - 1 + 4^k
>- 1 + 3 (já que 4^k - 1 já foi provado ser divisível por três, 2(4^k -1)
>+ 3 também é)
>
>Deve haver uma prova ridiculamente simples para este problema. Meu pai
>disse que o enunciado do problema é muito bom, a prova é fácil. Bem, eu
>ao menos demorei algum tempinho para descobrir que 1 = - 1 - 1 + 3...
>
>Grande abraço,
>
>Benjamin Hinrichs
>
>