Wikilivros

Teoria de números/Máximo divisor comum: diferenças entre revisões

Explorar interativamente o histórico
(Ver alterações pendentes à versão publicada)
[edição não verificada][edição não verificada]
← Edição anteriorEdição posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
m alguns detalhes
INÍCIO da correção de índices, e aprimoramento na formatação das fórmulas TEX
Linha 191:
{{Wikipedia|Algoritmo de Euclides}}
É preciso verificar que <u>o algoritmo irá parar</u>, e ainda mais importante, que <u>fornecerá a resposta correta</u>.
{{Demonstração|/Início}}▼
Considere <math>r_0 = a\,\!</math> e <math>r_1 = b\,\!</math>, e a seguinte sequência de igualdades (obtidas pelo algoritmo da divisão):▼
 
:{| cellpadding=0px cellspacing=6px
▲{{Demonstração|
|-
▲Considere a seguinte sequência de igualdades (obtidas pelo algoritmo da divisão):
:|align=right| <math>r_0 =\,\!</math> r_1q_2|| width=150px | <math>r_1q_0+r_2\,\!</math>, com|| <math>0 \le r_2<r_1\,\!</math>▼
 
|-
:<math>a = bq_0+r_0\,\!</math>, com <math>0 \le r_0<b\,\!</math>
:|align=right| <math>br_1 =\,\!</math> r_0q_1|| <math>r_2q_1+r_1r_3\,\!</math>, com|| <math>0 \le r_1r_3<rr_2\,\!</math>
|-
▲:<math>r_0 = r_1q_2+r_2\,\!</math>, com <math>0 \le r_2<r_1\,\!</math>
:|align=right| <math>\ldotsvdots\,\!</math> || ||
|-
:<math>r_{k-2} = r_{k-1}q_{k}+r_{k}\,\!</math>, com <math>0 \le r_k<r_{k-1}\,\!</math>▼
:|align=right| <math>r_{k-12} =\,\!</math> r_kq_|| <math>r_{k+-1}q_{k-2}+r_{k+1}\,\!</math>, com|| <math>0 \le r_{k+1}<r_kr_{k-1}\,\!</math>
|-
:<math>\ldots\,\!</math>
▲:|align=right| <math>r_{k-21} =\,\!</math> || <math>r_{k-1}q_{k-1}+r_{k+1}\,\!</math>, com|| <math>0 \le r_k<r_{k-+1}<r_{k}\,\!</math>
|-
|align=right| <math>\vdots\,\!</math> || ||
}|}▼
 
Juntando as desigualdades anteriores, tem-se uma sequência decrescente de números não negativos:
:<math>br_1>r_0r_2>r_1r_3>\ldots >r_k>\ldots \ge 0\,\!</math>
 
No entanto, só existe uma quantidade finita de números positivos menores que <math>br_1\,\!</math>. Logo, depois de algum resto <math>r_k\,\!</math>, tem-se <math>r_{k+1} = 0\,\!</math>, ou seja:
:<math>br_1>r_0r_2>r_1r_3>\ldots >\mathbf{r_k}>r_{k+1}=0\,\!</math>
 
É nesse ponto que <u>o algoritmo para</u>: quando o resto <math>r_{k+1} = 0\,\!</math>. Segundo o enunciado, o resultado fornecido será então <math>r_k\,\!</math>.
Linha 216 ⟶ 222:
 
Logo, obtem-se sucessivamente:
:<math>(a,b) = (b,r_0, r_1) = (r_0,r_1, r_2) = \ldots = (\mathbf{r_k},r_{k+1}) = (\mathbf{r_k},0) = \mathbf{r_k}\,\!</math>
 
Portanto o valor fornecido pelo algoritmo corresponde a <math>(a,b)\,\!</math>, e foi obtido através de exatamente <math>k\,\!</math> divisões.
 
▲}}
{{Demonstração/Fim}}
 
=== Exemplo numérico ===
Linha 236 ⟶ 243:
|-
! quociente
|width="40px"| 1 ||width="40px"| 1 ||width="40px"| 2
|width="40px"| 1
|width="40px"| 2
|-
! 30
Linha 258 ⟶ 263:
Na demonstração de que o algoritmo de Euclides funciona, aparecem várias igualdades da forma:
:<math>r_{j-1} = r_{j}q_{j+1}+r_{j+1}\,\!</math>
O índice <math>j\,\!</math> indica que esta é a <math>j\,\!</math>-ésima divisão efetuada no algoritmo.
 
EstaCada uma dessas equações é uma [[w:equação de diferenças|equação de diferenças]] de <u>segunda ordem</u>, em que cada termo é descrito em função de <u>dois</u> anteriores. No caso, cada resto depende dos próximos dois restos, e reciprocamente, cada resto depende dos dois anteriores.
 
ATal relação de recorrenciarecorrência pode também ser expressa como:
:<math>\begin{bmatrix} r_{j-1} \\ r_{j} \end{bmatrix} = \begin{bmatrix} q_{j+1} & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} r_{j} \\ r_{j+1} \end{bmatrix}</math>, sempre que <math>j\ge 1\,\!</math>
 
Com essa notação, os cálculos que aparecem no algoritmo de Euclides para o MDC tornam-se mais sucintos. Por exemplo:
 
:<math>\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} b \\ r_0 \end{bmatrix} = \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} q_1 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} r_0 \\ r_1 \end{bmatrix}</math>▼
:{| cellpadding=0px cellspacing=6px
|-
| align=right | <math>\begin{bmatrix} r_0 \\ r_1 \end{bmatrix}\,\!</math>
| <math>= \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} r_1 \\ r_2 \end{bmatrix}\,\!</math>
|-
|
| <math>= \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix}\cdot \overbrace{ \begin{bmatrix} q_1 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} r_2 \\ r_3 \end{bmatrix} }\,\!</math>
|-
|
▲:| <math>\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} b \\ r_0 \end{bmatrix} = \begin{bmatrix} q_0q_1 & 1\\ 1 & 0 \end{bmatrix}\cdot \overbrace{ \begin{bmatrix} q_1q_2 & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} r_0r_3 \\ r_1r_4 \end{bmatrix} } \,\!</math>
|}
 
E procedendo desse modo em cada passo do algoritmo, no final resulta:
:<math>\begin{bmatrix} ar_0 \\ br_1 \end{bmatrix} = \overbrace{ \begin{bmatrix} \mathbf{q_0} & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} \mathbf{q_1} & 1\\ 1 & 0 \end{bmatrix}\cdot \ldots \cdot \begin{bmatrix} \mathbf{q_{k+1}} & 1\\ 1 & 0 \end{bmatrix} } \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = M \cdot \begin{bmatrix} d \\ 0 \end{bmatrix}</math>, sendo que <math>d=(a,b)\,\!</math>.
 
Perceba que assim não há uma confusão tão grande com os índices dos sucessivos quocientes e restos.
Linha 275 ⟶ 292:
:<math>M = \begin{bmatrix} a' & u\\ b' & v \end{bmatrix}\,\!</math>, com <math>a',b',u,v \in \mathbb{N}\,\!</math>
Disso se conclui que
:<math>\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} a' & u\\ b' & v \end{bmatrix} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = \begin{bmatrix} a'd \\ b'd \end{bmatrix}\,\!</math>
 
Escrevendo <math>\Delta = det(M) = a'v-b'u\,\!</math>, tem-se
Obtido em "https://pt.wikibooks.org/wiki/Teoria_de_números/Máximo_divisor_comum"