Mostre que [tex3]mdc(a^m − 1,a^n − 1) = a^{mdc(m,n)} − 1.
[/tex3]
Expliquem o mais detalhado possível por favor!
Acredito que devo usar o Lema de Euclides e o Algoritmo de Euclides
Lembrando que o lema de Euclides diz que [tex3]mdc(a,b)=mdc(a,qb+a)[/tex3]
A resolução que eu tenho :
[tex3]mdc(a^m − 1,a^n − 1) = mdc(a^{m−n} − 1 + (a^n − 1)a^m−n, a^n − 1) = mdc(a^{m−n} − 1,a^n − 1)[/tex3]
Como chego em [tex3]mdc(a^{m−n} − 1 + (a^n − 1)a^m−n, a^n − 1)[/tex3]
, obrigado!!
Olimpíadas ⇒ MDC - Lema de Euclides Tópico resolvido
Moderador: [ Moderadores TTB ]
-
undefinied3 
- Mensagens: 1483
- Registrado em: Dom 02 Ago, 2015 13:51
- Última visita: 30-09-22
Fev 2020
01
02:46
Re: MDC - Lema de Euclides
Tem algo estranho nessa sua resolução. Vou só mostrar a que eu conheço.
Seja [tex3]d=mdc(a^m-1,a^n-1)[/tex3] . Então d divide [tex3]a^m-1[/tex3] e d divide [tex3]a^n-1[/tex3] .
Eu vou usar congruência porque facilita a notação e eu to com preguiça.
[tex3]a^m-1 \equiv 0 \ (mod \ d) \rightarrow a^m \equiv 1 \ (mod \ d) \rightarrow a^{\alpha.m} \equiv 1 \ (mod \ d)[/tex3]
Analogamente, [tex3]a^{\beta .n} \equiv 1 \ (mod \ d)[/tex3]
Então [tex3]a^{\alpha.m+\beta.n} \equiv 1 \ (mod \ d)[/tex3] .
Mas seja [tex3]t=mdc(m,n)[/tex3] . Então existem [tex3]\alpha[/tex3] e [tex3]\beta[/tex3] tais que [tex3]\alpha m + \beta n = t[/tex3] , pela identidade de Bézout.
Então [tex3]a^{\alpha m + \beta n } \equiv 1 \rightarrow a^t \equiv 1 \rightarrow a^{mdc(m,n)} \equiv 1 \rightarrow a^{mdc(m,n)}-1 \equiv 0 \ (mod \ d)[/tex3]
Então d divide [tex3]a^{mdc(m,n)}-1[/tex3]
Mas isso não mostra que d é o maior divisor dessa expressão. Isso só vai ser verdade se também ocorrer que [tex3]a^{mdc(m,n)}-1[/tex3] divide d.
Ora, d é fator de [tex3]a^m-1[/tex3] e [tex3]a^n-1[/tex3] . Perceba que existem u e v tais que [tex3]m=mdc(m,n).u[/tex3] , [tex3]n=mdc(m,n).v[/tex3] . Isso é fácil de ver, pois mdc(m,n) é um fator comum de m e de n. u e v são apenas os demais fatores que completam m e n, respectivamente.
Então:
[tex3]a^m-1 = a^{u.mdc(m,n)}-1^{u.mdc(m,n)}=(a^{mdc(m,n)}-1)(a^{(u-1)mdc(m,n)}+....+1)[/tex3] , que claramente é divisível por [tex3]a^{mdc(m,n)}-1[/tex3] pois o fator está explicitado ali. O mesmo vale para [tex3]a^n-1[/tex3] .
Ora, se [tex3]a^{mdc(m,n)}-1[/tex3] divide tanto [tex3]a^m-1[/tex3] quanto [tex3]a^n-1[/tex3] , então [tex3]a^{mdc(m,n)}-1[/tex3] é um fator em comum àqueles dois valores. Logo [tex3]a^{mdc(m,n)}-1[/tex3] divide o maior dos fatores em comum daqueles dois valores, ou seja, divide d que é justamente o mdc.
E então terminamos, pois [tex3]d|a^{mdc(m,n)}-1[/tex3] e [tex3]a^{mdc(m,n)}-1|d[/tex3] significa que [tex3]a^{mdc(m,n)}-1=d[/tex3]
Segue que [tex3]d=mdc(a^m-1,a^n-1)=a^{mdc(m,n)}-1[/tex3]
É uma demonstração difícil mas tente absorver tudo que eu apresentei. É bom você ir se acostumando com o que tá aqui se for continuar estudando isso.
Seja [tex3]d=mdc(a^m-1,a^n-1)[/tex3] . Então d divide [tex3]a^m-1[/tex3] e d divide [tex3]a^n-1[/tex3] .
Eu vou usar congruência porque facilita a notação e eu to com preguiça.
[tex3]a^m-1 \equiv 0 \ (mod \ d) \rightarrow a^m \equiv 1 \ (mod \ d) \rightarrow a^{\alpha.m} \equiv 1 \ (mod \ d)[/tex3]
Analogamente, [tex3]a^{\beta .n} \equiv 1 \ (mod \ d)[/tex3]
Então [tex3]a^{\alpha.m+\beta.n} \equiv 1 \ (mod \ d)[/tex3] .
Mas seja [tex3]t=mdc(m,n)[/tex3] . Então existem [tex3]\alpha[/tex3] e [tex3]\beta[/tex3] tais que [tex3]\alpha m + \beta n = t[/tex3] , pela identidade de Bézout.
Então [tex3]a^{\alpha m + \beta n } \equiv 1 \rightarrow a^t \equiv 1 \rightarrow a^{mdc(m,n)} \equiv 1 \rightarrow a^{mdc(m,n)}-1 \equiv 0 \ (mod \ d)[/tex3]
Então d divide [tex3]a^{mdc(m,n)}-1[/tex3]
Mas isso não mostra que d é o maior divisor dessa expressão. Isso só vai ser verdade se também ocorrer que [tex3]a^{mdc(m,n)}-1[/tex3] divide d.
Ora, d é fator de [tex3]a^m-1[/tex3] e [tex3]a^n-1[/tex3] . Perceba que existem u e v tais que [tex3]m=mdc(m,n).u[/tex3] , [tex3]n=mdc(m,n).v[/tex3] . Isso é fácil de ver, pois mdc(m,n) é um fator comum de m e de n. u e v são apenas os demais fatores que completam m e n, respectivamente.
Então:
[tex3]a^m-1 = a^{u.mdc(m,n)}-1^{u.mdc(m,n)}=(a^{mdc(m,n)}-1)(a^{(u-1)mdc(m,n)}+....+1)[/tex3] , que claramente é divisível por [tex3]a^{mdc(m,n)}-1[/tex3] pois o fator está explicitado ali. O mesmo vale para [tex3]a^n-1[/tex3] .
Ora, se [tex3]a^{mdc(m,n)}-1[/tex3] divide tanto [tex3]a^m-1[/tex3] quanto [tex3]a^n-1[/tex3] , então [tex3]a^{mdc(m,n)}-1[/tex3] é um fator em comum àqueles dois valores. Logo [tex3]a^{mdc(m,n)}-1[/tex3] divide o maior dos fatores em comum daqueles dois valores, ou seja, divide d que é justamente o mdc.
E então terminamos, pois [tex3]d|a^{mdc(m,n)}-1[/tex3] e [tex3]a^{mdc(m,n)}-1|d[/tex3] significa que [tex3]a^{mdc(m,n)}-1=d[/tex3]
Segue que [tex3]d=mdc(a^m-1,a^n-1)=a^{mdc(m,n)}-1[/tex3]
É uma demonstração difícil mas tente absorver tudo que eu apresentei. É bom você ir se acostumando com o que tá aqui se for continuar estudando isso.
Última edição: undefinied3 (Sáb 01 Fev, 2020 02:47). Total de 1 vez.
Ocupado com início do ano no ITA. Estarei fortemente inativo nesses primeiros meses do ano, então busquem outro moderador para ajudar caso possível.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 6 Respostas
- 2785 Exibições
-
Última msg por geobson
-
- 0 Respostas
- 1312 Exibições
-
Última msg por FelipeMartin
-
- 0 Respostas
- 660 Exibições
-
Última msg por ltds
-
- 1 Respostas
- 2181 Exibições
-
Última msg por deOliveira
