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 →Exercícios: +ex.1 lista1 |
m ajustando ligações |
||
Linha 144:
Em geral, será buscado um valor <math>q\,\!</math> tal que <math>0\le a-bq<b\,\!</math>, pois assim a igualdade <math>(a,b) = (a-bq,b)\,\!</math> (que é sempre verdadeira, para qualquer valor inteiro de <math>q\,\!</math>) reduz o cálculo de <math>(a,b)\,\!</math> a um caso bem mais simples.
A existência de um número <math>q\,\!</math>, satisfazendo ambas as desigualdades é garantida pelo ''[[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo da divisão]]'' apresentado em um capítulo anterior. Se precisar relembrar os detalhes, consulte a seção "[[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|Algoritmo da divisão (de Euclides)]]".
De posse deste algoritmo, pode-se fazer uma melhoria no algoritmo sugerido anteriormente para o cálculo do MDC.
Linha 172:
É 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 [[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo da divisão]]):
:{| cellpadding=0px cellspacing=6px
Linha 344:
:Se <math>J\,\!</math> é subgrupo de <math>\mathbb{Z}\,\!</math>, então <math>J\,\!</math> possui elementos não-negativos. Em particular, <math>J\,\!</math> possui um ''menor elemento'' não-negativo <math>m\,\!</math>.
:Se <math>z \in J\,\!</math> então pelo [[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo de divisão
:Donde <math>r = z- mq \in J\,\!</math>.
:Como <math>0\le r<m\,\!</math>, segue que <math>r = 0\,\!</math>, ou seja, <math>z = mq \in \mathbb{Z}\,\!</math>.
Linha 361:
== Exercícios ==
# O [[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|algoritmo da divisão]] estabelece que dados os inteiros <math>a,b\,\!</math>, existem inteiros <math>q, r\,\!</math> tais que <math>a = bq + r\,\!</math>, com <math>0\le r<b\,\!</math>. Utilize uma calculadora comum (e apenas as quatro operações elementares) para obter os valores de <math>q, r\,\!</math> correspondentes a alguns pares de inteiros <math>a,b\,\!</math>.
# Dados ''a'' e ''b'', determine o valor de ''mdc(a,b)'' e números inteiros ''x'', ''y'' tais que ''d = xa + yb, para os seguintes valores de ''a'' e ''b'':
## a = 299 e b = 161
Linha 369:
[[Categoria:
| |||