OlimpíadasLema de Euclides 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 ]

Autor do Tópico
goncalves3718
3 - Destaque
Mensagens: 816
Registrado em: Qui 26 Dez, 2019 15:26
Última visita: 11-04-23
Jan 2020 24 21:38

Lema de Euclides

Mensagem não lida por goncalves3718 »

Calcule:
a) [tex3]mdc(n,n^2 + n + 1).[/tex3]

Sei que tem que usar o lema [tex3]mdc(a,b)=mdc(a,a+qb)[/tex3] onde [tex3]q \in Z[/tex3]




Avatar do usuário
deOliveira
5 - Mestre
Mensagens: 978
Registrado em: Qui 31 Ago, 2017 08:06
Última visita: 05-03-23
Localização: São José dos Campos
Jan 2020 25 00:04

Re: Lema de Euclides

Mensagem não lida por deOliveira »

Teorema de Bezout: Sejam [tex3]a,b\in\mathbb Z[/tex3] se [tex3]\mdc(a,b)=d[/tex3] então existem [tex3]x,y\in\mathbb Z[/tex3] tais que [tex3]ax+by=d[/tex3]
Corolário: Sejam [tex3]a,b\in\mathbb Z[/tex3] se existem [tex3]x,y \in\mathbb Z[/tex3] tais que [tex3]ax+by=1[/tex3] então [tex3]\mdc(a,b)=1[/tex3]

[tex3]n\in\mathbb Z\implies -n-1\in\mathbb Z[/tex3]
Note que [tex3](-n-1)n+1(n^2+n+1)=-n^2-n+n^2+n+1=1[/tex3]
Dessa forma, chamando [tex3]x=-n-1[/tex3] e [tex3]y=1[/tex3] temos que existem [tex3]x,y\in\mathbb Z[/tex3] tais que [tex3]xn+y(n^2+n+1)=1[/tex3]
[tex3]\implies\mdc(n,n^2+n+1)=1[/tex3]

Espero ter ajudado :).



Saudações.

Avatar do usuário
deOliveira
5 - Mestre
Mensagens: 978
Registrado em: Qui 31 Ago, 2017 08:06
Última visita: 05-03-23
Localização: São José dos Campos
Jan 2020 25 14:34

Re: Lema de Euclides

Mensagem não lida por deOliveira »

Uma solução usando o lema de Euclides é a seguinte:

[tex3]\mdc(1,n)=1\\n+1\in\mathbb Z\\\mdc(n,1+n(n+1))=\mdc(n,1)=1[/tex3]

Pensando em [tex3]\mdc(a,b)=\mdc(a,a+qb)[/tex3] temos
[tex3]a=1\\b=n\\q=n+1[/tex3]

Espero ter ajudado.


Saudações.

Autor do Tópico
goncalves3718
3 - Destaque
Mensagens: 816
Registrado em: Qui 26 Dez, 2019 15:26
Última visita: 11-04-23
Jan 2020 25 16:38

Re: Lema de Euclides

Mensagem não lida por goncalves3718 »

Mas logo de início já temos [tex3]MDC(1,n)=1[/tex3] ?

[tex3]mdc(n,n^2 + n + 1) = mdc(n,n^2 + n + 1 − n(n + 1)) = mdc(n,1) = 1.[/tex3]

Você poderia me dizer quem são [tex3]a,b [/tex3] e [tex3]q[/tex3] em [tex3]mdc(n,n^2 + n + 1 − n(n + 1))
[/tex3] ?

É a resolução descrita no material! Peço desculpas, é que eu realmente tenho 14 anos e estou iniciando com teoria dos números agora, então surgem muitas dúvidas!



Avatar do usuário
deOliveira
5 - Mestre
Mensagens: 978
Registrado em: Qui 31 Ago, 2017 08:06
Última visita: 05-03-23
Localização: São José dos Campos
Jan 2020 25 17:54

Re: Lema de Euclides

Mensagem não lida por deOliveira »

Porque [tex3]\mdc(1,n)=1[/tex3] :
Os únicos divisores de [tex3]1[/tex3] são [tex3]-1[/tex3] e [tex3]1[/tex3].
Além disso, todo número inteiro [tex3]n[/tex3] tem [tex3]1[/tex3] como divisor.
Então o maior divisor em comum a [tex3]1[/tex3] e a [tex3]n[/tex3] vai ser [tex3]1[/tex3]
Dessa forma, [tex3]\mdc(1,n)=1[/tex3] para todo [tex3]n\in\mathbb Z[/tex3]

Já nessa resolução eu acho que ele usou um desdobramento do Leme de Euclides.
[tex3]\mdc(a,b)=\mdc(a-bc,b)[/tex3]
Então seria
[tex3]a=n^2+n+1\\b=n\\c=n+1[/tex3]

A demonstração desse desdobramento tem nesse tópico aqui viewtopic.php?f=3&t=78214&p=213117&hilit=bezout#p213117
Mas não deve ser difícil achar outras.

Mas de qualquer forma, as duas outras resoluções que eu apresentei também são corretas.
goncalves3718 escreveu:
Sáb 25 Jan, 2020 16:38
Peço desculpas, é que eu realmente tenho 14 anos e estou iniciando com teoria dos números agora, então surgem muitas dúvidas!
Não se preocupe com isso, nem precisa se desculpar. Eu tenho mais familiaridade com essas coisas aí às vezes eu resolvo de uma forma meio automática que não fica bem explicada, estou trabalhando para melhorar isso.



Saudações.

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

Voltar para “Olimpíadas”