MÁXIMO DIVISOR COMUM (MDC) - VÍDEO

Aula de Máximo Divisor Comum (MDC).

Boa revisão pessoal!

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.

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

MÁXIMO DIVISOR COMUM

6.4 – FORMULAS QUE DÃO PRIMOS                  Um dos problemas até o momento insolúveis é a determinação de uma fórmula que forneça todos os números primos. Muitas expressões foram apresentadas, porém nenhuma delas permaneceu como verdadeira. Vejamos algumas: 1. Fórmula de Euler:     pn = n2 + n + 41.   Não é primo para n = 41, pois 412 + 41 + 41 = (41 + 1 + 1)x41 = 43 x 41. 2. pn = 2n2 + 29 (não é primo para n > 28) 3. pn = n2 + n + 17  (não é primo para n > 16) 4. pn = 3n2 + 3n + 23 (não é primo para n > 21)         O uso de fatoriais é útil para determinação de seqüências de números compostos.        Tomando por exemplo  (n + 1)! + 2, (n + 1)! + 3, (n + 1)! + 4,  (n + 1)! + (n + 1) são todos compostos pois para cada (n + 1)! + i  ( para 2 <  j  < n + 1) é divisível por j pois j é um fator de (n + 1)!. Assim, se quisermos  6 inteiros consecutivos compostos basta fazer 7! + 2, 7! + 3 , 7! + 4, 7! + 5, 7! + 6 e 7! + 7. Teremos neste caso os inteiros 5040 + 2, 5040 + 3, 5040 + 4, 5040 + 5, 5040 + 6, 5040 + 7 ou 5042, 5043, 5044, 5045, 5046 e 5047. EXERCÍCIOS 1 - Escreva uma seqüência de 4 números inteiros positivos compostos. 2 - Escreva uma seqüência de 10 números inteiros positivos compostos.

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

MÁXIMO DIVISOR COMUM

6.1 – NÚMEROS PRIMOS E COMPOSTOS          Consideremos os números  positivos 12 e 19. Ao determinarmos os divisores positivos de 12 e de 19 teremos os seguintes conjuntos: D(12) = {1, 2, 3, 4, 6, 12} e D(19) = {1, 19}. Conforme pode ser visto, o inteiro positivo 12 tem, além dos divisores triviais 1 e 12 outros divisores. Entretanto, os divisores de 19 são apenas os triviais 1 e 19. Números como o 12 são chamados de números compostos e números como o 19 são chamados de números primos. Podemos assim, definir:          Um número inteiro positivo é denominado número primo, se e somente se, seus únicos divisores positivos forem 1 e ele mesmo. Um número não primo é chamado de número composto. 6.2 – DETERMINAÇÃO DE NÚMEROS PRIMOS – CRIVO DE ERATÓSTENES          Um procedimento útil para determinar os números primos até o inteiro positivo consiste em construir uma tabela onde são indicados todos os inteiros de 2 até n. A seguir, cortam-se todos os múltiplos dos números primos p, tais p<   n , isto é cortam os inteiros p, 2p, 3p ....          Tomando por exemplo os inteiros de 2 até 200, teremos: 14  <       < 15   como o primo mais próximo de   200 é 13, basta que se eliminem os múltiplos dos primos de 2 até 13.

Eliminados todos os múltiplos de 2 - 3 - 5 - 7 - 9 e 13, com exceção destes,sobram os números 2 - 3 - 5 - 7 - 13 - 17 -  19 - 23 - 29 -  31 -  37 - 43 - 47 - 53 - 59 -  61 - 67 - 83 - 89 - 97 - 101 - 103 - 107 - 109 - 113 - 121 - 127 - 131 - 139 - 149 - 151 - 157 - 163 - 167 - 171 - 173 - 179 - 181 - 187 - 193 - 197 e 199, que são os números primos menores que 200.         Para determinar se um número n é ou não primo, basta então dividir tal número pelos primos a partir de 2. Quando o quociente tornar-se menor que o divisor e nenhuma divisão der resto zero, o número é primo. Exemplo: verificar de 631 é ou não primo.         Dividindo 631 por 2, 3, 5, 7, 11, 13, 17, 19, 21, 23 e 29 todos os restos são diferentes de zero (as divisões não são exatas). Nas divisões por 2, 3, 5, ... 23, o quociente é maior que o divisor (maior que 2, 3, 5, ...23, respectivamente). Entretanto, na divisão por 29 o quociente é 21 (menor que 29). Assim, 631 é um número primo.         Já o número 437 é um composto pois ao dividi-lo por 19, o quociente é 23 e o resto é zero.         A tabela acima pode ser usada para verificar se um número até 2002 = 40000 é ou não primo. EXERCÍCIOS: 1 – Verifique se os números 169, 197, 239, 473, 917, 1013 são ou não primos. 6.3 – DECOMPOSIÇÃO EM FATORES PRIMOS          Todo número composto pode ser decomposto em 2 ou mais fatores. Tomando por exemplo o número 72, teremos  72 = 4 x 18  ou 72 = 3 x 4 x 6. Se continuarmos decompondo encontraremos  72 = 2 x 2 x 2 x 3 x 3 = 23 x 32. Como os fatores 2 e 3 são primos não há forma de continuar a decomposição. A decomposição de 72 na forma 2 x 2 x 2 x 3 x 3 é chamada de decomposição em fatores primos ou decomposição canônica.          Com relação à decomposição temos: - A decomposição canônica em fatores primos é única. - Todo número composto pode ser decomposto em fatores primos. - Se a forma da decomposição de um inteiro positivo N é p1a1.p2a2.p3a3...pnan, então o número de divisores inteiros de N é d(N) = (a1 + 1)(a2 + 1)(a3 + 1)...(an + 1) Exemplo: A decomposição canônica de 600 é   600 = 23 x 3 x 52. Isto implica que 600 tem (3 + 1)(1 + 1)(2 + 1) = 4 x 2 x 3 = 24 divisores ou d(600) = 24. EXERCÍCIOS 1 – Achar todos os primos da forma n2 – n. 2 – Achar três primos ímpares cuja soma seja (a) 81      (b) 125 3 – Achar todos os pares de primos p e q tais que p – q = 3. 4 – Achar todos os primos que são iguais a um quadrado perfeito menos 1. 5 – Ache a decomposição canônica de 5400. 6 – Quantos divisores positivos tem o número 5400?   7 – Na decomposição de um número positivo com 30 divisores positivos, a decomposição canônica fornece 25.3a. Determine o valor de a e o número.