Universidade Federal do Rio de Janeiro
Instituto de Matemática
Prof. Tulio Gentil
Álgebra I - Números Inteiros
Aula 07 - Divisibilidade e o Algoritmo de Euclides
1 Algoritmo da divisão de Euclides
Sejam a, b ∈ Z. Dizemos que b divide a (ou que b é um divisor de a, ou que a é um
múltiplo de b) se existe c ∈ Z tal que a = b · c.
Usaremos a notação b|a para indicar que b divide a. Usamos a notação b ̸ |a para
indicar que b não divide a.
Observe que, se b ̸= 0, o inteiro c da definição é único. De fato, suponha que existam
c1 , c2 ∈ Z tais que a = b · c1 e a = b · c2 , então b · c1 = b · c2 , como Z é um domínio de
integridade e b ̸= 0, pela lei do cancelamento, c1 = c2 . Neste caso, o inteiro c é chamado
quociente de a por b e é denotado por
a
c = a/b = .
b
No caso em que b = 0, então 0|a se, e somente se a = 0. Nesse caso, para todo c ∈ Z
tem-se que 0 = 0 · c. Por essa razão, vamos excluir o caso em que o divisor é zero.
Proposição 1.1. Se b|a e a ̸= 0, então |b| ≤ |a|.
Demonstração. Como b|a, existe c ∈ Z tal que a = b · c e assim, |a| = |b| · |c|. Como
|c| > 0, temos que |c| ≥ 1 e, multiplicando ambos os membros dessa desigualdade por
|b| > 0, temos que |b| ≤ |b| · |c| = |a|.
Corolário 1.2. i) Os únicos divisores de 1 são 1 e −1.
ii) Se b|a e a|b então a = ±b.
Demonstração. i) Seja b ∈ Z um divisor de 1 (b|1), então pela Proposição 1.1, |b| ≤ 1.
Portanto, −1 ≤ b ≤ 1. Como b ̸= 0, b = ±1.
ii) Se b|a e a|b, então existem inteiros c1 e c2 tais que ac1 = b e bc2 = a. Logo,
ac1 c2 = a.
Como a ̸= 0, c1 c2 = 1 e assim c2 |1. Por i), c2 = ±1 e consequentemente a = ±b.
A seguir enunciamos propriedades importantes da divisibilidade, onde estamos sempre
assumindo que o divisor é não nulo.
Proposição 1.3. (Propriedades da divisibilidade) Sejam a, b, c, d números inteiros, então
i) a|a;
ii) Se a|b e b|c, então a|c;
iii) Se a|b e c|d, então ac|bd;
iv) Se a|b e a|c, então a|b + c;
v) Se a|b, então para todo m ∈ Z, tem-se que a|mb;
vi) Se a|b e a|c, então, a|(mb + nc), quaisquer que sejam m, n ∈ Z.
Demonstração. i) Observe que a = a · 1;
ii) Se a|b e b|c, então existem inteiros c1 e c2 tais que b = ac1 e c = bc2 e portanto,
c = a(c1 c2 ). Concluímos que a|c.
iii) Exercício.
iv) Exercício.
v) Se a|b, então existe c ∈ Z tal que b = ac. Multiplicando ambos os membros da
equação b = ac por m, obtemos bm = a(cm) e portanto, a|bm.
vi) Segue dos itens v) e iv).
Teorema 1.4. (Algoritmo da divisão) Sejam a, b ∈ Z, com b ̸= 0. Então, existem únicos
q e r números inteiros tais que a = b · q + r e 0 ≤ r < |b|.
Demonstração. Vamos mostrar, primeiramente, que podemos determinar q e r quando
b > 0 e a é qualquer e dividimos essa prova nos dois casos abaixo.
• (Caso a ≥ 0 e b > 0) Considere o conjunto
S = {a − bx | x ∈ Z, a − bx ≥ 0}.
Note que S ̸= ∅, pois para x = 0, a − bx = a ∈ S. Pelo Princípio da Boa Ordem,
existe r = min S. Como r ∈ S, r = a − bq ≥ 0 para algum q ∈ Z. Bata mostrar
então que r < b. Suponha que r ≥ b, então
a − b(q + 1) = a − bq − b = r − b ≥ 0
e pela definição de S, teríamos a − b(q + 1) = r − b < r = min S, uma contradição.
• (Caso a < 0 e b > 0) Pelo ponto anterior, podemos determinar, q ′ e r′ tais que
|a| = bq ′ + r′ , 0 ≤ r′ < b.
Se r′ = 0, então −|a| = a = b(−q ′ )+0 e então q = q ′ e r = 0 satisfazem as condições
do Teorema.
Se r′ > 0, então
a = −|a| = b(−q ′ ) − r′ = b(−q ′ ) − b + b − r′ = b(−q ′ − 1) + (b − r′ ).
Note que, neste caso, 0 < b − r′ < b; basta tomar q = −q ′ − 1 e r = b − r′ .
Agora, vamos mostrar que o resultado vale para b < 0. Pelo que fizemos acima,
podemos determinar inteiros q ′ e r′ tais que
a = |b|q ′ + r′ , 0 ≤ r′ < |b|.
Neste caso, temos que |b| = −b, logo
a = |b|q ′ + r′ = (−b)q ′ + r′ = b(−q ′ ) + r′
e basta tomar q = −q ′ e r = r′ .
Por fim, mostraremos que se dois pares de inteiros (q, r) e (q ′ , r′ ) satisfazem as condições
do resultado, então q = q ′ e r = r′ . Temos que
qb + r = a = q ′ b + r′ .
Sem perda de generalidade, podemos supor r′ ≥ r. Segue de qb + r = a = q ′ b + r′ que
(q − q ′ )b = r′ − r.
Como r′ < |b|, segue que r − r′ < |b| e assim,
(q − q ′ )b < |b|.
Tomando módulos na desigualdade acima, segue que
0 ≤ |q − q ′ ||b| < |b|,
o que implica que
0 ≤ |q − q ′ | < 1.
Como q e q ′ são números inteiros, segue que q − q ′ = 0, ou seja q = q ′ . Pela igualdade
qb + r = a = q ′ b + r′ , concluímos que r = r′ .
Os números inteiros q e r unicamente determinados no Algoritmo da divisão são cha-
mados, respectivamente, quociente e resto da divisão de a por b.