04 TopicosdeAlgebra
97 pág.

04 TopicosdeAlgebra


DisciplinaMatemática78.260 materiais1.407.245 seguidores
Pré-visualização27 páginas
o resultado do Lema da Divisão Euclidiana, já estudado por nós.
ER 8. Calcule o mdc(15, 4).
Solução: Fazendo as divisões sucessivas de 15 por 4 teremos
15 = 3 · 4 + 3
4 = 1 · 3 + 1
3 = 3 · 1 + 0
ou, como escrevemos desde o ensino fundamental:
3 1 3 \u2190 quocientes
15 4 3 1
3 1 0 \u2190 restos
Assim, mdc(a, b) = 1, que é o ultimo resto não-nulo obtido nas divisões sucessivas.
1.24 Lema. Se b for não-nulo e a = qb + r , então mdc(a, b) = mdc(b, r).
FTC EAD | LICENCIATURA EM MATEMÁTICA26
Prova: Seja d o máximo divisor comum de a e b.
Como r = a\u2212 qb(por hipótese) e d divide tanto a quanto b, concluímos que d | r e, portanto, d | b e d | r .
Por outro lado, se u for um inteiro tal que u | b e u | r , então u | a (pois a = qb + r ). Portanto, como d é
o máximo divisor comum de a e b concluímos que u \u2264 d , ou seja, d satisfaz a definição do máximo divisor
comum de b e r , como queríamos demonstrar.
Agora fica mais fácil entender o algoritmo de Euclides. Sejam a e b inteiros positivos e b \u2264 a. Dividindo a
por b obtemos
a = q1b + r1, com 0 \u2264 r1 < b \u2264 a
e, pelo lema, mdc(a, b) = mdc(b, r1). Se r1 = 0, então mdc(a, b) = mdc(b, 0) = b.
Caso contrário, podemos dividir b por r1, obtendo
b = q2r1 + r2, com 0 \u2264 r2 < r1 < b \u2264 a
e mdc(b, r1) = mdc(r1, r2). Se r2 = 0, então mdc(a, b) = mdc(b, r1) = mdc(r1, 0) = r1.
Se r2 6= 0, e obtendo r3 6= 0, . . . , rn 6= 0, podemos escrever
a = q1b + r1, 0 < r1 < b
b = q2r1 + r2, 0 < r2 < r1
r1 = q3r2 + r3, 0 < r2 < r1
.
.
.
rn\u22122 = qnrn\u22121 + rn, 0 < rn < rn\u22121rn\u22121 = qn+1rn
e então, por aplicação sucessiva do lema,
mdc(a, b) = mdc(b, r1) = mdc(r1, r2) = . . . = mdc(rn\u22121, rn) = mdcmdc(rn, 0) = rn.
Observe que, com certeza, obteremos um resto nulo em algum momento desse processo, já que é decres-
cente a seqüência,
b > r1 > r2 > r3 > . . . > 0
e entre 0 e b só existe um número finito de números naturais. 2
Para formalizar a demonstração do processo descrito anteriormente, usaremos o Princípio da indução.
1.25 Teorema. (Máximo Divisor Comum - Algoritmo de Euclides) Sejam a e b dois números naturais não-nulos,
com a \u2265 b. Dividindo sucessivamente segundo o algoritmo de Euclides, obtemos:
a = q1b + r1, 0 < r1 < b
b = q2r1 + r2, 0 < r2 < r1
r1 = q3r2 + r3, 0 < r3 < r2
.
.
.
rn\u22122 = qnrn\u22121 + rn, 0 < rn < rn\u22121
rn\u22121 = qn+1rn.
Temos, então, que o máximo divisor comum de a e b é rn, o último resto não-nulo obtido nesse algoritmo.
No caso de r1 = 0, então mdc(a, b) = b.
TÓPICOS DE ÁLGEBRA 27
Prova: Sabemos que, se a = q0b, então mdc(a, b) = b. Provaremos o caso geral, fazendo indução sobre
a quantidade de passos do algoritmo de Euclides. Sendo assim, consideremos a seguinte afirmação: se, ao
aplicamos o algoritmo de Euclides a dois números, obtivermos o primeiro resto nulo após n+1 passos, então
mdc(a, b) é igual ao último resto não-nulo obtido neste algoritmo, isto é, o resto rn obtido no passo n.
Observe que o número de passos é contado pelo índice do quociente qj . Dessa forma, no algoritmo
apresentado no enunciado do teorema, foram necessários n+ 1 passos para se obter o primeiro resto nulo; o
resto rn é o máximo divisor comum procurado.
Se n = 1 (isto é, se o primeiro resto nulo ocorrer no segundo passo), o Lema 1.24 garante a veracidade
da afirmação, pois,
mdc(a, b) = mdc(b, r1) = mdc(r1, 0) = r1.
Suponhamos, agora, que a afirmação seja verdadeira toda vez que (n + 1) passos forem necessários
para se obter o primeiro resto nulo. Consideremos agora que o primeiro resto nulo na aplicação do algoritmo
de Euclides aos números a e b ocorra após (n + 2) passos, isto é,
a = q1b + r1, 0 < r1 < b
b = q2r1 + r2, 0 < r2 < r1
r1 = q3r2 + r3, 0 < r3 < r2
.
.
.
rn\u22122 = qnrn\u22121 + rn, 0 < rn < rn\u22121
rn\u22121 = qn+1rn + rn+1, 0 < rn+1 < rn
rn = qn+2rn+1.
Queremos provar que mdc(a, b) = rn+1.
De fato, temos que o algoritmo de Euclides, aplicado aos números b e r1, produziu o primeiro resto
nulo após (n + 1) passos e pela hipótese de indução, mdc(r1, b) = rn+1. Mas, pelo Lema 1.24, temos que
mdc(a, b) = mdc(b, r1), o que completa a prova. 2
Nota 8. Como, pela proposição 1.23, mdc(a, b) = mdc(|a|, |b|), podemos também utilizar o algoritmo
dado para calcular o máximo divisor comum de inteiros negativos.
ER 9. Calcule o mdc(726,\u2212275).
Solução: Como o mdc(726,\u2212275) é igual ao mdc(726, 275), podemos aplicar o algoritmo de Euclides a
mdc(726, 275):
726 = 2 · 275 + 176
275 = 1 · 176 + 99
176 = 1 · 99 + 77
99 = 1 · 77 + 22
77 = 3 · 22 + 11
22 = 2 · 11,
FTC EAD | LICENCIATURA EM MATEMÁTICA28
ou seja,
2 1 1 1 3 2
726 275 176 99 77 22 11
176 99 77 22 11 0
e, portanto, mdc(726,\u2212275) = 11.
Dizemos que um número c é combinação linear nos inteiros dos números a e b, se existem inteiros x , y tais
que c = xa+yb. É interessante notar, então, que o máximo divisor comum de 726 e \u2212275 é combinação desses
números:
11 = 77\u2212 3 · 22
= 77\u2212 3(99\u2212 1 · 77) = 4 · 77\u2212 3 · 99
= 4(176\u2212 1 · 99)\u2212 3 · 99 = 4 · 176\u2212 7 · 99
= 4 · 176\u2212 7(275\u2212 1 · 176) = 11 · 176\u2212 7 · 275
= 11(726\u2212 2 · 275)\u2212 7 · 275 = 11 · 726 + 29(\u2212275).
A próxima proposição mostra que o que foi feito com 726 e \u2212275 pode ser feito com quaisquer inteiros a e
b; para isso, basta percorrer o algoritmo de Euclides no sentido contrário.
1.26 Proposição. Sejam a e b inteiros não simultaneamente nulos. Então existem inteiros x e y tais que
mdc(a, b) = xa + yb.
Prova: No caso de um deles ser nulo, por exemplo b, temos que
mdc(a, b) = mdc(a, 0) = |a| = (±1)a + y0
para qualquer inteiro y e x = ±1, dependendo de a ser positivo ou negativo.
Se ambos são não-nulos basta provar o resultado para inteiros positivos. De fato, se mdc(|a|, |b|) =
x |a|+ y |b| para certos números x e y , então mdc(a, b) = mdc(|a|, |b|) = (±)ax + (±)by .
Sejam, então, a e b dois números inteiros positivos. Se b | a, então mdc(a, b) = b = a · 0 + b · 1. Se
b \u2224 a, então mdc(a, b) pode ser calculado pelo algoritmo de Euclides e a demonstração será feita por indução
no número de passos do algoritmo. Para isso, suponhamos que, ao aplicarmos o algoritmo de Euclides aos
números inteiros positivos a e b, obtenhamos o primeiro resto nulo após (n+1) passos e que, nessa situação,
existam inteiros x e y tal que rn = xa + yb (lembre-se que rn = mdc(a, b)).
A afirmação é verdadeira se dois passos são necessários ( observe que o caso em que apenas um passo
é necessário já foi considerado), pois, se r2 = 0, então,
a = q1b + r1, 0 < r1 < b
b = q2r1,
ou seja,
r1 = a \u2212 q1b = 1a+ (\u2212q1)b.
Suponhamos que a afirmava seja verdadeira toda vez que (n+1) passos forem necessários para se obter
o primeiro resto nulo. Consideraremos inteiros a e b tais que, aplicando-se o algoritmo de Euclides a eles,
TÓPICOS DE ÁLGEBRA 29
obtemos o primeiro resto nulo após (n + 2) passos:
a = q1b + r1, 0 < r1 < b
b = q2r1 + r2, 0 < r2 < r1
r1 = q3r2 + r3, 0 < r3 < r2
.
.
.
rn\u22122 = qnrn\u22121 + rn, 0 < rn < rn\u22121
rn\u22121 = qn+1rn + rn+1, 0 < rn+1 < rn
rn = qn+2rn+1.
Logo, aplicando-se o algoritmo de Euclides a b e r1, obtemos o primeiro resto nulo após (n + 1) passos.
Portanto, pela hipótese de indução, existem inteiros w e x tais que,
rn+1 = mdc(b, r1) = wb + xr1.
Mas, como a = q1b + r1, temos que r1 = a\u2212 q1b; portanto,
rn+1 = wb + x(a \u2212 q1b)x = xa + (w \u2212 q1x)b,
que é o resultado desejado com y = w \u2212 q1x . 2
Nota 9. Percebamos, no entanto, que os inteiros x e y dados pela Proposição 1.26 não são únicos.
Podemos observar, por exemplo, que vale 2 = mdc(6, 4). Mas
1 · 6 + (\u22121)4 = 2 e 3 · 6 + (\u22124)4 = 2.
Em geral, também não vale a recíproca da Proposição 1.26, pois,
2 · 6 + (\u22122)4 = 4 e mdc(6, 4) 6= 4.
Entretanto, se existirem inteiros x e y tais que xa+ yb = 1, então mdc(a, b) = 1 (veja o exercício proposto
1.17). Esse é o único caso em que a recíproca da Proposição 1.26 é verdadeira.
ER 10. Mostre que, se p for primo e p \u2224 a, então