Divisibilidade e o MDC – Csaba Schneider

Sejam

a, b \in Z

. Dizemos que $b$ divide $a$ ou que $a$ é um múltiplo de $b$ se existe

q \in Z

, tal que

b q = a

. Usamos a notação

b | a

para indicar que

b

divide

a

$\pm a | a$ e $\pm 1 | a$ para todo inteiro $a$ .
$a | 0$ para todo inteiro $a$ , mas se $0 | a$ então $a = 0$ . Em particular $0 | 0$ .

As seguintes propriedades são válidas.

Se $a | b$ e $b | a$ então $b = \pm a$ .
Se $a | b$ e $b | c$ então $a | c$ .
Se $a | b$ e $a | c$ então $a | (b \pm c)$ .
Se $a | b$ e $c$ é um inteiro então $a | b c$ .

Exercício.

Sejam

a

b

números inteiros não simultaneamente iguais a zero. Definimos o maior divisor comum de $a$ e $b$ como sendo o inteiro

d

que satisfaz as seguintes propriedades:

$d \geq 0$ ;
$d | a$ e $d | b$ ;
se $c$ é um inteiro tal que $c | a$ e $c | b$ então $c | d$ .

Não é imediatamente claro da definição que o maior divisor comum existe. No entanto, segue da definição que se ele existir, então ele deve ser único. Isso porque se $d_{1}$ e $d_{2}$ são mdcs de $a$ e $b$ , então a definição implica que $d_{1} | d_{2}$ e $d_{2} | d_{1}$ . Ora temos pelo lema anterior que $d_{1} = \pm d_{2}$ , mas como $d_{1}$ e $d_{2}$ são não negativos, isso é possível apenas quando $d_{1} = d_{2}$ .

O maior divisor comum de $a$ e $b$ será denotado por $mdc (a, b)$ .

É claro que $mdc (a, b) = mdc (b, a)$ e que $mdc (a, b) = mdc (\pm a, \pm b)$ . A definição também implica que $mdc (a, 0) = | a |$ para todo $a \neq 0$ .

a

b

são inteiros tais que

mdc (a, b) = 1

, então dizemos que

a

b

são primos entre si ou que eles são coprimos.

Sejam

a, b \in Z

com

b \neq 0

e escreve

a = q b + r

com

0 \leq r < | b |

como no Teorema de Divisão de Euclides. Então

mdc (a, b) = mdc (b, r)

(assumindo que existem estes mdcs).

Seja

d = mdc (a, b)

. Afirmamos que

mdc (b, r) = d

. Primeiro,

d \geq 0

pela definição de mdc (propriedade 1. do mdc). Como

d = mdc (a, b)

, temos que

d | a

d | b

. Pelo lema anterior, isto implica que

d | (a - q b) = r

. Logo

d | b

d | r

(propriedade 2. do mdc).

O lema anterior pode ser usado para determinar o mdc de dois números naturais do modo seguinte. Sejam,. por exemplo,

a = 115

b = 25

. Escreva

115 = 4 \cdot 25 + 10

para concluir que

mdc (115, 25) = mdc (25, 10)

. Depois escreva

25 = 2 \cdot 10 + 5

e obtenha que

mdc (25, 10) = mdc (10, 5)

.
Depois

10 = 2 \cdot 5 + 0

que implica que

mdc (10, 5) = mdc (5, 0) = 5

. Logo

mdc (115, 25) = mdc (25, 10) = mdc (10, 5) = mdc (5, 0) = 5.

Esta conta segue essencialmente o Algoritmo de Euclídes que será o conteúdo da semana seguinte.