Fórum PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Máximo Divisor Comum

3 participantes

Ir para baixo

Máximo Divisor Comum Empty Máximo Divisor Comum

Mensagem por Cristina Lins Seg 06 Set 2021, 15:49

Sendo a, b, q, r, d pertencente a Z, com r>=0, prove que:
Se a = b.q + r e mdc (b,r) = d, então mdc (a,b) = d


Última edição por Cristina Lins em Ter 07 Set 2021, 11:01, editado 2 vez(es)

Cristina Lins
Jedi
Jedi

Mensagens : 458
Data de inscrição : 01/03/2012
Idade : 63
Localização : Itapetininga - SP

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por tales amaral Ter 07 Set 2021, 08:31

Salve  cheers, só para confirmar. Não seria mdc (a,b) = d ali no final?
tales amaral
tales amaral
Padawan
Padawan

Mensagens : 99
Data de inscrição : 02/05/2020
Idade : 17
Localização : ES

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por Cristina Lins Ter 07 Set 2021, 10:59

Bom dia Tales

Nossa, eu digitei errado. Obrigada. Relmente é mdc (a,b) = d

Cristina Lins
Jedi
Jedi

Mensagens : 458
Data de inscrição : 01/03/2012
Idade : 63
Localização : Itapetininga - SP

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por tales amaral Ter 07 Set 2021, 12:53

Salve  cheers. Pelo algoritmo de Euclides:

[latex]\text{mdc}(a,b) = \text{mdc}(b.q + r ,b) = \text{mdc}(b ,r) = d[/latex]



Uma demonstração seria: se k é um divisor comum de a e b, temos [latex]a = nk[/latex] e [latex]b = mk \implies a-b = (n-m)\cdot k[/latex], ou seja, k também divide a diferença entre a e b. Aí teriamos que fazer essa diferença q vezes para chegar em [latex] \text{mdc}(b.q + r ,b) = \text{mdc}(b ,r)[/latex]. 
tales amaral
tales amaral
Padawan
Padawan

Mensagens : 99
Data de inscrição : 02/05/2020
Idade : 17
Localização : ES

Edu lima gosta desta mensagem

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por Edu lima Ter 07 Set 2021, 13:15

Acredito que seja isso:

Primeira vamos demonstrar a proposição que chamei de A.

Proposição A: Se d|a e d|b, então d|(a-b)

Hipótese: d|a e d|b
Tese: d|(a-b) 

Como d|a, vai existir um s pertencente ao conjunto do inteiros tal que a=d*s; de forma análoga, como d|b vai existir um t, pertence ao conjunto dos números inteiros tal que d=b*t

Assim, a-b =d*s-d*t = d*(s-t), logo d|(a-b).

Assim, sabemos que, de fato, essa proposição acima é válida.

Com isso,

Hipótese: Se a=b*q+r  e mdc(b,r)=d 

Tese: então mdc(a,b)=d

Como mdc(b,r)=d, logo d|b e d|a, mas se d|b, ele tbm vai dividir b*q, ou seja,  d|b*q

Pela proposição A temos que: se d|(a-b*q), então d|r.

Vamos verificar:

Tomando c pertencente aos inteiros tal que c|a e c|b e c|b*q, então pela proposição A, c|(a-bq), mas se ele divide essa expressão, então c|r.

Portanto, 

Como c|b e c|r, então ele divide d, ou seja, c|d

Assim como, se ele c|b e c|a, então ele c|d

Conclusão da hipótese é que: mdc(b,r)=mdc(a,b)=d (que é justamente a tese)

Dica: para visualizar melhor a demonstração use um contraexemplo, tipo: 9=4*2+1, em que a=9; b=4; q=2 e r=1. Pois assim, fica melhor de enxergar.


Última edição por Edu lima em Ter 07 Set 2021, 18:08, editado 1 vez(es)

Edu lima
Jedi
Jedi

Mensagens : 342
Data de inscrição : 31/05/2018
Idade : 31
Localização : RN

tales amaral gosta desta mensagem

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por Cristina Lins Ter 07 Set 2021, 14:58

Boa tarde Edu Lima

Muito obrigada. Demonstração bem esclarecedora. Valeu a ajuda

Cristina Lins
Jedi
Jedi

Mensagens : 458
Data de inscrição : 01/03/2012
Idade : 63
Localização : Itapetininga - SP

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por Cristina Lins Ter 07 Set 2021, 17:24

Boa tarde Edu Lima

Uma dúvida
Como mdc(b,r)=d, logo d|b e b|r , não seria d|b e d|r?

Cristina Lins
Jedi
Jedi

Mensagens : 458
Data de inscrição : 01/03/2012
Idade : 63
Localização : Itapetininga - SP

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por Edu lima Ter 07 Set 2021, 18:03

Eu inverti essa parte: b|r, na verdade é d|a. Vou ajeitar, foi só falta de atenção.

A gente parte desse ponto: a=b*q+r e mdc(b,r)=d (que é a nossa hipótese)

A estratégia é mostrarmos que, d|r, ou seja, d|(a-b*q), sabendo que r=a-b*q, aí a partir disso, podemos fazer as conclusões finais. Por isso que trouxe a demonstração da primeira proposição para poder usá-la nesta parte.

Exemplo: 

9=4*2+1, mdc(4,1)=1, afirmo isso: 4/1 e 9/1, e quero saber: 1/1
a=b*q+r,  mdc(b,r)=d, afirmo isso: d|b e d|a, e quero saber: d|r

Vc altera essa parte. Ao invés de b|r é d|a.


Última edição por Edu lima em Ter 07 Set 2021, 18:20, editado 1 vez(es)

Edu lima
Jedi
Jedi

Mensagens : 342
Data de inscrição : 31/05/2018
Idade : 31
Localização : RN

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por Cristina Lins Ter 07 Set 2021, 18:16

OK MUITO OBRIGADA

Cristina Lins
Jedi
Jedi

Mensagens : 458
Data de inscrição : 01/03/2012
Idade : 63
Localização : Itapetininga - SP

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por Edu lima Ter 07 Set 2021, 18:18

De nada... Smile

Edu lima
Jedi
Jedi

Mensagens : 342
Data de inscrição : 31/05/2018
Idade : 31
Localização : RN

Ir para o topo Ir para baixo

Máximo Divisor Comum Empty Re: Máximo Divisor Comum

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Ir para o topo


 
Permissões neste fórum
Você não pode responder aos tópicos