Teoria de números/Máximo divisor comum: diferenças entre revisões
[edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
m CONTINUANDO ajustes |
CONTINUANDO as correções (fim?) |
||
Linha 28:
}}
{{Wikipedia|Números primos entre si}}
Quando o conjunto <math>D(a,b)\,\!</math> possui apenas um elemento positivo, ou seja, quando <math>
==== Exemplo ====
Linha 39:
== Teorema de Bézout ==
{{Teorema|texto=
Se <math>d=
}}
{{Wikipedia|Identidade de Bézout}}
Linha 48:
=== Corolário ===
{{Teorema|texto=
Se <math>m|ab\,\!</math> e <math>
}}
Linha 74:
De fato, como <math>p\,\!</math> é primo, o conjunto de seus divisores é <math>D(p)=\{\pm 1,\pm p \}\,\!</math>. Além disso, <math>p\not|a\,\!</math>, logo <math>p\,\!</math> não pode ser um divisor comum de <math>a\,\!</math> e <math>b\,\!</math>.
Segue que <math>
De acordo com o corolário acima, isso implica que <math>p\,\!</math> divide <math>b\,\!</math>.
Linha 368:
:Como <math>0\le r<m\,\!</math>, segue que <math>r = 0\,\!</math>, ou seja, <math>z = mq \in \mathbb{Z}\,\!</math>.
Para provar que se tem <math>m=
Observe que:
Linha 377:
Mas <math>m\,\!</math> é o maior divisor porque, dado qualquer outro divisor <math>\delta \in D(a,b)\,\!</math>, tem-se <math>\delta | ax_0 + by_0 = m\,\!</math>
Logo, <math>|\delta| \le |m|\,\!</math>, ou seja, <math>m =
}}
== Número de passos ==
Linha 383:
Nesta seção, será discutido quão eficiente é o algoritmo de Euclides para o cálculo do MDC. De forma mais precisa, se forem dados dois números inteiros:
''Quantas etapas (divisões) do algoritmo são necessárias para que
Recorde-se que o algoritmo baseia-se na construção da sequência:
:<math>a = r_0 \ge b
cujos termos verificam as seguintes igualdades:
:<math>a = bq_0+r_0\,\!</math>, com <math>0 \le r_0<b\,\!</math>▼
:<math>b = r_0q_1+r_1\,\!</math>, com <math>0 \le r_1<r_0\,\!</math>▼
:<math>\ldots\,\!</math>▼
:<math>r_{k-2} = r_{k-1}q_{k}+r_{k}\,\!</math>, com <math>0 \le r_k<r_{k-1}\,\!</math>▼
:<math>r_{k-1} = r_kq_{k+1}+r_{k+1} = r_kq_{k+1}\,\!</math>, pois <math>r_{k+1} = 0\,\!</math>▼
:{| cellpadding=0px cellspacing=6px
O algoritmo fornece <math>(a,b) = r_k\,\!</math>, que é o último resto não nulo obtido nas sucessivas divisões.▼
|-
▲
|-
▲
|-
|align=right| <math>\vdots\,\!</math> || ||
|-
▲
|-
▲
|}
▲O algoritmo fornece <math>(a,b) = r_k\,\!</math>, que é o último resto não nulo, obtido
=== Fazendo estimativas ===
Uma observação importante é que o resto de uma divisão é sempre menor que a metade do dividendo:
:<math>
Sendo a primeira desigualdade válida porque <math>q_0\ge 1\,\!</math> e a segunda porque <math>
:<math>a > 2r_0\,\!</math>▼
:<math>r_0 > 2r_2\,\!</math>
:<math>r_1 > 2r_3\,\!</math>
e em geral
:<math>r_{k
Assim, comparando os termos cujos índices são pares, segue:
Linha 439 ⟶ 446:
Assim, sabendo que o algoritmo para exatamente quando <math>r_{k+1} = 0\,\!</math>, conlui-se que tal índice <math>k+1\,\!</math> não pode ser maior que <math>2t\,\!</math>, em símbolos:
:<math>k+1 \le 2([ \log_2 a ] + 1)\,\!</math>
Para melhor compreender o significado dessa estimativa, considere que <math>a\,\!</math> tem <math>N\,\!</math> dígitos decimais. Então:
:<math>10^{N-1}\le a < 10^N\,\!</math>
Aplicando o logaritmo em ambos os membros da segunda desigualdade, resulta
:<math>\log_2 a < N\cdot\log_2 10\,\!</math>
Logo, <math>k+1 \le 2 ([\log_2 a] +1)<
Embora esta não seja a melhor aproximação para <math>k\,\!</math>, já é bastante útil, pois mostra que o número de etapas cresce linearmente com o número de dígitos de <math>a\,\!</math>.
Linha 475 ⟶ 482:
Aplicando <math>q_j = 1\,\!</math> na fórmula de recorrência, tem-se:
:<math>r_{j-1} = r_jq_{j
Isso lembra a fórmula que define a [[w:Sequência de Fibonacci|sequência de Fibonacci]], embora esteja "ao contrário".
Linha 492 ⟶ 499:
}}
{{Tarefa|Conferir se o expoente k+1 está correto ou se deveria ser k, na próxima equação}}
Matricialmente, as condições <math>q_0 = 1,\ldots, q_{k
:<math>\begin{bmatrix} a \\ b \end{bmatrix} = \overbrace{ \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}\cdot \ldots \cdot \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix} } \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}^{k+
Com um simples uso do [[w:Indução matemática|princípio de indução finita]], consegue-se:
Linha 499 ⟶ 507:
Deste modo,
:<math>\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} F_{n+
Como <math>d=(a,b)\ge 1\,\!</math>, segue que
* <math>a\ge F_{n+
* <math>b\ge F_{n+
=== Teorema de Lamé ===
|