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 Desfeita a edição 83175 de Albmont (Usuário Discussão:Albmont) |
m +links p. wikipedia |
||
Linha 27:
O ''máximo divisor comum'' (abreviadamente MDC) entre <math>a\,\!</math> e <math>b\,\!</math> é o maior elemento do conjunto <math>D(a,b)\,\!</math>, e será denotado por <math>mdc(a,b)\,\!</math>, ou simplesmente <math>(a,b)\,\!</math>.
}}
{{Wikipedia|Números primos entre si}}
Quando o conjunto <math>D(a,b)\,\!</math> possui apenas um elemento, ou seja, quando <math>mdc(a,b)=1\,\!</math>, os números <math>a\,\!</math> e <math>b\,\!</math> são ditos ''
==== Exemplo ====
Linha 41:
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}}
O resultado também é conhecido como
Antes de apresentar qualquer justificativa ([[#Demonstração do teorema de Bézout|construtiva]] ou [[#Demonstração alternativa do teorema de Bézout|puramente algébrica]]) dessa identidade, serão mostradas suas consequências imediatas mais importantes.
Linha 59:
Claramente, <math>m\,\!</math> divide cada parcela desta soma. Consequentemente deve dividir <math>b\,\!</math>.
}}
{{Wikipedia|Euclides}}
Com essa propriedade,
=== Propriedade fundamental dos primos ===
Linha 113:
:<math>(a,b) = (a-b)u+bv = au + b(v-u)\,\!</math>
}}
{{Wikipedia|Algoritmo}}
Como toda prova por indução, a demonstração anterior fornece um
'''Dados de entrada'''
Linha 151 ⟶ 152:
''Dados os números inteiros <math>a\,\!</math> e <math>b\,\!</math>, ou <math>a\,\!</math> é múltiplo de <math>b\,\!</math> ou está entre dois múltiplos consecutivos de <math>b\,\!</math>.''
{{Wikipedia|Princípio da boa ordenação}}
{{Demonstração|
Considere inicialmente que <math>a>0\,\!</math>.
Linha 157 ⟶ 158:
Se <math>X = \{ a-bt: t\in \mathbb{Z}\} \subseteq \mathbb{Z}\,\!</math>, então <math>X' = X \cap \mathbb{N} \not=\emptyset\,\!</math> (pois para <math>t=0\,\!</math> tem-se <math>a-bt = a >0\,\!</math>).
Logo, pelo
Como <math>r \in X'\,\!</math>, segue que <math>r = a-bq\,\!</math>, para algum inteiro <math>q\,\!</math>, e <math>r\ge 0\,\!</math>.
Linha 188 ⟶ 189:
Observe que esta é simplesmente uma generalização do algoritmo apresentado logo após a [[#Demonstração do teorema de Bézout|demonstração do teorema de Bézout]].
{{Wikipedia|Algoritmo de Euclides}}
É preciso verificar que <u>o algoritmo irá parar</u>, e ainda mais importante, que <u>fornecerá a resposta correta</u>.
Linha 380 ⟶ 381:
:<math>\ldots\,\!</math>
{{Wikipedia|Progressão geométrica#Progressão geométrica decrescente}}
Por indução, resulta para cada termo:
Linha 388 ⟶ 389:
:<math>r_{2j+1}<a/2^{j+1}\,\!</math>
Com isso, a sequência dos <math>r_j\,\!</math> decresce
A questão colocada era: ''Quantas divisões são necessárias para que o resto <math>r_{k+1}\,\!</math> seja zero?''
| |||