Por que a^fi(b)*b^fi(a) == 0 (mod ab) ?
claudio.buffara wrote:
*De:* [EMAIL PROTECTED]
*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
=========================================================================
