OlimpíadasMaterial do POTI - Teoria dos Números Tópico resolvido

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 ]

Avatar do usuário
Autor do Tópico
GustavoSG
iniciante
Mensagens: 6
Registrado em: Sex 07 Dez, 2018 16:02
Última visita: 31-12-19
Jan 2019 18 20:15

Material do POTI - Teoria dos Números

Mensagem não lida por GustavoSG »

Prove que quaisquer dois termos consecutivos da sequência de Fibonacci são primos entre si,ou seja, possuem MDC igual a 1.




Avatar do usuário
LucasOBM
Junior
Mensagens: 10
Registrado em: Ter 21 Ago, 2018 19:12
Última visita: 19-01-19
Jan 2019 18 21:08

Re: Material do POTI - Teoria dos Números

Mensagem não lida por LucasOBM »

Vamos fazê-lo via Indução Finita.
Base da Indução: (1, 1, 2, 3, 5, 8, ...) os termos iniciais satisfazem a propriedade.
Assim, suponha que mdc(F_n, F_n-1) = 1 para algum n inteiro positivo e, suponha por absurdo que mdc(F_n+1, F_n) = d>1 => d divide F_n+1-F_n = F_n-1, ou seja, F_n-1 e F_n têm um divisor comum maior que 1, o que é um absurdo. Assim, mdc(F_n, F_n-1) => mdc(F_n+1, F_n) = 1, provando por indução o enunciado.




Avatar do usuário
erihh3
4 - Sabe Tudo
Mensagens: 559
Registrado em: Dom 16 Set, 2018 12:59
Última visita: 15-10-23
Jan 2019 18 21:12

Re: Material do POTI - Teoria dos Números

Mensagem não lida por erihh3 »

Seja [tex3]a_n[/tex3] o n-ésimo termo da série de fibonacci.

Sabemos que [tex3]a_1=1[/tex3]

O termo geral será dado por:

[tex3]a_n+a_{n+1}=a_{n+2}[/tex3]

Vamos supor, então, que o q-ésimo termo e o próximo termo tenham MDC diferente de 1. Ou seja,

[tex3]a_q=kb[/tex3]
[tex3]a_{q+1}=kc[/tex3]
[tex3]k\neq 1[/tex3]

O termo geral para o q-ésimo termo ficará do seguinte modo:

[tex3]a_{q-1}+a_q=a_{q+1}[/tex3]
[tex3]a_{q-1}+kb=kc[/tex3]
[tex3]a_{q-1}=kc-kb[/tex3]
[tex3]a_{q-1}=k(c-b)[/tex3]

Ou seja, k é múltiplo de [tex3]a_{q-1}[/tex3]

Repetindo para o termo anterior

[tex3]a_{q-2}+a_{q-1}=a_{q}[/tex3]
[tex3]a_{q-2}+k(c-b)=kb[/tex3]
[tex3]a_{q-2}=k(2b-c)[/tex3]

Assim, k também é múltiplo de [tex3]a_{q-2}[/tex3]

Repetindo esse procedimento até os primeiros termos, tem-se:

[tex3]a_1=kd;\quad d\in \mathbb{N}[/tex3]

ABSURDO! Isso não pode acontecer porque [tex3]a_1=1[/tex3] e isso só pode acontecer se [tex3]k=1[/tex3] e [tex3]d=1[/tex3] , haja vista que os dois números pertencem ao conjunto dos números naturais. No entanto, [tex3]k\neq 1[/tex3] .



Ciclo Básico - IME

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

Voltar para “Olimpíadas”