DemonstraçõesTécnica olímpica - Lifting the exponent (LTE)

Fórum de coletânea das melhores demonstrações de teoremas de matemática.
Se você quiser postar uma demonstração aqui, poste, inicialmente, no fórum correspondente utilizando o título "Demonstração Teorema X" e substitua com o nome do teorema/fórmula que você postou e, depois, envie o link para um moderador pedindo para sua mensagem ser movida para o fórum "Demonstrações". Somente moderadores poderão mover sua mensagem para este fórum.

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
Ittalo25
5 - Mestre
Mensagens: 2218
Registrado em: Seg 18 Nov, 2013 22:11
Última visita: 16-01-21
Jan 2021 12 22:15

Técnica olímpica - Lifting the exponent (LTE)

Mensagem não lida por Ittalo25 »

Definição: Seja p um número primo. Se [tex3]e_p(a)=k [/tex3] , então [tex3]p^k \mid a[/tex3] mas [tex3]p^{k+1} \nmid a[/tex3] . Ou seja, k é a maior potência de p que divide a.

Propriedade 1: Se p é primo ímpar, [tex3]p \nmid a[/tex3] , [tex3]p \nmid b[/tex3] , mas [tex3]p|(a-b) [/tex3] , então: [tex3]e_p(a^n-b^n)=e_p(n)+e_p(a-b) [/tex3]
Demonstração:
Resposta

O caso base [tex3]n=1 [/tex3] é óbvio, supondo [tex3]n\geq 2[/tex3] e ser verdade para todo [tex3]k<n [/tex3] , precisamos mostrar que também vale para n.
1° caso: [tex3]p \nmid n[/tex3] .
Sendo [tex3]d = a-b [/tex3] , então:
[tex3]a^{n}-b^n = (b+d)^n-b^n = d\cdot \(nb^{n-1}+\sum_{i=2}^{n}\left(\frac{n}{i}\right)b^{n-i}d^{i-2}\)[/tex3]
Agora [tex3]p|d [/tex3] mas [tex3]p \nmid n [/tex3] e [tex3]p \nmid b^{n-1} [/tex3] , ou seja:
[tex3]e_p(a^n-b^n) = e_p(d) = e_p(a-b) [/tex3]
Mas [tex3]e_p(n)=0 [/tex3] por hipótese, assim:
[tex3]e_p(a^n-b^n) = e_p(a-b)+e_p(n) [/tex3]

2° caso: [tex3]p \mid n[/tex3] .
Seja: [tex3]n=mp [/tex3] , [tex3]d=a^m-b^m [/tex3] e [tex3]b^{m} = c[/tex3] , então:
[tex3]a^n-b^n = (a^m)^p-(b^m)^p = (d+c)^p-c^p = pdc^{p-1}+d^p+\sum_{i=2}^{n}\left(\frac{p-1}{i}\right)d^ic^{p-i} [/tex3]
Agora: Para todo [tex3]2\leq i\leq p-1[/tex3] , [tex3]p|\left(\frac{p}{i}\right)[/tex3] e também [tex3]d^2|d^i [/tex3] .
Como [tex3]p|a-b [/tex3] e [tex3]a-b|a^m-b^m [/tex3] , então [tex3]p|a^m-b^m=d [/tex3] , mas como p é ímpar [tex3](p\geq 3)[/tex3] , então [tex3]pd^2 \mid d^p [/tex3]
Sendo assim, existe um inteiro k tal que [tex3]d^p+\sum_{i=2}^{n}\left(\frac{p-1}{i}\right)d^ic^{p-i} =kpd^2[/tex3]
Portanto: [tex3]a^n-b^n =pdc^{p-1}+kpd^2 = pd \cdot (c^{p-1}+kd) [/tex3] . Como [tex3]p|d [/tex3] mas [tex3]p\nmid c [/tex3] , então: [tex3]p\nmid c^{p-1}+kd [/tex3] .
Chegamos em: [tex3]e_p(a^n-b^n) = e_p(pd) = 1+e_p(d) = 1+ e_p(a^m-b^m) [/tex3]
Mas [tex3]m = \frac{n}{p}<n [/tex3] e por hipótese de indução: [tex3]e_p(a^m-b^m) = e_p(a-b)+e_p(m) [/tex3] , usando isso:
[tex3]e_p(a^n-b^n) = 1+ e_p(a^m-b^m) = 1+e_p(m)+ e_p(a-b) = e_p(a-b)+e_p(n) [/tex3]
Propriedade 2: Se p é primo, n ímpar e [tex3]p \nmid a[/tex3] , [tex3]p \nmid b[/tex3] , mas [tex3]p|(a+b) [/tex3] e [tex3]a+b\neq 0[/tex3] , então: [tex3]e_p(a^n+b^n)=e_p(n)+e_p(a+b) [/tex3]
Demonstração:
Resposta

