TEORIA DOS NÚMEROS - MÁXIMO DIVISOR COMUM (3)

MÁXIMO DIVISOR COMUM

6.5 – MÁXIMO DIVISOR COMUM          Consideremos os inteiros 24 e 18. Os conjuntos dos divisores de 24 e 18 são:  D(24) = {1, 2, 3, 4, 6, 8, 12, 24}  e D(18) = {1, 2, 3, 6, 9, 18}.          Selecionando os divisores comuns temos: D(24, 18) = {1, 2, 3, 6}. Como o conjunto dos divisores de um inteiro é finito, o conjunto dos divisores comuns também é finito. Por essa razão, o conjunto dos divisores terá um elemento máximo, que no caso é 6. Esse maior elemento do conjunto dos divisores de dois ou mais números é denominado máximo divisor comum e se escreve, mdc(a, b) para indicar o máximo divisor comum dos inteiros a e b.          Definição:- Sejam os inteiros a e b não conjuntamente todos nulos. Chama-se máximo divisor comum de a e b, que indicamos por mdc(a, b), ao inteiro “d”, tal que:

(1) d | a e d | b  (2) se c | a e se c | b, então c < d.

Pelo definição, em (1), exige-se que d seja um divisor comum de a e b; e, em (2) exige-se que d seja o maior dos divisores comuns de a e b.        A respeito do máximo divisor comum de dois ou mais números podem ser verificadas as seguintes propriedades: P1 – mdc(a, b) = mdc(b, a) P2 – mdc(0, 0) não existe pois todo inteiro é divisor de zero. P3 – mdc(1, a) = 1 P4 – mdc(a, a) = a P5 – Se a < b e d = mdc(a, b) então d < a.        Isto significa que o mdc de dois números é menor ou igual ao menor dos dois números. P6 – mdc[a, (b, c)] = mdc[a, mdc(b, c)] = mdc[mdc(a, b), c] = mdc (a, b, c).       Esta propriedade mostra que para determinar o mdc de três ou mais números pode-se calcular o mdc de dois deles e depois o mdc do mdc desses dois com o terceiro, e assim, sucessivamente. P7 – O mdc(a, b) é igual ao produto dos fatores primos comuns de a e b, com seus menores expoentes.        Esta propriedade fornece um método para calcular o mdc de dois ou mais números pelo processo da fatoração.  Por exemplo: calcular mdc(48, 180). Fatorando os dois números temos:  48 = 24x3  e 180 = 22x32x5. Os fatores comuns dos dois números, com seus menores expoentes são 22x3 = 12. P8 – Se a e b são dois inteiros não conjuntamente nulos, então existe e é único o mdc(a, b).       Esta propriedade é evidente pois:        (1) todo inteiro tem pelo menos dois divisores  - 1 e ele mesmo;       (2) o conjunto dos divisores é finito e, (3) o maior elemento de um conjunto, subconjunto finito dos inteiros, existe e é único. P9 – Quaisquer que sejam os inteiros a e b, não conjuntamente nulos, existem os inteiros x e y tais que mdc(a, b) = ax + by.        Vimos anteriormente que se a | b e a | c, então a | (bx + cy), " x, y Î Z. (P8 – item 5.2).         Como mdc(a, b) | a e mdc(a, b) | b, então mdc(a, b) | ax + by. Portanto, existem os inteiros x e y tais que;mdc(a, b) = ax + by. 6.6 – ALGORÍTMO DE EUCLIDES          Este é um procedimento que permite determinar o mdc de dois números inteiros a partir das divisões sucessivas. Este procedimento tem por base o princípio “ se a = bq + r, então mdc(a, b) = mdc(b, r).        Assim, para achar o mdc de dois números divide-se o maior pelo menor. Este, divide-se pelo resto da divisão obtendo um segundo resto, e assim sucessivamente até encontrar um resto nulo. O último resto não nulo é o mdc dos dois números. Seja então determinar o mdc(480, 130). Temos 480 = 130.3 + 90 (o primeiro resto é 90)  è mdc(480, 130) = mdc(130, 90)         130 =   90.1 + 40 ( o segundo resto é 40) è mdc(130, 90) = mdc(90, 40)            90 =   40.2 + 10 ( o terceiro resto é 10) è mdc(90, 40) = mdc(40, 10)            40 = 10.4 + 0,  como foi obtido o resto 0, temos mdc(40, 10) = 10.                Portanto, mdc(480, 130) = 10.   Para simplificar o processo podemos dispor os números, os quocientes e os restos em um quadro conforme abaixo:

