A maior rede de estudos do Brasil

Grátis
126 pág.
Introducao a Algebra Abstrata

Pré-visualização | Página 26 de 47

de um número inteiro dado: y é 
divisor de z (simbologia y|z) se existe q tal que z = y . q. Nesta seção, procuraremos analisar os 
divisores comuns de dois inteiros dados, em particular, o maior destes divisores comuns, chamado, 
por razões óbvias, de máximo divisor comum dos dois números e indicado por mdc(z, y). Por 
exemplo, como os divisores positivos de 20 são 1, 2, 4, 5, 10 e 20 e os divisores de 24 são 1, 2, 3, 4, 
6, 8, 12 e 24, temos que mdc(20, 24) = 4.
Observe que este exemplo já indica um algoritmo para se determinar o máximo divisor 
comum de dois inteiros z e y: 1. Determina-se os conjuntos D(z) e D(y) contendo todos os divisores 
de z e de y; 2. Determina-se o conjunto D(z) ∩ D(y); 3. Determina-se o maior elemento de D(z) ∩ 
D(y). O problema com este algoritmo é que, como será mostrado adiante, não existe algoritmo 
eficiente para obtenção de divisores de um número muito grande (aí, algoritmo eficiente significa 
que seja um algoritmo que forneça sua saída num tempo razoável). 
Apresentaremos a seguir um algoritmo (concebido pelo matemático grego Euclides, que viveu 
de 330 a. C. a 275 a. C., na cidade de Alexandria, na Grécia) que calcula de forma eficiente o 
máximo divisor comum de dois números dados. A demonstração do algoritmo de Euclides requer o 
resultado dado no seguinte lema.
Lema 1.6
Se z, y são inteiros positivos, então mdc(z, y) = mdc(y, z - y . m), qualquer que seja o inteiro m.
Demonstração
Sejam d1 = mdc(z, y) e d2 = mdc(y, z - y . m). Vamos mostrar que d2 ≤ d1 e que d1 ≤ d2 . De
d2 = mdc(y, z - y . m) temos que d2|y e d2|(z - y . m). Daí, d2|z. Assim, d2 é divisor comum de z e y e 
então d2 ≤ d1, já que d1 = mdc(z, y).
Mutatis mutandis se demonstra que d1 ≤ d2 (mutatis mutandis é uma expressão latina que 
significa mudando o que se deve).
Observe que se tomarmos m = q( z, y), temos que z - y . m = r, onde r = r(z, y). Dessa forma, 
temos o seguinte corolário do lema 1.6.
Corolário 1.6
Se z, y são inteiros positivos e r = r(z, y), então mdc(z, y) = mdc(y, r).
Com a utilização deste corolário, a determinação de mdc(20, 24) seria: 
mdc(20, 24) = mdc(24, 20) = mdc(20, 4) = mdc(4, 0) = 4, 
sendo esta última igualdade explicada pelo fato de que 4|0 e 4 é, obviamente, o maior divisor de 4.
A aplicação do corolário pode ser simplificada pelo fato de que o máximo divisor satisfaz às 
seguintes propriedades que decorrem imediatamente da definição e cujas demonstrações serão 
70
Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão
deixadas como exercício.
Propriedades do máximo divisor comum
a) mdc(a, b) = mdc(|a|, |b|).
b) mdc(a, b) = mdc(b, a).
c) Se b|a, então mdc(a, b) = |b|. 
Por exemplo, mdc(504, 540) = mdc(540, 504) = mdc(504, 36) = 36, pois 36|504. 
Outro exemplo: mdc(200, 73) = mdc(73, 54) = mdc(54, 19) = mdc(19, 16) = mdc(16, 3) =
= mdc(3, 1) = 1. 
Teorema 1.6 (algoritmo de Euclides)
Sejam z e y dois inteiros positivos. Se
z = y . q1 + r1, com 0 ≤ r1 < y
y = r1 . q2 + r2, com 0 ≤ r2 < r1
r1 = r2 . q3 + r3, com 0 ≤ r3 < r2
r2 = r3 . q4 + r4, com 0 ≤ r4 < r3
. . .
rn-4 = rn-3 . qn-2 + rn-2, com 0 ≤ rn-2 < rn-3
rn-3 = rn-2 . qn-1 + rn-1, com 0 ≤ rn-1 < rn-2
rn-2 = rn-1 . qn + rn, com 0 ≤ rn < rn-1
. . .,
então existe n tal que rn = 0 e rn-1 = mdc(z, y). 
Além disso, existem inteiros t e u tais que t . z + u . y = mdc(z, y).
Demonstração
Das desigualdades relativas aos restos, temos que y > r1 > r2 > r3 > ... > rn > ... ≥ 0 e então, 
pelo corolário 5.3, existe n tal que rn = 0. Por outro lado, pelo corolário 1.6, mdc(z, y) = mdc(y, r1) =
= mdc(r1, r2) = mdc(r2, r3) = … = mdc(rn-3, rn-2) = mdc(rn-2, rn-1) = rn-1. 
Além disso, de mdc(z, y) = rn-1 segue mdc(z, y) = rn-3 - rn-2 . qn-1, na qual podemos substituir
rn-2 = rn-4 - rn-3 . qn-2, obtendo mdc(z, y) = rn-3 - (rn-4 - rn-3 . qn-2). qn-1. Nesta igualdade podemos 
substituir rn-3 = rn-5 - rn-4 . qn-3, e, seguindo substituindo retroativamente, encontraremos t e u tais que
t . z + u . y = mdc(z , y).
A aplicação deste algoritmo “na mão” (isto é, com lápis e papel) pode ser feita no esquema 
abaixo, onde calculamos mdc( 396, 84):
396 84 60 24 12 0
4 1 2 2
concluindo que mdc(396, 84) = 12.
Observe que este esquema é simplesmente uma maneira prática de se realizar as divisões
396 = 84 . 4 + 60,
84 = 60 . 1 + 24,
60 = 24 . 2 + 12,
24 = 12 .2 e r4 = 0.
Para encontrar os inteiros m e n tais que m . 396 + n . 84 = 12 temos as seguintes igualdades:
12 = 60 – 2 . 24, 
12 = 60 – 2 . (84 – 1 . 60) = -2 . 84 + 3 . 60,
12 = -2 . 84 + 3 . (396 - 84 . 4) = 3 . 396 – 14 . 84,
71
Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão
e, portanto, m = 3 e n = -14.
É interessante observar que a recíproca da segunda parte do teorema anterior não é verdadeira. 
Isto é, se z, y e d são inteiros e existem inteiros t e u tais t . z + u . y = d não se tem necessariamente
d = mdc(z, y). Por exemplo, existem inteiros t e u (t = 2 e u = -2) tais que 15 . t + 10 . u = 10 mas 
mdc(15, 10) = 5. Mostraremos na próxima seção que esta recíproca é verdadeira quando o máximo 
divisor comum dos dois inteiros é igual 1. 
Na linguagem algorítmica estabelecida no capítulo 4, a parte do Algoritmo de Euclides que 
trata da determinação do máximo divisor comum de dois inteiros (quando ambos são positivos) 
seria escrita da seguinte forma: 
algoritmo deEuclides;
leia(a, b);
r := resto(a, b);
repita enquanto r > 0
a := b;
b := r;
r := resto(a, b);
mdc := b;
escreva(mdc);
A eficiência deste algoritmo, que é medida pelo números de iterações do comando repita 
enquanto, será discutida no capítulo 9.
A escrita da segunda parte do Algoritmo de Euclides (a que trata da existência de inteiros t e u 
tais que t . z + u . y = mdc(z, y)) na linguagem algorítmica foge ao escopo do livro. 
6.3 Inteiros primos entre si
Na seção anterior afirmamos que a recíproca da segunda parte do Algoritmo de Euclides (se
d = mdc(z, y), então existem inteiros t e u tais que t . z + u . y = d) só era verdadeira se d = 1. Ou 
seja, como veremos na proposição seguinte, se existem inteiros t e u tais que t . z + u . y = 1, então 
mdc(z, y) = 1. Além da veracidade desta recíproca, o fato de o máximo divisor comum de dois 
inteiros ser igual a 1 é importante pois ele gera outras propriedades interessantes. Para facilitar a 
linguagem, quando mdc(z, y) = 1, dizemos que os dois inteiros z e y são primos entre si (ou co-
primos) ou que um dos inteiros é primo em relação ao outro. Observe que desta definição decorre 
que dois inteiros primos entre si não possuem divisores positivos comuns diferentes de 1 (um).
Proposição 1.6
Sejam z e y dois inteiros. Se existem inteiros t e u tais que z . t + y . u = 1, então mdc(z, y) = 1. 
Demonstração
Seja d = mdc(z, y). Assim, d|z e d|y o que implica d|(z . t + y . u). Daí, d|1 o que acarreta
d = 1, já que d > 0.
As outras propriedades de pares de inteiros primos entre si são apresentadas na seguinte 
proposição.
Proposição 2.6
Sejam a, b e c inteiros positivos, com a e b primos entre si. Então
a) Se b|(a . c), então b|c.
b) Se a|c e b|c, então (a . b)|c.
Demonstração
72
Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão
a) Como a e b são primos entre si, existem inteiros m e n tais que a . m + n . b = 1. Daí, 
multiplicando ambos os termos desta igualdade por c, temos a . m . c + n . b . c = c. Como b divide 
as duas parcelas, temos b|c.
b) Da hipótese de que a|c temos que existe q1 tal que c = a . q1. Assim, da hipótese b|c, segue 
que b|(a . q1). Então, pelo item (a), b|q1 e, portanto, existe q2 tal que q1 = b . q2. Substituindo isto em 
c = a . q1, temos que c = a . b . q2, o que mostra que (a . b)|c.
Observe que a hipótese de que a e b são primos entre si é crucial para as conclusões da 
proposição. Por exemplo, 6|(3 . 8) e 6 não divide 3, nem divide 8; 3|24 e 6|24, porém 3 . 6 = 18 não 
divide 24.
6.4 Equações diofantinas
Do algoritmo de Euclides também decorre a