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>mdc(a,b)=1\,\!</math>, os números <math>a\,\!</math> e <math>b\,\!</math> são ditos ''primos entre si'', ''relativamente primos'' ou simplesmente ''co-primos''.
 
==== Exemplo ====
Linha 39:
== Teorema de Bézout ==
{{Teorema|texto=
Se <math>d=mdc(a,b)\,\!</math>, então existem inteiros <math>x\,\!</math> e <math>y\,\!</math> tais que <math>d=ax+by\,\!</math>.
}}
{{Wikipedia|Identidade de Bézout}}
Linha 48:
=== Corolário ===
{{Teorema|texto=
Se <math>m|ab\,\!</math> e <math>mdc(a,b)=1\,\!</math> então <math>m|b\,\!</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>mdc(a,b)=1\,\!</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=mdc(a,b)\,\!</math>, escreva <math>m=ax_0+by_0\,\!</math> (isso é possível, já que <math>m \in J\,\!</math>).
 
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 = mdc(a,b)\,\!</math>.
}}
== 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 oum resto <math>r_{k+1}\,\!</math> seja zero?''
 
Recorde-se que o algoritmo baseia-se na construção da sequência:
:<math>a = r_0 \ge b >= r_0r_1 > r_1r_2 > \ldots > r_k > r_{k+1} = 0\,\!</math>
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>r_0 = r_1q_2+r_2\,\!</math>, com <math>0 \le r_2<r_1\,\!</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.
|-
{{Tarefa|Melhorar forma de exibição dos dados anteriores. Talvez usar uma tabela para alinhar os sinais de igualdade ou os últimos restos.}}
:|align=right| <math>br_0 =\,\!</math> r_0q_1|| width=200px | <math>r_1q_0+r_1r_2\,\!</math>, com|| <math>0 \le r_2<r_1<r_0\,\!</math>
|-
:|align=right| <math>ar_1 =\,\!</math> bq_0|| <math>r_2q_1+r_0r_3\,\!</math>, com|| <math>0 \le r_0r_3<br_2\,\!</math>
|-
|align=right| <math>\vdots\,\!</math> || ||
|-
:|align=right| <math>r_{k-2} =\,\!</math> || <math>r_{k-1}q_{k-2}+r_{k}\,\!</math>, com|| <math>0 \le r_kr_{k}<r_{k-1}\,\!</math>
|-
:|align=right| <math>r_{k-1} =\,\!</math> r_kq_|| <math>r_{k+}q_{k-1}+r_{k+1} = r_kq_r_{k+}q_{k-1}\,\!</math>, || pois <math>0 = r_{k+1} = 0<r_{k}\,\!</math>
|}
 
O algoritmo fornece <math>(a,b) = r_k\,\!</math>, que é o último resto não nulo, obtido nasem sucessivas<math>k\,\!</math> passos (divisões).
 
=== Fazendo estimativas ===
Uma observação importante é que o resto de uma divisão é sempre menor que a metade do dividendo:
:<math>ar_0 = bqr_1q_0+r_0r_2 \ge br_1+r_0r_2 > 2r_02r_2\,\!</math>
Sendo a primeira desigualdade válida porque <math>q_0\ge 1\,\!</math> e a segunda porque <math>br_1>r_0r_2\,\!</math>. Deste modo, tem-se
:<math>a > 2r_0\,\!</math>
:<math>b > 2r_1\,\!</math>
:<math>r_0 > 2r_2\,\!</math>
:<math>r_1 > 2r_3\,\!</math>
:<math>\ldotsr_2 > 2r_4\,\!</math>
:<math>ar_3 > 2r_02r_5\,\!</math>
e em geral
:<math>r_{k-1}>2r_{k+12}\,\!</math>, para cada <math>k\ge 10\,\!</math>.
 
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)< 2(N2N\cdot\log_2 10) + 12\,\!</math>, ouque numericamente,para valores grandes de <math>k N\approx,\!</math> é aproximadamente <math>6,6N\,\!</math>.
 
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+-1} + r_{j+1} \Rightarrow r_{j-1} = r_j + r_{j+1}\,\!</math>
 
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+-1} = 1\,\!</math> produzem as seguintes igualdades:
:<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+21} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix}</math>, sendo que <math>d=(a,b)\,\!</math>.
 
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+32} & F_{k+21}\\ F_{k+21} & F_{k+1} \end{bmatrix} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = \begin{bmatrix} d\cdot F_{n+32} \\ d\cdot F_{k+21} \end{bmatrix}</math>
 
Como <math>d=(a,b)\ge 1\,\!</math>, segue que
* <math>a\ge F_{n+32}\,\!</math>
* <math>b\ge F_{n+21}\,\!</math>
 
=== Teorema de Lamé ===