Re: [obm-l] Problemas de Teoria de Numeros

[Adroaldo Munhoz <amunhoz@xxxxxxxxx>]

Por que a^fi(b)*b^fi(a) == 0 (mod ab) ?


claudio.buffara wrote:

>  
> *De:* 	owner-obm-l@mat.puc-rio.br
>
> *Para:* 	obm-l@mat.puc-rio.br
>
> *Cópia:* 	
>
> *Data:* 	Wed, 28 Sep 2005 07:46:35 -0300
>
> *Assunto:* 	[obm-l] Problemas de Teoria de Numeros
>
> > Pessoal, estou com alguns problemas de Teoria de Números que não sei
> > como resolver.
> >
> > 1. Provar que para p primo (p-1)!=p-1 (mod 1+2+3+...+(p-1))
>  
> módulo = p(p-1)/2
> Obviamente, (p-1)! == p-1 ( == 0 ) (mod (p-1)/2)
> T. de Wilson ==> (p-1)! == p-1 (mod p)
> Logo, (p-1)! == p-1 (mod p(p-1)/2).
>  
> > 2. Encontrar o máximo divisor comum de (p-1)!-1 e p!, com p primo.
>  
> p divide ambos e, além disso, p^2 não divide p!.
> Qualquer primo maior do que p não divide p!
> Qualquer primo menor do que p não divide (p-1)! - 1.
> Logo, mdc = p.
>  
> > 3. Mostrar que para n>=4 o resto da divisão por 12 de 
> 1!+2!+3!+...+n! é 9.
>  
> Para n >= 4, n! é divisível por 12.
> Logo, Soma == 1! + 2! + 3! == 9 (mod 12).
>  
> > 4. Mostrar que para todo n inteiro 3n^2-1 nunca é um quadrado.
>  
> Um quadrado só pode ser == 0 ou 1 (mod 3), pois:
> k == 0, 1, 2 (mod 3) ==> k^2 == 0, 1, 1 (mod 3), respectivamente.
> 3n^2 - 1 == 2 (mod 3). Logo, não pode ser quadrado.
> 3n^2 - m^2 = 1 ==>
>  
> > 5. Mostrar que 5n^3+7n^5=0 (mod 12) para todo n.
>  
> Usando pequeno Fermat e propriedades das congruências, teremos:
> Mod 3: 5n^3 + 7n^5 == 2n + n = 3n == 0
> Mod 4: 5n^3 + 7n^5 == n^3 - n^5 = -n^3(n - 1)(n + 1) == 0, pois se n 
> for par, então 8 | n^3 e se n for ímpar então n-1 e n+1 serão pares.
>  
> > 6. Seja f(x)=a_0+a_1x+...+a_nx^n um polinômio com coeficientes inteiros
> > onde a_n>0 e n>=1. Mostrar que f(x) é composto para infinitos 
> valores da
> > variável x.
>  
> Suponhamos que f(c) = p = primo, para algum inteiro c (se um tal c não 
> existir, então acabou!).
> f(x) - f(c) = (x - c)*g(x), para um certo g(x) ==>
> f(x) = (x - c)*g(x) + p.
> Além disso, como a_n > 0, g(x) > 0 para x suficientemente grande.
>  
> Tome x = t*p - c, com t inteiro.
> Então, f(t*p - c) = p*(t*g(t*p - c) + 1).
>  
> Para todo t suficientemente grande, t*g(t*p - c) + 1 > 1 ==>
> f(t*p - c) = múltiplo de p = composto.
>  
> > 7. Mostrar que para a e b inteiros, com (a, b)=1 temos 
> a^fi(b)+b^fi(a)=1
> > (mod ab)
> >
> T. de Euler ==> a^fi(b) == 1 (mod a) e b^fi(a) == 1 (mod b).
> Logo, (a^fi(b) - 1)(b^fi(a) - 1) == 0 (mod ab) ==>
> a^fi(b)*b^fi(a) - (a^fi(b) + b^fi(a)) + 1 == 0 (mod ab) ==>
> Mas a^fi(b)*b^fi(a) == 0 (mod ab), donde segue o resultado desejado.
>  
>  
> []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
=========================================================================