OlimpíadasDivisibilidade

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Autor do Tópico
goncalves3718
3 - Destaque
Mensagens: 816
Registrado em: Qui 26 Dez, 2019 15:26
Última visita: 11-04-23
Jan 2021 07 17:17

Divisibilidade

Mensagem não lida por goncalves3718 »

Encontre todos os pares ordenados [tex3](k,n)[/tex3] de inteiros positivos tais que [tex3]7^k-3^n[/tex3] divide [tex3]k^4+n^2[/tex3] .
Resposta

Como [tex3]7^k[/tex3] e [tex3]3^n[/tex3] sempre são números ímpares, a diferença [tex3]7^k-3^n[/tex3] é par. Logo, [tex3]k^4+n^2[/tex3] tem que ser par também e isso só é válido quando [tex3]k[/tex3] e [tex3]n[/tex3] têm a mesma paridade.

[tex3]7 \equiv -1 \,(\mod 4) \implies 7^k \equiv (-1)^k \, (\mod 4)[/tex3]
[tex3]3 \equiv -1 \,(\mod 4) \implies 3^n \equiv (-1)^n \, (\mod 4)[/tex3]

[tex3]7^k -3^n \equiv (-1)^k - (-1)^n[/tex3]

Quando [tex3]k[/tex3] e [tex3]n[/tex3] são ímpares:

[tex3](-1)^k - (-1)^n = -1 - (-1) = 0[/tex3]

Quando [tex3]k[/tex3] e [tex3]n[/tex3] são pares:

[tex3](-1)^k - (-1)^n = 1 - 1 =0[/tex3]

Ou seja:

[tex3]7^k -3^n \equiv 0 \, (\mod 4)[/tex3]

Se [tex3]7^k - 3^n[/tex3] é múltiplo de [tex3]4[/tex3] é necessário que [tex3]k^4+n^2[/tex3] seja múltiplo de [tex3]4[/tex3] para que [tex3]7^k-3^n|k^4+n^2[/tex3] .

Se [tex3]k[/tex3] e [tex3]n[/tex3] são ímpares, temos o seguinte:

Lema: o quadrado de um número ímpar sempre deixa resto [tex3]1[/tex3] na divisão por [tex3]4[/tex3] .
Resposta

Demonstração: [tex3](2z+1)^2 = 4z^2+4z+1 = 4(z^2+z) + 1 \equiv 1 \, (\mod 4)[/tex3]
[tex3]k^4 = (k^2)^2 \equiv 1 \, (\mod 4)[/tex3]
[tex3]n^2 \equiv 1 \, (\mod 4)[/tex3]

[tex3]k^4+n^2 \equiv 1+1 \equiv 2 \, (\mod 4)[/tex3] (ABSURDO)

Logo [tex3]k[/tex3] e [tex3]n[/tex3] são ambos pares.
Se [tex3]k = 2a[/tex3] e [tex3]n=2b[/tex3]

[tex3]k^4+n^2 = 16a^4 + 4b^2[/tex3]
[tex3]7^k-3^n = 7^{2a} - 7^{2b} = (7^a)^2 - (7^b)^2 = ( 7^a + 7^b)(7^a - 7^b)[/tex3] e por consequência [tex3]7^a + 3^b| 16a^4 +4b^2 \implies 7^a + 3^b \leq 16a^4+4b^2[/tex3]

Como prosseguir?
Meu amigo disse que [tex3]7^a+3^b > 16a^4+4b^2[/tex3] para [tex3]a \geq 5[/tex3] e [tex3]b\geq 4[/tex3] e então [tex3]a \leq 4[/tex3] e [tex3]b\leq 3[/tex3] .
Como ele chegou nisso? Não sei! Conseguem dar uma ajudinha?

Última edição: goncalves3718 (Qui 07 Jan, 2021 17:18). Total de 1 vez.



Avatar do usuário
Ittalo25
5 - Mestre
Mensagens: 2349
Registrado em: Seg 18 Nov, 2013 22:11
Última visita: 27-03-24
Jan 2021 07 18:08

Re: Divisibilidade

Mensagem não lida por Ittalo25 »

[tex3]7^a+3^b > 16a^4+4b^2[/tex3]

Para a=5 é o menor valor tal que [tex3]7^{a}>16a^4[/tex3]
vamos ver se dá para provar por indução que sempre funciona para a>5
base:
[tex3]7^{k}>16k^4[/tex3]
[tex3]7^{k+1}>7\cdot 16k^4=16k^4+16\cdot (6k^4)[/tex3]
[tex3]7^{k+1}>7\cdot 16k^4=16k^4+16\cdot (6k^4)>16k^4+16\cdot (4k^4)>16k^4+16 \cdot (4k^3+6k^2+4k+1) = 16\cdot (k+1)^4[/tex3]
Veja:
[tex3]k^4> 4k^3\rightarrow \boxed{k>4} [/tex3]
[tex3]k^4> 6k^2\rightarrow k>\sqrt{6} \approx2,4[/tex3]
[tex3]k^4> 4k\rightarrow k>\sqrt[3]{4}\approx 1,6[/tex3]
[tex3]k^4> 1\rightarrow k>1[/tex3]

Então a ideia é imaginar que [tex3]7^a+3^b > 16a^4+4b^2[/tex3] e tentar provar que [tex3]7^{a}>16a^4[/tex3] .
Testando os casos pequenos perceber que para [tex3]a\geq 5[/tex3] parece que dá certo. Então tenta provar por indução.

Para [tex3]3^{b}>4b^2[/tex3] deve ser de modo análogo

Última edição: Ittalo25 (Qui 07 Jan, 2021 18:11). Total de 2 vezes.


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

Autor do Tópico
goncalves3718
3 - Destaque
Mensagens: 816
Registrado em: Qui 26 Dez, 2019 15:26
Última visita: 11-04-23
Jan 2021 08 00:10

Re: Divisibilidade

Mensagem não lida por goncalves3718 »

Ittalo25, veja se entende esse desenvolvimento. (NÃO ENTENDI MUITO BEM)
Se puder me ajude?

Para [tex3]a \geq 5[/tex3] , [tex3]7^a = (6+1)^a > { a\choose 5}6^5 = \dfrac{a(a-1)(a-2)(a-3)(a-4) \cdot324}{5} > 64a \cdot \dfrac{2a}{3} \cdot \dfrac{2a}{3} \cdot \dfrac{a}{2} \cdot 2 > 16a^4 [/tex3]

Para [tex3]b\geq 4[/tex3] , [tex3]3^b = (1+2)^b > { b \choose 3}2^3 + { b \choose 4}2^4 = \dfrac{b(b-1)(b-2) \cdot 4}{3} + \dfrac{b(b-1)(b-2)(b-3) \cdot 2}{3 } >b\left(\dfrac{b}{2}\right)^2\cdot \dfrac{4}{3} + b\left( \dfrac{b}{2} \right)^3\cdot \dfrac{2}{3} \geq \dfrac{4b^2}{3} + \dfrac{4b^2}{3} >4b^2[/tex3]

Entao [tex3]7^a+3^b > 16a^4 + 4b^2[/tex3] , logo [tex3]a \leq 4[/tex3] e [tex3]b \leq 3[/tex3]

Última edição: goncalves3718 (Sex 08 Jan, 2021 00:12). Total de 1 vez.



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

Voltar para “Olimpíadas”