Re: [obm-l] Provar uma congruencia

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 13.10.04 20:19, Demetrio Freitas at demetrio_freitas_2002_10@yahoo.com.br
wrote:

> Ola,
> 
> Gostaria de provar uma congruencia.
> 
> Dado F(n) = n^5 -20*n^4 +40*n^3 +70*n^2 +79*n -50
> Prove que F(n) = 0 (mod 120), se n for primo > 7.
> (Onde = denota conguente)
> 
> Por exemplo:
> F(11) = -69240 = -120 * 577
> F(19) = 170760 =  120 * 1423
> F(97) = 6853927800 = 120 * 57116065
> F(563) = 54562015773960 = 120 * 454683464783
> 
> Porem:
> F(15) = -101240 -> nao divisivel por 120
> F(129) = 30271636600 -> nao divisivel por 120
> F(597) = 73303331579800 -> nao divisivel por 120
> 
> 
> Qual caminho usar?
> 
> Obrigado,
> 
> Demetrio
> 
> OBS:
> Naturalmente a condição eh "se n primo" e não "sse (se
> e somente se)", pois ha muitos n compostos onde F(n)
> = 0 (mod 120)
> 
>
A primeira coisa eh decompor 120 em fatores primos:
120 = 2^3*3*5.

Agora, basta provar que F(n) == 0 mod 3, 5 e 8 para n primo > 7.

Para cada um dos 3 modulos, a ideia eh reduzir F(n) usando propriedades das
congruencias e o pequeno teorema de Fermat.

Mod 3:
F(n) = n^5 -20*n^4 +40*n^3 +70*n^2 +79*n - 50 ==>
F(n) == n + n^2 + n + n^2 + n + 1 ==>
F(n) == 2*n^2 + 1

Se n for multiplo de 3, entao F(n) == 1 (mod 3).
No entanto, todos os primos > 7 sao impares e nao multiplos de 3, de forma
que os seus quadrados sao todos == 1 (mod 3).
Logo, para n primo > 7, 2*n^2 + 1 == 2*1 + 1 == 0 (mod 3)

***

Mod 5:
F(n) = n^5 -20*n^4 +40*n^3 +70*n^2 +79*n - 50 ==>
F(n) = n - 0 + 0 + 0 - n + 0 ==>
F(n) == 0

Ou seja, F(n) eh multiplo de 5 para qualquer inteiro n.

***

Mod 8:
F(n) = n^5 -20*n^4 +40*n^3 +70*n^2 +79*n - 50 ==>
F(n) == n^5 + 4*n^4 + 0 - 2*n^2 - n - 2 ==>
F(n) == n*n^4 + 4*n^4 - 2*n^2 - n - 2

O quadrado de cada impar eh == 1 (mod 8). Assim, para n impar, teremos:
F(n) == n*1 + 4*1 - 2*1 - n - 2 == 0 (mod 8).

Ou seja, para n impar e nao multiplo de 3, F(n) == 0 (mod 3*5*8).
Em particular, para cada primo n > 7, F(n) eh divisivel por n.

Repare que, no seu exemplo acima, 15, 129 e 597 sao todos multiplos de 3.

[]s,
Claudio.


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================