Introducao a Algebra Abstrata

que b|c.
c) De b|ai, para i = 1, ..., n, segue que existem qi, i = 1, ..., n, tais que ai = b . qi, i = 1, ..., n. 
Daí, para quaisquer os inteiros c1, ..., cn, c1 . a1 + ... + cn . an = c1 . (b . q1) + ... + cn . (b . qn), o que 
resulta em c1 . a1 + ... + cn . an = b . (c1 . q1 + ... + cn . qn).
Se a1, ..., an são números inteiros, uma expressão do tipo c1 . a1 + ... + cn . an, com c1, ..., cn 
inteiros é chamada combinação linear de a1, ..., an de coeficientes c1, ..., cn. O item c da proposição 
anterior diz que se um inteiro b divide os inteiros a1, ..., an, então b divide qualquer combinação 
linear desses inteiros. 
5.3 Divisão euclidiana
Duas perguntas que podem ser feitas são: como determinar q quando b|a? como saber quando 
b|/a? O teorema a seguir, além de responder estas perguntas, é fundamental para o estabelecimento 
de uma forma inteligente de se representar os números inteiros.
Teorema 1.5 (divisão euclidiana) 
Dados dois inteiros a e b, com b ≠ 0, existem inteiros q e r tais que a = b . q + r e 0 ≤ r < |b|. 
Além disso, os inteiros q e r que satisfazem às relações acima são únicos. 
Demonstração 
Pela propriedade arquimediana discutida no corolário 5.3, existe um inteiro n tal que
n . (-b) ≥ -a. Isto garante que o conjunto S = {z ∈ ℤ| z ≥ 0 e z = a - b . n, para algum n ∈ ℤ} é não 
vazio. Como S é limitado inferiormente, pelo princípio da boa ordenação, S tem um elemento 
mínimo r. Como r ∈ S, r ≥ 0 e r = a - b . q para algum inteiro q. Ou seja, existem inteiros q e r tais 
que a = b . q + r e r ≥ 0. Para a primeira parte do teorema, falta mostrar que r < |b|. Suponhamos, 
por absurdo, que r ≥ |b|. Assim, r > r - |b| ≥ 0. Agora, de a = b . q + r segue a = b . q + r + |b| - |b| 
que implica a = b . (q ± 1) + (r - |b|), onde q ± 1 indica a expressão “q + 1 ou q − 1”. Daí, 
r - |b| = a - b . (q ± 1), o que mostra r - |b| ∈ S, contrariando o fato de r ser o elemento mínimo de S. 
Para provar que q e r são únicos, suponhamos que a = b . q1 + r1 = b . q2 + r2, com 0 ≤ r1 < |b| e 
0 ≤ r2 < |b|.
De r1 < |b| segue que r1 - r2 < |b|, pois - r2 < 0. Por outro lado, de r2 < |b| segue que -|b| < -r2 o 
que implica -|b| < r1 – r2, pois 0 ≤ r1. Assim -|b| < r1 - r2 < |b| e então, pelo item d da proposição 9.3,
|r1 - r2| < |b|.
Agora de b . q1 + r1 = b . q2 + r2 temos que b . (q1 - q2) = r2 – r1 e, como consequência da já 
citada proposição 8.3, |b| . |q1 - q2| = |r2 – r1|. Assim, utilizando a desigualdade |r1 - r2| < |b| mostrada 
acima, |b| . |q1 - q2| < |b| e então |q1 - q2| < 1. Daí, |q1 - q2| = 0 resultando q1 = q2. Da igualdade
b . (q1 - q2) = r2 - r1, segue r2 = r1, o que conclui a demonstração.
Na divisão euclidiana a = b . q + r, com 0 ≤ r < |b|, a e b são, respectivamente, o dividendo e 
o divisor e q e r são o quociente e o resto da divisão de a por b, que podem ser indicados por
q(a, b) e r(a, b). A divisão euclidiana de a por b pode ser indicada por a ÷ b.
Observe que se r(a, b) = 0, temos que b|a e se r(a, b) ≠ 0, temos b|/a. 
Por exemplo, q(7, 3) = 2 e r(7, 3) = 1, pois, é fácil ver que 7 = 3 . 2 + 1. Assim, 3|/7.
A determinação do quociente e do resto da divisão de um inteiro a por um inteiro b, no caso 
a ≥ 0 e b > 0, pode ser feita através do seguinte algoritmo.
algoritmo Divisão euclidiana
leia(a, b);
q := 1;
59
Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão
repita enquanto b . q ≤ a
q := q + 1;
q := q - 1;
r := a - b . q;
escreva(q, r);
A propriedade arquimediana (corolário 5.3) nos garante que este algoritmo para, pois ela 
assegura a existência de um inteiro z tal que z . b > a. A interrupção do comando de repetição ocorre 
na primeira vez que b . q > a, porém o comando q := q - 1 faz com que se retorne à desigualdade
b . q ≤ a. Do comando r := a - b . q segue que a = b . q + r e o fato de que b . q ≤ a tem como 
consequência r ≥ 0. Resta mostrar que r < b. Se r ≥ b, a - b . q ≥ b e, então, a ≥ b . (q + 1). Mas isso 
é uma contradição, pois q é o maior inteiro tal que b . q ≤ a.
Para exemplificar, a tabela abaixo simula a execução do algoritmo Divisão euclidiana para 
a = 11 e b = 2.
a b q r
11 2 1
2
3
4
5
6
5 1
O exercício 5.2 dará indicação para determinação de quocientes e restos de divisões a ÷ b 
quando a < 0 ou b < 0.
Dois resultados a respeito do quociente e do resto da divisão euclidiana de dois inteiros 
positivos são imediatos, mas são indispensáveis para o estabelecimento de uma forma de se 
representar os inteiros.
Proposição 4.5
Sejam dois inteiros a e b, com a, b > 0, e q = q(a, b). Então
a) q ≥ 0.
b) Se b > 1, então a > q.
Demonstração 
a) De a = b . q + r, com 0 ≤ r < b, segue que a < b . q + b o que implica a < b . (q + 1). Por 
redução ao absurdo, se q < 0, temos q ≤ -1 e, então, q + 1 ≤ 0. Daí e da desigualdade anterior
a < b . (q + 1) segue a ≤ 0, o que contraria a hipótese.
b) Do item anterior segue que q ≥ 0. Se q = 0, a hipótese a > 0 já diz que a > q. Se q > 0, de
b > 1 segue que b . q > q. Daí e de r ≥ 0, segue que b . q + r > q e portanto a > q. 
5.4 Sistemas de numeração
Seja b um inteiro maior que 1. Uma forma de se representar os números inteiros consiste em 
se adotar símbolos, chamados algarismos, para representar os b menores inteiros maiores do que ou 
iguais a zero e utilizá-los de acordo com a sua posição na representação para indicar os demais 
inteiros. Isto será mais bem esclarecido após o entendimento do seguinte teorema.
60
Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão
Teorema 2.5
Sejam os inteiros a e b, com a > 0 e b > 1. Então existem inteiros positivos n, c0, c1, ..., cn, 
com 0 ≤ ci < b, para todos i = 0, 1, ..., n, tais que a = cn . bn + cn-1 . bn-1 + ... + c1 . b + c0. 
Além disso, c0, c1, ..., cn são únicos.
Demonstração
Pela divisão euclidiana temos que existem únicos q0 e c0 tais que a = b . q0 + c0, 0 ≤ c0 < b. Da 
mesma forma existem únicos q1 e c1 tais que q0 = b . q1 + c1, 0 ≤ c1 < b.
Seguindo este raciocínio obtemos q1 = b . q2 + c1, 0 ≤ c2 < b; q2 = b . q3 + c1, 0 ≤ c3 < b; …;
qn-2 = b . qn-1 + cn-1, 0 ≤ cn-1 < b; qn-1 = b . qn + cn, 0 ≤ cn < b; …, com cada ci e cada qi únicos. 
Pela proposição 1.5, como a > 0 e b > 1, temos que qi ≥ 0 e qi+1 < qi, para todo i = 0, 1, ..., 
n, .... Assim obtemos uma sequência q0 > q1 > ... > qn > ... ≥ 0 e então pelo corolário 6.3, existe n tal 
qn = 0. Logo, qn-1 = cn e, por substituição,
qn-2 = b . cn + cn-1
qn-3 = b . (b . cn + cn-1) + cn -2 = cn . b2 + cn-1 . b + cn-2
. . .
a = cn . bn + cn-1 . bn-1 + ... + c1 . b + c0
com c0, c1, ..., cn únicos, como queríamos demonstrar.
A expressão a = cn . bn + cn-1 . bn-1 + ... + c1 . b + c0, com 0 ≤ ci < b, i = 0, 1, ..., n é chamada 
expansão b-ádica do inteiro a, com denominações particulares para alguns valores de b: para b = 2, 
expansão binária; para b = 3, expansão ternária.
Por exemplo, como
11 = 2 . 5 + 1,
5 = 2 . 2 + 1,
2 = 2 . 1 + 0,
1 = 2 . 0 + 1,
temos
5 = 2 . 2 + 1 = 2 . (2 . 1 + 0) + 1 = 1 . 22 + 0 . 2 + 1. 
11 = 2 . 5 + 1 = 2 . (1 . 22 + 0 . 2 + 1) + 1 = 1 . 23 + 0 . 22 + 1 . 2 + 1, 
e, assim 1 . 23 + 0 . 22 + 1 . 2 + 1 é a expansão binária de 11.
Dado um inteiro b > 1, o sistema de numeração de base b é obtido definindo-se um conjunto 
de b símbolos (os símbolos 0 e 1 incluídos) para representar os inteiros ci, i = 0, 1, ..., b - 1, com
0 ≤ ci < b, representando-se então um inteiro positivo a de expansão b-ádica
a = cn . bn + cn-1 . bn-1 + ... + c1 . b + c0
por
a = (cncn-1...c1c0)b,
onde, aí, estamos identificando ci com o símbolo que o representa. O inteiro (0cncn-1...c1c0)b é 
identificado com o inteiro (cncn-1...c1c0)b e um inteiro negativo é representado pelo seu simétrico 
precedido do sinal – (lido menos). Em a = (cncn-1...c1c0)b, dizemos que c0, ..., cn são os dígitos ou 
algarismos de a no sistema de base b e n + 1 é dito número de dígitos de a. Dizemos também que 
c0 é o algarismo da casa das unidades.
É interessante