Se [tex3]p\neq 2[/tex3] então basta aplicar a propriedade 1 para os números [tex3]a [/tex3] e [tex3]-b [/tex3] .
Se [tex3]p=2 [/tex3] , então:
[tex3]a^n+b^n = (a+b) \cdot (a^{n-1}-a^{n-2}b+....-ab^{n-2}+b^{n-1}) [/tex3]
Mas como [tex3]2\nmid a [/tex3] e [tex3]2\nmid b [/tex3] , então a e b são ímpares.
O número: [tex3](a^{n-1}-a^{n-2}b+....-ab^{n-2}+b^{n-1}) [/tex3] é a soma de n números ímpares, ou seja, é um número ímpar.
Sendo assim:
[tex3]e_p(a^n+b^n) = e_p(a+b) + e_p(a^{n-1}-a^{n-2}b+....-ab^{n-2}+b^{n-1})=e_p(a+b)+0 = e_p(a+b)+e_p(n)[/tex3]
Exemplo de aplicação 1: Sejam n>1 e a>0 inteiros e p um primo ímpar tal que [tex3]a^{p}\equiv 1\mod(p^n)[/tex3] . Prove que [tex3]a\equiv 1 \mod(p^{n-1}) [/tex3] .
Solução:
Resposta

Se [tex3]p^{n}| a^p-1[/tex3] , então [tex3]p| a^p-1[/tex3] , ou seja: [tex3]a^p \equiv 1 \mod(p) [/tex3]
Mas pelo pequeno teorema de Fermat: [tex3]a^p \equiv a \mod(p) [/tex3]
Sendo assim: [tex3]a \equiv 1 \mod(p) [/tex3]
Então: [tex3]p\nmid a [/tex3] , [tex3]p\nmid 1 [/tex3] e [tex3]p|a-1 [/tex3] .
Usando o LTE:
[tex3]e_p(a^p-1) = e_p(a-1)+e_p(p) = e_p(a-1)+1 [/tex3]
Como [tex3]a^{p}\equiv 1\mod(p^n)[/tex3] , então: [tex3]e_p(a^p-1) \geq n [/tex3] .
Ou seja: [tex3]e_p(a-1)+1 \geq n\rightarrow \boxed{e_p(a-1) \geq n-1} [/tex3]
Sendo assim: [tex3]p^{n-1}|a-1 [/tex3] e está provado.
Exemplo de aplicação 2: (Irlanda - 1996) Seja p um número primo, a e n inteiros positivos. Se [tex3]2^p+3^p=a^n [/tex3] , prove que [tex3]n=1 [/tex3]
Solução:
Resposta

Para p=2: [tex3]2^2+3^2 = 13^1 [/tex3]
Para p=3: [tex3]2^3+3^3 = 5 \cdot 7 [/tex3]
Para p=5: [tex3]2^5+3^5 = 11 \cdot 5^2 [/tex3]
Então supondo [tex3]p\geq 7[/tex3]
Para p ímpar: [tex3]2^p+3^p = 5 \cdot (2^{p-1}-3\cdot 2^{p-2}+....2\cdot 3^{p-2}-3^{p-1}) [/tex3]
Ou seja: [tex3]5|a^n [/tex3] .
[tex3]5 \nmid 2 [/tex3] , [tex3]5 \nmid 3 [/tex3] e [tex3]5|2+3 [/tex3] . Usando LTE:
[tex3]e_5(a^n) = e_5(2^p+3^p) = e_5(2+3) + e_5(p) = \boxed {1}[/tex3]
Exemplo de aplicação 3: Se a e n são inteiros positivos e [tex3]n|2^n+1 [/tex3] , então prove que [tex3]n=3 [/tex3] ou [tex3]9|n [/tex3]
Solução:
Resposta