6.7 – EQUAÇÕES DIOFANTINAS          Na propriedade 9, vimos que se mdc(a, b) = d, então existem os inteiros x e y, tais que: ax + by = d. É evidente que se ax + by = d, tem solução, a equação ax + by = k.d, com k inteiro também terá. Se xo, yo é uma solução de ax + by = d, então kxo, kyo será solução de ax + by = k.d Equações desse tipo são chamadas de equações diofantinas.          A solução de uma equação do tipo ax + by = d, é obtida a partir das divisões efetuadas para obtenção do mdc. Vejamos alguns exemplos – 1º Seja resolver a equação 480x + 130y = 10. Nas divisões sucessivas obtemos: 480 = 130.3 + 90 è 90 = 480 – 130.3 (igualdade 3)  130 =   90.1 + 40 è 40 = 130 – 90.1 (igualdade 2)   90 =   40.2 + 10 è 10 = 90 – 40.2 (igualdade 1)   40 = 10.4 + 0.  A partir da divisão em que o resto é igual ao mdc, fazemos: (1) 10 = 90 – 40.2.  (igualdade 1) (2) Substituindo o valor de 40, da igualdade 2 na expressão (1), resulta: 10 = 90 – (130 – 90.1)2.  (3) Reunindo os coeficientes de 90 e 50, teremos 10 = 90.3 – 130.2  (4) Substituindo o valor de 90, da igualdade 3, na expressão obtida em (3), resulta: 10 = (480 – 130.3).3 – 130.2.  (5) Reunindo os coeficientes de 480 e 130, resulta, finalmente   10 = 480.3 – 130.11.  (6) Comparando com a equação dada, obtemos  x = 3 e y = -11. 2º exemplo: Resolver a equação   170x + 27y = 5. Divisões sucessivas: 170 = 27.6 + 8 è 8 = 170 – 27.6   27 =  8.3 + 3 è 3 =   27 -    8.3     8 =  3.2 + 2 è 2 =     8  -   3.2       3 =  2.1 + 1 è 1 =     3  -   2.1     2 =  2.1 + 0 è mdc(170, 27) = 1         Resolvendo a equação para 170x + 27y = 1, temos: 1 = 3 – 2.1 = 3 – (8 – 3.2).1 = 3.3 – 8 = (27 – 8.3).3 – 8 = 27.3 – 8.10 = 27.3 – (170 – 27.6).10 è 1 = 27.63 – 170.10.         Assim, as soluções de 170x + 27y = 1 são  x = -10 e y = 63.         Em conseqüência, temos para 170x + 27y = 5, as soluções x = 5.(-10) = - 50 e y = 5.(63) = 315. EXERCÍCIOS 1 – Calcule o mdc dos seguintes pares de números:  a)   306 e 657               b)   272 e 1479              c)   7469 e 2387            d) –816 e 7209  e)   –5376 e –3402.       f) 14 e -21 2 – Calcule o mdc dos seguintes números:  a)     624, 504 e 90                    b)     285, 675 e 405                 c) 69, 598 e 253 3 – Resolva as equações: a)     mdc(56, 72) = 56x + 72y              b) mdc(24, 138) = 24x + 138y  c) mdc(1769, 2378) = 1769x + 2378y  d) 78x + 32y = 2  e) 104x + 91y = 13 e)     288x + 51y = 3                           g) 17x + 5y = -2. 4 – Se mdc(a, 0) = 13, ache os possíveis valores de a. 5 – Sabe-se que a e b são primos entre si. Calcule mdc(a + b, a – b). 6 – Se a e b são dois números primos não pares, determine mdc(a + b, a – b). 7 – Ache os elementos de {1, 2, 3, 4, 5} que são primos com 8. 8 – Enumerar os elementos  x de {1, 2, 3, 4, 5, 6} tais que mdc(x, 6) = 1. 9 – Deseja-se cercar um terreno retangular de dimensões 940 m por 740 m com arame farpado. Para isso o dono deverá colocar moirões em todos os lados de modo que a distância entre dois moirões consecutivos seja sempre a mesma. Qual é o número mínimo de moirões usados e qual é a distância entre dois moirões consecutivos? 10 – Sabe-se que a e b são dois números primos entre si. Calcule mdc(a + b, a – b). 11 – Se mdc(a, 0) = 23, achar os valores de a. 12 – Se n é um inteiro qualquer, calcule mdc(n, n + 1). 13 – Calcule os inteiros positivos a e b se a)     a + b = 63 e mdc(a, b) = 9  b)     ab = 756 e mdc(a, b) = 6. 14 – Achar o maior inteiro positivo pelo qual se deve dividir 160, 198 e 370 para que os restos da divisão sejam respectivamente 7, 11 e 13. 15 – O mdc de dois números inteiros positivos é 10 e o maior deles é 120. Determine os possíveis valores do outro número. 16 – Calcule a e b se a2 – b2 = 7344 e mdc(a, b) = 12. 17 – Dividindo-se dois inteiros pelo mdc destes dois, a soma dos quocientes é 8. Determinar os dois inteiros, se sua soma é igual a 384.