Seção 3.1 Máximo Divisor Comum
Teorema 3.1.1.
Sejam \(a\) e \(b\) números inteiros com \(b\neq 0\text{.}\) Então existem únicos inteiros \(q\) e \(r\) tais que
O número \(a\) é chamado de dividendo, o número \(b\) é chamado de divisor, o número \(q\) é chamado de quociente e o número \(r\) é chamado de resto.
Tecnologia 3.1.2.
Escolha valores para \(a\) e \(b\) para obter os valores do quociente e resto na divisão de \(a\) por \(b\text{.}\)
Definição 3.1.4.
Sejam \(a\) e \(b\) dois inteiros, diz-se que o inteiro positivo \(d\) é o máximo divisor comum de \(a\) e \(b\text{,}\) e denotamos por \(d=mdc(a,b)\text{,}\) se \(d\) satisfaz as seguintes condições:
- \(d\) é um divisor comum de \(a\) e \(b\text{,}\) ou seja, \(d|a\) e \(d|b\text{;}\)
- \(d\) é divisível por todo divisor comum de \(a\) e \(b\text{,}\) isto é, se \(c\) é divisor comum de \(a\) e \(b\text{,}\) então \(c|d\text{.}\)
Tecnologia 3.1.5.
Método \(\verb|gcd|\) para calcular MDC.
Teorema 3.1.6. (Algoritmo de Euclides para calcular o MDC).
Sejam \(a\) e \(b\) inteiros positivos. O \(mdc(a,b)\) pode ser calculado com os seguintes passos.
- Faça \(i=1\text{,}\) \(r_0=max\{a,b\}\) e \(r_1=min\{a,b\}\text{;}\)
- Defina \(r_{i+1}\) como o resto da divisão de \(r_{i-1}\) por \(r_i\text{,}\) isto é, \(r_{i-1}=q_ir_i+r_{i+1}\) com \(0\leq r_{i+1}\lt r_i\text{;}\)
- Se \(r_{i+1}\neq0\) incremete \(i\) de 1 e volte para o passo 2, caso contrário \(mdc(a,b)=r_i\text{.}\)
Tecnologia 3.1.7.
Escolha valores para \(a\) e \(b\) para obter todos os passos do algoritmo descrito no teorema anterior.
Tecnologia 3.1.9.
Dados números inteiros \(a_1, a_2, \ldots, a_n\text{,}\) não todos nulos, existe seu MDC e
Para obter o MDC de vários números inteiros, digite os números em uma lista como abaixo e aperte no botão "Update".
Teorema 3.1.11.
(Bachet-Bézout). Se \(a\) e \(b\) são inteiros, um dos quais não é nulo, então existem inteiros \(x\) e \(y\) tais que
Método xgcd do SageMath
Tecnologia 3.1.12.
Escolha valores para \(a\) e \(b\) para obter todos os passos até obter o MDC entre \(a\) e \(b\) os valores de \(x\) e \(y\text{,}\) conforme o Teorema anterior.