Re: [obm-l] Provar uma congruencia
acho que a minha resposta tah bacana: F(n) = n^5 - 20n^4 + 40n^3 + 70n^2 + 79n - 50 para reduzir o grau dessa expressao, podemos utilizar uma outra que sabemos que eh multipla de 120: por exemplo: (n-5)(n-4)(n-3)(n-2)(n-1) esse numero eh multiplo de 120 pois eh multiplo de 5 (produto de 5 numeros consecutivos), eh multiplo de 3 (produto de tres numeros consecutivos) e eh multiplo de 8 (produto de pelo menos dois numeros pares consecutivos) (n-5)(n-4)(n-3)(n-2)(n-1) = n^5 - 15n^4 + 85n^3 - 225n^2 + 274n - 120 e portanto: F(n) = (n-5)(n-4)(n-3)(n-2)(n-1) - 5n^4 - 45n^3 + 295n^2 - 195n + 70 F(n) = (n-5)(n-4)(n-3)(n-2)(n-1) - 5( n^4 + 9n^3 - 59n^2 + 39n - 14) entao, para provar que F(n) = 0 (mod 120), para qualquer primo maior que 7, basta provar que P(n) = n^4 + 9n^3 - 59n^2 + 39n - 14 = 0 (mod 24), para qualquer primo maior que 7. agora vamos utilizar o mesmo procedimento: sabemos que o produto de quatro numeros consecutivos eh multplo de 24, vamos usar a expressao n(n+1)(n+2)(n+3) = n^4 + 6n^3 + 11n^2 + 6n portanto, P(n) = n(n+1)(n+2)(n+3) + 3n^3 - 70n^2 + 33n - 14 entao, para provar que F(n) = 0 (mod 120) para qualquer primo maior que 7, basta provar que Q(n) = 3n^3 - 70n^2 + 33n - 14 = 0 (mod 24) para qualquer primo maior que 7. se o numero é primo e maior que 7, entao ele é ímpar e pode ser escrito como n = 2k+1 Q(2k+1) = 3[2k + 1]^3 - 70[2k + 1]^2 + 33[2k + 1] - 14 = 4[6k^3 - 61k^2 - 49k - 12] portanto, basta provar que 6k^3 - 61k^2 - 49k - 12 é multiplo de 6 multiplo de 2 percebos que eh, pois se k for impar teremos: par - impar - impar - par = par se k for par, teremos: par - par - par - par = par entao, soh falta provar que é multiplo de 3, o que será se 61k^2 + 49k o for. caso k = 3p, 61k^2 + 49k = k(61k + 49) = 3p(61k + 49), que eh multiplo de 3 k = 3p + 1 faria com que o numero n fosse igual a 3(3p + 1), o que contraria a hipótese de que n é primo e maior que 7 caso k = 3p + 2, 61k^2 + 49k = 3[183p^2 + 293p + 114], que eh multiplo de 3 como soh falatava provar isso, a tese estah provada On Wed, Oct 13, 2004 at 07:19:28PM -0300, Demetrio Freitas 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) > > > > > > > ___ > Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador agora! > http://br.acesso.yahoo.com/ > = > 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 > = = 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 =
Re: [obm-l] Provar uma congruencia
Ok, Cláudio. Obrigado, Demétrio --- Claudio Buffara <[EMAIL PROTECTED]> escreveu: > on 13.10.04 20:19, Demetrio Freitas at > [EMAIL PROTECTED] > 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 > = > ___ Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador agora! http://br.acesso.yahoo.com/ = 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 =
Re: [obm-l] Provar uma congruencia
on 13.10.04 20:19, Demetrio Freitas at [EMAIL PROTECTED] 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 =
[obm-l] Provar uma congruencia
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) ___ Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador agora! http://br.acesso.yahoo.com/ = 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 =
