Buscar

Apostila de MDC e MMC

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 11 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 11 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 11 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

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:

Outros materiais