Baixe o app para aproveitar ainda mais
Prévia do material em texto
LICENCIATURA EM MATEMÁTICA DISCIPLINA: Estruturas Algébricas I PROFESSORA: Msc. Ivone Cristina Barros Pedroza MDC E MMC MÁXIMO DIVISOR COMUM Considere “a” e “b” dois números inteiros positivos. Queremos saber se existe um número que divide simultaneamente “a” e “b”, isto é, que seja divisor comum de “a” e “b”. Inicialmente escolhemos um número inteiro positivo qualquer “a” e “b” escreveremos o conjunto de todos os seus divisores (lembrando que existem divisores negativos e positivos). A partir dos conjuntos de todos os divisores de dois números inteiros quaisquer, desejamos discutir se é possível eleger um divisor que seja, comum a estes dois números inteiros de tal forma que ele seja "máximo" e, ainda, como determinar tal elemento. Consideremos os inteiros . Usando a notação D(n) para o conjunto dos divisores de um dado número inteiro n, temos que: Observemos que existem alguns divisores comuns para os inteiros 45 e 36, sendo que o maior deles é o + 9. Também podemos notar que todo divisor vem acompanhado de seu elemento oposto e, claramente, sempre escolheremos um número positivo, já que desejamos eleger o máximo divisor comum entre inteiros. Observe ainda que, no exemplo acima, podemos escolher outro divisor positivo comum aos inteiros 45 e 36, por exemplo, . Neste caso, este outro divisor comum é um divisor de + 9, que é o maior divisor comum determinado. Este fato deve ser considerado ao formalizarmos a definição de máximo divisor comum. Segue, assim, a definição abaixo. Assim podemos generalizar para os números inteiros a seguinte definição: Definição 1: Sejam . Chama-se máximo divisor comum de “a” e “b” o numero inteiro positivo denotado por: que satisfaz as seguintes condições: ; Se existe tal que e consequentemente Definição 2: Sejam . O máximo divisor comum entre a, b e c é o numero inteiro positivo d, denotado por: que satisfaz as seguintes condições: ; Se existe tal que e consequentemente Existência e Unicidade do MDC Teorema 1: Se “a” e “b” são inteiros não conjuntamente nulos, ou seja, , então existe e é único o ; além disso existem inteiros “x”e “y” tais que o , isto é, o é pode ser escrito como uma combinação linear entre “a” e “b” com coeficientes inteiros. Proposição 1: Sejam “a” e “b” números inteiros não simultaneamente nulos. Então: ; É único o ; ; ; Se ; Exemplo 1: Obter o máximo divisor comum dos seguintes números inteiros: Solução: Portanto: Solução: Portanto: INTEIROS PRIMOS ENTRE SI Definição 3: Sejam “a” e “b” dois números inteiros não conjuntamente nulos, ou seja, . Diz-se que “a” e “b” são primos entre si, se e somente se, o . Observamos que, se os inteiros “a” e “b” são primos entre si, os únicos divisores comuns entre eles são -1 e + 1. Exemplo 2: São inteiros primos entre si: 2 e 3, 2 e 5, -9 e 22, -18 e -55, pois temos: Teorema 2: Dois inteiros “a” e “b”, não conjuntamente nulos , são primos entre si, e somente se, existe inteiros “x”e “y” tais que . Teorema 3: Sejam “a” e “b” dois números inteiros, . Então existem inteiros “x” e “y” tais que é o máximo divisor comum entre “a” e “b”. (Identidade de Bézout) Portanto se é tal que Consequência do teorema anterior: Se “a” e “b” são dois inteiros, então o conjunto de todos os múltiplos do é dado por . Corolário 1: Se “a” e “b” são dois inteiros, e , então Exemplo 3: Sabemos que o . Assim Corolário 2: Se e se , então o Corolário 3: Se se e se , então o Corolário 4: Se , então o Corolário 4: Se , então o Teorema 4: Se e se o , então Exemplo 4: Achar o menor inteiro positivo “d” da forma onde “x” e “y” são dois inteiros. Exemplo 5: Calcular o , sendo “n” um número par. O Algoritmo de Euclides para o cálculo do mdc Imagine se estivéssemos interessados em calcular o . Com certeza, não seria muito prático realizar uma discussão análoga. Então Euclides descreveu um método que já conhecemos o “Algoritmo de Euclides”. Antes de enunciá-lo, ilustraremos este algoritmo por meio de exemplo. Exemplo 6: Considere o problema de calcular o . Isolando os restos Isolando os restos Isolando os restosSolução: 21 2 Considerando então o divisor 35 e o resto 21 dessa primeira divisão e efetuamos a divisão Euclidiana de 35 por 21, temos: 14 1 Agora repetimos o processo iniciado, isto é, tomamos 21 na próxima divisão como dividendo e 14 como divisor temos: 7 1 Finalmente, chegamos a divisão exata, temos: 0 2 Tendo chegado a um resto igual a zero, o algoritmo termina. O último resto não-nulo das divisões sucessivas realizadas é o mdc procurado, ou seja, , ou seja, o mdc entre o dividendo e o divisor é igual ao mdc entre o divisor e o resto. A partir destas igualdades obtemos, passo a passo, cada um dos três restos como combinação linear de 91 e 35 Lema de Euclides: Se nas condições do Algoritmo de Euclides, então se e somente se . Então, . Observemos que o lema anterior afirma que se a divisão de “a” por “b” se expressa por , então o mdc entre o dividendo e o divisor é igual ao mdc entre o divisor e o resto. O método que discutiremos para calcular o mdc entre dois inteiros baseia-se em aplicações repetidas desta proposição, sempre considerando divisões entre o divisor e o resto tomados numa divisão imediatamente anterior. Exemplo 7: Utilizemos o processo das divisões sucessivas para calcular: Solução: Para simplificação dos cálculos, podemos iniciar pela divisão entre 954 e 648, pois mdc(954,-648) = mdc(954,648). Temos as seguintes divisões sucessivas: -648 1 306 -612 2 36 -288 8 18 - 36 2 0 COMBINAÇÃO LINEAR ISOLANDO OS RESTOS e assim, mdc(954,-648) = mdc(954, 648) = mdc(648, 306) = mdc(306,36) = mdc(36, 18) = 18 OBS: É freqüente encontrarmos tais divisões representadas em um quadro da seguinte forma: Quocientes 1 2 8 2 954 648 306 36 18 Restos 306 36 18 0 Dispositivo prático para o cálculo do Máximo divisor comum de dois inteiros positivos a e b é denominado Algoritmo de Euclides Exemplo 8: Sejam números inteiros. Demonstre que existem inteiros tais que se, e somente se, Exemplo 9: Sejam números inteiros. Demonstre que existem inteiros tais que então o Exemplo10: Determinar inteiros positivos a e b sabendo que: e e Exemplo11: Sejam números inteiros. Mostre que se , então . Exemplo12: Três rolos de arame farpado têm, respectivamente, 168 m, 264m e 312 m. Deseja-se cortá-los em partes de comprimentos iguais, de maneira que cada parte seja a maior possível. Qual o comprimento e o número de partes? MÍNIMO MÚLTIPLO COMUM Agora escolha um número inteiro qualquer “a” e escreva o conjunto de todos os seus múltiplos (negativos e positivos). A partir dos conjuntos de todos os múltiplos de dois números inteiros, desejamos discutir se é possível eleger um múltiplo que seja comum a estes, de tal forma que ele seja "mínimo". Também queremos discutir um método para determinar tal elemento. Consideremos os inteiros . Usando a notação para o conjunto dos múltiplos de um dado número inteiro n, temos que: Existem múltiplos positivos comuns para os inteiros 45 e 36, sendo que o menor deles é o . A princípio, podemos dizer que o mínimo múltiplo comum entre dois inteiros “a” e “b” pode ser definido como sendo o menor inteiro positivo “m” tal que “a” divide “m” e “b” divide “m”. Definição 4: Sejam “a” e “b” dois números inteiros diferentes de zero (Chama-se mínimo múltiplo comum entre “a” e “b”o número inteiro positivo “m” denotado por: que satisfaz às seguintes condições: ; Se existe tal que OBS: Se , então Definição 5 (MMC de vários inteiros): O conceito de mínimo múltiplo comum, definido para dois inteiros “a” e “b”, estende-se de maneira natural a mais de dois inteiros. No caso de três inteiros “a”, “b” e “c”, diferentes de zero, o é o inteiro positivo “m” que satisfaz as seguintes condições: ; Se Proposição 2: Sejam “a” e “b” números inteiros não simultaneamente nulos. Então: ; ; ; Se ; É único o ; ; Exemplo 13: Calcule o mínimo múltiplo comum nos seguintes casos: Solução: Portanto: Solução: Portanto: Teorema 5: Sejam “a”, “b” e “c” inteiros não todos nulos. Então . Exemplo 14: Encontre o . Solução: Relação entre o MDC e o MMC Salientamos que obter o através dos conjuntos dos múltiplos de “a” e “b” não é algo muito prático. Utilizaremos uma relação entre o para discutir um método de obtenção do . Teorema 6: Para quaisquer inteiros “a” e “b”, com é válida à seguinte relação: Exemplo 15: Vamos determinar o , pois já conhecemos o . Solução: Corolário 5: Para quaisquer números inteiros “a” e “b”, com se e somente se, “a” e “b” são primos entre si, ou seja se Regra prática para obtenção do MDC e MMC de vários inteiros Podemos determinar o e o de dois ou mais números inteiros positivos procedendo do seguinte modo: Fatoramos os números, decompondo-se em fatores primos positivos; Calculamos o multiplicando os fatores comuns aos números, tomando cada fator uma só vez e com o menor expoente que ele apresenta nas decomposições dos números dados; Calculamos o multiplicando os fatores comuns e os não, comuns aos números, tomando cada fator uma só vez e com o maior expoente que ele apresenta nas decomposições dos números dados; Exemplo 16: Dados as seguintes decomposições de inteiros: . Determine: Exemplo 17: Usando o algoritmo de Euclides, achar os inteiros que verifiquem cada uma das seguintes igualdades: Exemplo 18: Calcular:
Compartilhar