Matematica pura

Prévia do material em texto

MA14 - Aritme´tica
Unidade 5 - Parte 2
Algoritmo de Euclides
(Propriedades do mdc)
Abramo Hefez
PROFMAT - SBM
Aviso
Este material e´ apenas um resumo de parte do conteu´do da
disciplina e o seu estudo na˜o garante o dom´ınio do assunto.
O material completo a ser estudado encontra-se no
Cap´ıtulo 5 - Sec¸a˜o 5.2,
do livro texto da disciplina:
Aritme´tica, A. Hefez, Colec¸a˜o PROFMAT.
Colaborou na elaborac¸a˜o desses resumos Maria Lu´cia T. Villela.
PROFMAT - SBM Aritme´tica - Unidade 5 - Parte 2 - Propriedades do mdc slide 2/9
Sejam a, b ∈ Z. O conjunto a seguir desempenhara´ papel
importante
I (a, b) = {xa + yb; x , y ∈ Z}.
Note que se a e b na˜o sa˜o simultaneamente nulos, enta˜o
I (a, b) ∩ N 6= ∅.
De fato, temos que a2 + b2 = a · a + b · b ∈ I (a, b) ∩ N.
A importaˆncia do conjunto I (a, b) pode ser medida pelo resultado
a seguir.
PROFMAT - SBM Aritme´tica - Unidade 5 - Parte 2 - Propriedades do mdc slide 3/9
Teorema
Sejam a, b ∈ Z na˜o ambos nulos. Se d = min I (a, b) ∩ N, enta˜o
i) d e´ o mdc de a e b; e
ii) I (a, b) = dZ (= {xd ; x ∈ Z}).
Esse teorema nos da´ uma outra demonstrac¸a˜o da existeˆncia do
mdc de dois nu´meros.
Note que essa demonstrac¸a˜o, ao contra´rio da prova de Euclides,
na˜o e´ construtiva, no sentido de que na˜o nos fornece um meio
pra´tico para achar o mdc dos dois nu´meros.
O teorema admite va´rios corola´rios.
PROFMAT - SBM Aritme´tica - Unidade 5 - Parte 2 - Propriedades do mdc slide 4/9
Corola´rios
1. Quaisquer que sejam a, b ∈ Z, na˜o ambos nulos, e n ∈ N,
(na, nb) = n(a, b).
2. Dados a, b ∈ Z, na˜o ambos nulos, tem-se que(
a
(a, b)
,
b
(a, b)
)
= 1.
Dois nu´meros inteiros a e b sera˜o ditos primos entre si, ou
coprimos, se (a, b) = 1; ou seja, se o u´nico divisor comum positivo
de ambos e´ 1.
3. Dois nu´meros inteiros a e b sa˜o primos entre si se, e somente
se, existem nu´meros inteiros m e n tais que ma + nb = 1.
PROFMAT - SBM Aritme´tica - Unidade 5 - Parte 2 - Propriedades do mdc slide 5/9
Um Teorema Fundamental
A propriedade acima estabelece uma relac¸a˜o crucial entre as
estruturas aditiva e multiplicativa dos nu´meros naturais, o que
permite provar o importante resultado a seguir.
Teorema
Sejam a, b e c nu´meros inteiros.
a | b · c e (a, b) = 1 =⇒ a|c .
Corola´rio
Dados a, b, c ∈ Z, com b e c na˜o ambos nulos, temos que
b|a e c |a ⇐⇒ bc
(b, c)
| a.
PROFMAT - SBM Aritme´tica - Unidade 5 - Parte 2 - Propriedades do mdc slide 6/9
Generalizac¸a˜o do conceito de mdc
Um nu´mero natural d sera´ dito mdc de dados nu´meros inteiros
a1, . . . , an, na˜o todos nulos, se possuir as seguintes propriedades:
i) d e´ um divisor comum de a1, . . . , an.
ii) Se c e´ um divisor comum de a1, . . . , an, enta˜o c|d .
O mdc, quando existe, e´ certamente u´nico e sera´ representado por
(a1, . . . , an).
Dados nu´meros inteiros a1, . . . , an, na˜o todos nulos, existe o seu
mdc e pode ser calculado recursivamente atrave´s da fo´rmula:
(a1, . . . , an) = (a1, . . . , (an−1, an)).
PROFMAT - SBM Aritme´tica - Unidade 5 - Parte 2 - Propriedades do mdc slide 7/9
Exemplos
(72, 138, 252) = (72, (138, 252)) = (72, 6) = 6.
1 1 4 1 3
252 138 114 24 18 6
114 24 18 6
(15, 72, 180) = (15, (72, 180)) = (15, 36) = 3.
2 2
180 72 36
36
e
2 2 2
36 15 6 3
6 3
PROFMAT - SBM Aritme´tica - Unidade 5 - Parte 2 - Propriedades do mdc slide 8/9
Os inteiros a1, . . . , an sera˜o ditos primos entre si, ou coprimos,
quando (a1, . . . , an) = 1.
Exemplo
(5, 12, 18) = (5, (12, 18)) = (5, 6) = 1.
(143, 175, 245) = (143, (175, 245)) = (143, 35) = 1.
1 2 2
245 175 70 35
70 35
e
4 11 1 2
143 35 3 2 1
3 2 1
PROFMAT - SBM Aritme´tica - Unidade 5 - Parte 2 - Propriedades do mdc slide 9/9