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]
Olimpíadas ⇒ Lema de Euclides Tópico resolvido
Moderador: [ Moderadores TTB ]
-
- 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
Teorema de Bezout: Sejam [tex3]a,b\in\mathbb Z[/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 .
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.
-
- 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
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.
[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.
-
- Mensagens: 816
- Registrado em: Qui 26 Dez, 2019 15:26
- Última visita: 11-04-23
Jan 2020
25
16:38
Re: Lema de Euclides
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!
?[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!
-
- 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
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.
: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.
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.goncalves3718 escreveu: ↑Sáb 25 Jan, 2020 16:38Peço desculpas, é que eu realmente tenho 14 anos e estou iniciando com teoria dos números agora, então surgem muitas dúvidas!
Saudações.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 6 Respostas
- 2652 Exibições
-
Última msg por geobson
-
- 0 Respostas
- 1261 Exibições
-
Última msg por FelipeMartin