Obviamente n tem que ser ímpar para dividir [tex3]2^n+1 [/tex3] , sendo assim:
[tex3]2^n+1 = (2+1) \cdot (2^{n-1}-2^{n-2}+....-2+1) [/tex3] , ou seja, n é múltiplo de 3.
[tex3]3 \nmid 2 [/tex3] , [tex3]3\nmid 1 [/tex3] e [tex3]3\nmid 2+1 [/tex3] , usando LTE:
[tex3]e_3(2^n+1) \geq e_3(n) [/tex3]
[tex3]e_3(2+1)+e_3(3) \geq e_3(n) [/tex3]
[tex3]1+1 \geq e_3(n) [/tex3]
[tex3]\boxed{2 \geq e_3(n)\geq 1} [/tex3]
Exemplo de aplicação 4: (República Tcheca - 1996) Encontre todos os pares de inteiros positivos (x,y) tais que [tex3]p^x-y^p=1 [/tex3] , onde p é um primo ímpar
Solução:
Resposta

Como p é ímpar então: [tex3]p^x = y^p+1 = (y+1) \cdot (y^{p-1}-y^{p-2}+....-y+1) [/tex3] , ou seja: [tex3]y+1|p^x [/tex3] .
Mas então [tex3]y+1 [/tex3] é uma potência de p. Obviamente [tex3]p\nmid y[/tex3] , do contrário teríamos [tex3]p|1 [/tex3] . Então usando LTE:
[tex3]e_p(y^p+1) = e_p(y+1)+e_p(p) [/tex3]
[tex3]e_p(y+1) = x-1 [/tex3]
Ou seja: [tex3]p^{x-1} | y+1[/tex3]
Sendo assim:
[tex3]p^{x-1}= y+1 [/tex3] ou [tex3]p^x=y+1 [/tex3] .
1° caso:
[tex3]p^{x-1} = y+1 [/tex3]
[tex3]y^p+1 = py+p [/tex3]
[tex3]y^p-y =(y+1)(p-1) [/tex3] . Como [tex3]mdc(y,y+1)=1 [/tex3] , então:
[tex3]y| p-1\rightarrow p\geq y+1[/tex3] . Mas [tex3]y+1 [/tex3] é uma potência de p, ou seja: [tex3]y+1=p \rightarrow x=2[/tex3] .
Ou seja:
[tex3]p^2 = y^p+1 = (p-1)^p + 1 [/tex3]
[tex3](p-1) \cdot (p+1) = (p-1)^p [/tex3]
[tex3]p+1 = (p-1)^{p-1} [/tex3]
Mas p-1 é par: [tex3]p-1=2k [/tex3]
[tex3]p = (p-1-1)^{k}\cdot (p-1+1)^k [/tex3]
Então [tex3]k=1\rightarrow p=3[/tex3]
Solução: [tex3](x,y,p) = (2,2,3) [/tex3]
2° caso:
[tex3]p^{x} = y+1 [/tex3]
[tex3]y^p+1 = y+1 [/tex3]
[tex3]y^p = y [/tex3]
Único jeito seria [tex3]y=1 [/tex3] , mas daria [tex3]p^x = 2 [/tex3] , contradição já que p é primo ímpar.
Única solução: [tex3]\boxed{(x,y,p) = (2,2,3)} [/tex3]

Última edição: Ittalo25 (Qui 14 Jan, 2021 00:55). Total de 6 vezes.


Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]

Avatar do usuário
Autor do Tópico
Ittalo25
5 - Mestre
Mensagens: 2218
Registrado em: Seg 18 Nov, 2013 22:11
Última visita: 16-01-21
Jan 2021 12 22:23

Re: Técnica olímpica - Lifting the exponent (LTE)

Mensagem não lida por Ittalo25 »

Babi123, null



Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Demonstrações”