Capítulo 8

Prévia do material em texto

��
Capítulo 8:MÁXIMO DIVISOR COMUM E EQUAÇÕES DIOFANTINAS
Rosvita Fuelber Franke�
Introdução
No presente capítulo vamos trabalhar o conceito de divisores e, mais precisamente, definir o máximo divisor comum. Veremos também as importantes propriedades do mdc e como podemos determinar o mdc de dois números inteiros. Iremos também utilizar o mdc para discutir a existência de solução em uma Equação Diofantina Linear. Apresentamos ainda a resolução de alguns problemas envolvendo os conceitos trabalhados. 
Máximo Divisor Comum
 Quando no Ensino Médio, ou até mesmo no Ensino Superior, um aluno é questionado sobre o que é o MMC de dois números, rapidamente obtem-se a resposta que o MMC é “o cálculo que fazemos quando queremos somar ou subtrair frações”. No entanto, quando questionamos um aluno sobre o que é o MDC, raramente temos resposta. Na maioria das vezes o aluno diz não lembrar do que se trata. Pois nesta disciplina nós iremos olhar mais atentamente o máximo divisor comum de dois inteiros e veremos que com o uso desse conceito podemos resolver problemas interesantes e que frequentemente são encontrados nos livros do Ensino Fundamental.
 
Divisores Comuns de dois Inteiros
Chama-se divisor comum de dois inteiros a e b todo inteiro , d≠0 tal que d|a e d|b, ou seja, d pertence simultaneamente ao conjunto dos divisores de a, D(a), e ao conjunto dos divisores de b, D(b).
O conjunto de todos os divisores comuns a dois inteiros a e b indica-se por D(a,b), ou seja, D(a,b)={d(ℤ*| d|a ( d|b}, assim, podemos dizer que o conjunto dos divisores comuns de a e b é:
D(a,b)={d(ℤ*| d|a ( d|b}={d(ℤ*|d(D(a) ( d(D(b)}=D(a)( D(b)
Lembre-se que a intersecção de conjuntos é uma operação comutativa e, isto significa que podemos considerar D(a,b) = D(b,a).
Observe ainda que vimos no capítulo anterior que 1 e 
 são divisores de qualquer inteiro e então podemos dizer que são divisores comuns dois inteiros quaisquer a e b, daí, podemos concluir que o conjunto D(a,b) nunca será vazio. 
Exemplo: observe que 
 e que 
 assim, 
.
Máximo Divisor Comum
Sejam a e b dois inteiros tais que a≠0 ou b≠0. Chama-se máximo divisor comum de a e b, ou simplesmente, o MDC de a e b, o inteiro positivo d (d>0) que satisfaz as seguintes condições:
d|a e d|b;
Se c|a e se c|b, então c≤d.
Pelas condições i e ii, temos que o inteiro d é o maior divisor dentre todos os divisores comuns de a e b, ou o máximo divisor comum de a e b.
Notação: mdc(a,b) = d.
A partir da definição de MDC fazemos algumas observações:
mdc(a,b)=mdc(b,a). Lembre-se que a intersecção do conjunto dos divisores de a com o conjunto dos divisores de b é uma operação comutativa;
O mdc(0,0) não existe, observe que na definição exigimos que a e b não sejam conjuntamente nulos, ou seja, exigimos que a≠0 ou b≠0. Vale ainda acrescentar que todo número inteiro não nulo divide zero e assim, não temos como encontrar o maior inteiro com tal característica.
O mdc(a,1)=1 para qualquer inteiro a, já que 1 é o único divisor positivo de 1. 
Se a≠0, então o mdc(a,0)=|a|. Neste caso, observe que qualquer inteiro não nulo é divisor de 0 mas o maior divisor do inteiro a é o inteiro positivo |a|.
Se a|b, então o mdc(a,b)=|a|.
Existência e Unicidade do MDC
O teorema que enunciamos e provamos a seguir nos garante que se temos dois inteiros que não são conjuntamente nulos (a e b), então sempre existe e é único o máximo divisor comum desses inteiros. Vamos ver também que o mdc(a,b) é o menor inteiro positivo que pode ser escrito na forma ax+by, isto é, que pode ser representado como uma combinação linear de a e de b.
 Teorema: Se a e b são dois inteiros, sendo a≠0 ou b≠0, então existe e é único o mdc(a,b). Além disso, existem inteiros x e y tais que: mdc(a,b) = ax+by, isto é, o mdc(a,b) é uma combinação linear de a e b.
Demonstração: Seja S o conjunto de todos os inteiros positivos da forma au+bv, com u,v 
ℤ isto é:
S={ au+bv | au + bv > 0 e u,v(ℤ }.
Este conjunto S não é vazio, ou seja, S≠Ø, pois se a≠0, então um dos dois inteiros a = a.1+b.0 ou –a=a(-1)+b.0 é positivo e pertence a S. Logo, pelo Princípio da boa ordenação, existe e é único o elemento mínimo d de S, min(S)=d>0. E conforme a definição de S, temos que existem inteiros x e y tais que d = ax+by.
Vamos mostrar agora que d=mdc(a,b). Com efeito, pelo algoritmo da divisão temos que existem q e r tais que a = dq+r com 0≤r<d. Assim temos que r = a – dq = a - (ax+by)q =a(1-xq) - bqy, isto é, o resto r é uma combinação linear de a e b. Como 0≤r<d e d>0 é o elemento mínimo de S, segue-se que r=0 e a=dq, isto é, d|a. Seguindo o mesmo raciocínio conclui-se também que d|b. Logo d é um divisor comum positivo de a e b. Finalmente, se c é um divisor comum positivo de a e de b, c|a e c|b, com c>0 então, c|(ax+by)⇒c|d⇒c≤d, isto é, d é o maior divisor comum positivo de a e b, ou seja: mdc(a,b)=d=ax+by com x,y(ℤ.
Feita a demonstração, cabe observar que d pode ser escrito como combinação linear de a e b, mas esta combinação não é única, pois temos que: mdc(a,b) = d = a (x + bt) + b (y - at) para qualquer que seja o número t inteiro. Observe ainda que se existir algum inteiro c = ax + by, não quer dizer que este inteiro c é o mdc(a,b).
Inteiros Primos Entre Si
Sejam a e b dois inteiros, de modo que, a≠0 ou b≠0. Diz-se que a e b são primos entre si se, e somente se o mdc(a,b)=1.
Observe que os inteiros 2 e 5 são primos entre si pois o mdc(2,5)=1. Assim como também os inteiros 16 e -27 são primos entre si, já que é verdade que o mdc(16,-27)=1.
Veja também que sendo a e b primos entre si, então a e b admitem como únicos divisores comuns o 1 e –1.
Algoritmo de Euclides
Euclides (aproximadamente 360 a.C.) considerado um dos maiores geômetras de todos os tempos escreveu em um dos volumes dos Elementos o conhecido Algoritmo de Euclides ou o algoritmo das divisões sucessivas. Tal algoritmo é usado para determinar o mdc de dois inteiros quaisquer.
Antes de apresentar o Algoritmo de Euclides vamos listar algumas proposições que versam sobre o mdc de dois inteiros. Os teoremas que serão apresentados na sequencia, não serão demonstrados, mas a demonstração de cada um pode ser encontrada na bibliografia citada ao final no capítulo. 
Teorema: Dois inteiros a e b, de modo que, a≠0 e b≠0, são primos entre si se, e somente se existem inteiros x e y tais que, ax+by=1.
Corolário: Se o 
, então o 
.
Teorema (Teorema de Euclides): Se 
e se o 
, então, 
.
Lema: Se 
, então o 
.
Os teoremas aqui listados serão utilizados para demonstrar o Algoritmo de Euclides (ou processo das divisões sucessivas) para encontrar o mdc de dois números inteiros.
Algoritmo de Euclides (processo das divisões sucessivas):
Considerando a e b inteiros tais que a≠0 ou b≠0, pelo algoritmo da divisão existem e são únicos os inteiros 
 e 
 tais que: 
 com 
.
Se 
 então 
, portanto 
. Logo 
. Caso isso não aconteça, ou seja, se 
, aplicaremos o lema anterior, no qual o 
. Daí pelo algoritmo da divisão existe 
e 
 tais que: 
, com 
.
Se 
 então 
 e o 
. Caso isso não aconteça, ou seja, se 
, aplicamos novamente o lema, isto é, existem 
e 
, tais que: 
, com 
.
Se 
 então 
 e o 
. Caso contrário, ou seja, 
, efetuamos novamente o lema.
Assim o processo se repetirá n vezes, até encontrarmos um resto 
, tal que
, isto é, o 
, 
, com 
.
Tendo como base o algoritmo de Euclides apresentado acima, foi deduzido o dispositivo para a determinação do mdc (figura 1) utilizado no 4º ano do Ensino Fundamental.
Para determinar mdc(a,b) fazemos divisões sucessivas até que encontramos 
. Veja: 
Figura 1
Vamos determinar mdc(1348,698) utilizando o algoritmo de Euclides. 
Concluímos então que o mdc(1348,698) = 2.
A determinação do mdc(1348,698) pelo algoritmo de Euclides nos permite também apresentar o mdc como combinação linear de 1348 com 698, basta para isso eliminar os restos nas igualdades, veja:
2 =22–4.5=22–(26–22).5 = 22-26.5+22.5 = 26.(-5)+22.6 = 26.(-5)+(48-26).6 =
= 26.(-5)+48.6-26.6 =26.(-11)+48.6 = (650-48.13)(-11)+48.6 =
= 650(-11)+48.143+48.6 = 650(-11)+48(149) = 650(-11)+(698-650).149 =
= 650(-11)+698.149+650(-149) = 650(-160)+698.149 =
= (1348-698)(-160)+698.149 = 1348(-160)+698.160+698.149 =
= 1348.(-160)+698.(309).
Assim, podemos dizer que 2=1348x+698y é uma combinação linear de 1398 com 698 que resulta no mdc(1348,698). Uma possível solução para x e y é x=-160 e y=309.
Equações Diofantinas Lineares
Uma Equação Diofantina Linear com duas incógnitas x e y é uma equação do tipo:
ax + by = c
onde a, b e c são inteiros dados e ab≠0.
Todo par de inteiros x0, y0 tais que 
 é uma solução inteira ou apenas uma solução da equação 
.
Consideremos, como exemplo, a equação diofantina linear com duas incógnitas 8x + 2y = 22.
Observe que 8.3 + 2.(-1) = 22, e também 8.(-1)+2.15=22, assim como 8.2 + 2.3 = 22. Portanto, os pares 3 e -1, -1 e 15 e também o par 2 e 3 são soluções inteiras da equação diofantina linear 8x + 2 y = 22. 
Existem equações diofantinas lineares com duas incógnitas que não têm solução. Considere por exemplo a equação 6x + 2y = 3. Veja que 6 e 2 são inteiros pares e o produto de um inteiro par com qualquer inteiro sempre irá resultar em um inteiro par, consequentemente não iremos encontrar inteiros x e y tais que o resultado seja 3, já que 3 é um inteiro ímpar!
De modo geral, a equação diofantina linear ax+by=c não tem solução sempre que o mdc(a,b) não dividir c, como veremos no seguinte teorema, que nos dá uma condição para a existência de solução deste tipo de equação. 
Teorema: A equação diofantina linear 
 tem solução se, e somente se, o mdc(a,b) divide c.
O teorema seguinte apresenta uma forma de obter outras soluções para a equação 
 a partir de uma solução já determinada.
Teorema: Se d divide c (d|c), sendo 
, e se o par de inteiros x0, y0 é uma solução particular da equação diofantina 
, então todas as outras soluções desta equação são dadas pelas equações:
 e 
.
Onde t é um inteiro arbitrário.
Como se vê, se d = mdc (a,b) divide c , então a equação diofantina linear ax + by = c admite um número infinito de soluções inteiras, uma para cada valor do inteiro arbitrário t.
Corolário: Se o mdc(a,b)=1 e se e se o par de inteiros x0, y0 é uma solução particular da equação diofantina 
, então todas as outras soluções desta equação são dadas pelas equações:
 e 
.
Onde t é um inteiro arbitrário.
Cabe resaltar que os teoremas aqui citados não serão demonstrados. A demonstração pode ser encontrada nos livros apresentados na bibliografia listada ao final do capítulo. Vamos apenas considerar que cada uma das proposições nos orienta em como podemos resolver equações diofantinas ou problemas que recaem em uma equação diofantina. 
Exemplo: Um circo cobra R$ 6,00 a entrada de crianças e R$ 11,00 a de adultos. Qual é o menor número de pessoas que pode assistir a um espetáculo de maneira que a bilheteria seja R$ 350,00? (Em tempo: a capacidade desse circo é suficiente para esse número de pessoas).
Resolução: Inicialmente, considere que o problema pode ser modelado pela equação diofantina 6x + 11y = 350. Utilizando o algoritmo de Euclides, vamos determinar o mdc(6,11), veja:
Concluímos então que mdc(6,11)=1. É claro que 1 divide 350 e, portanto, a equação possui solução. Na verdade a equação possui infinitas soluções (mas não é qualquer solução que serve para o problema).
Para encontrar uma solução vamos usar o método de eliminar os restos, assim como fizemos para escrever 2=1348.(-160)+698.309, no exemplo anterior. Observe que 1 = 6 - 5.1 = 6 - (11-6).1 = 6 + 6 – 11= 6.2 +11.(-1).
Assim, o par 2 e -1 é uma solução para a equação 6x+11y = 1, para encontrarmos uma solução para a equação pedida (6x+11y=350) basta multiplicar a equação anterior por 350, assim, obtemos o seguinte resultado 6.2.350+11.(-1).350=1.350, ou seja, o par x=700 e y=-350 é uma solução para a equação 6x +11y = 350 dada no problema. Mas observe que esta solução não serve para o problema pois x e y são pessoas! Mas agora, fazendo uso do corolário temos condições de encontrar outras soluções e, soluções possíveis para resolver o problema, basta para tanto considerar as seguintes equações:
x = 700 + 11t e y = -350 – 6t.
Como o problema pede o número de pessoas, x e y devem ser números positivos, para isso devemos escolher um t que satisfaça as desigualdades:
700 + 11t > 0 e -350 – 6t >0.
	Então: 700 + 11t > 0 ⇒ 11t > -700 ⇒ t > -63,63 e, por outro lado devemos ter também -350 – 6t >0 ⇒ -6t > 350 ⇒ t < - 58,33 o que implica que o inteiro t deve pertencer ao intervalo -63,63 < t < -58,33. O que nos leva a testar os valores t = -63, t = -62, t = -61, t = -60, t = -59 e t = -58. Mas como o problema pede o menor número de pessoas, devemos encontrar o menor valor de x e y para satisfazer a equação, o que nos leva a t = -63. Assim, temos:
x = 700 + 11(-63) = 7 crianças e y = -350 – 6(-63) = 28 adultos, total de 35 pessoas. Concluímos então que 35 será o número mínimo de pessoas para que a bilheteria seja R$ 350,00. 
Recapitulando
No capítulo 8 você estudou os conceitos de máximo divisor comum e conheceu as Equações Diofantinas. Embora exista um grande número de propriedades e considerações acerca do assunto mdc, apenas as mais importantes foram aqui relacionadas, pois o objetivo principal do capítulo é usar o máximo divisor comum e suas propriedades para encontrar soluções para as equações diofantinas e resolver alguns problemas interessantes que recaem em nessas equações. Vale considerar que as demonstrações dos teoremas que não foram apresentadas no decorrer do capítulo são bastante interessantes e vale a pena consultar a bibliografia indicada para verificar como são feitas tais demonstrações. 
Dica de Leitura
Para maiores informações sobre o assunto MDC e Equações Diofantinas sugiro a leitura dos seguintes artigos selecionados da Revista do Professor de Matemática:
Uma equação diofantina e suas resoluções, Gilda de La Rocque e João B. Pitombeira – RPM19;
Uma interpretação geométrica do mdc, Zelci C. De Oliveira – RPM29;
Dispositivo prático para expressar o mdc de dois números como combinação linear deles, José P. Q. Carneiro – RPM37.
Referências bibliográficas do capítulo
ALENCAR FILHO, Edgard. Teoria Elementar dos Números. São Paulo: Nobel, 1992.
CHEMALE, Elena Haas; KRUSE, Fábio. Curiosidades Matemáticas. Novo Hamburgo: FEEVALE,1999.
DOMINGUES, Hygino H.; IEZZI, Gelson. Álgebra Moderna: volume único. São Paulo: Atual, 2003.
OLIVEIRA SANTOS, José Plínio de. Introdução à Teoria dos Números. Rio de Janeiro: IMPA, CNPq, 1998.
RIPOLL, Jaime Bruck; RIPOLL, Cydara Cavedon; SILVEIRA, José Francisco Porto da. Números racionais, reais e complexos. Porto alegre: Editora UFRGS,2006.
SCHEINERMAN, Edward R. Matemática Discreta: uma introdução. São Paulo: Pioneira Thompson Learning, 2003.
VÁZQUEZ, Modesto Sierra; ACOSTA, Mario Gonzáles; GARCÍA, Andrés Sánches; ASTUDILLO, Maria Teresa González. Divisibilidad. Madrid: Síntesis, 1989.
VERASTEGUI, T. I. Introducción a la Teoría de Números. Lima: Moshera S.R.L.,1996.
WALTER, Mora F. Introducctión a la Teoría de Números: Ejemplos y algoritmos. Revista digital Matemática, Educación e Internet, 2012. Disponível em<http://www.tec-digital.itcr.ac.cr/revistamatematica/Libros/WMora_TeoriaNumeros/W_Mora_TeoriaNumeros.pdf> Acesso em: 09 de novembro de 2013, 10h20min.
� Mestre em Álgebra pela Universidade Federal do Rio Grande do Sul. Desde 2001 é professora do Curso de Licenciatura em Matemática da ULBRA. Atualmente também atua como professora do curso de Administração EAD da ULBRA e como professora do curso de Matemática da Universidade do Vale do Rio dos Sinos – UNISINOS.
_1114175057.unknown
_1114175203.unknown
_1114175254.unknown
_1124103850/ole-[42,4D, 76, BA, 00, 00, 00, 00]
_1193835262.unknown
_1448124766.unknown
_1448298913.unknown
_1448299620.unknown
_1448299627.unknown
_1448298860.unknown
_1193835884.unknown
_1193835255.unknown
_1114175267.unknown
_1114175279.unknown
_1114175261.unknown
_1114175229.unknown
_1114175242.unknown
_1114175248.unknown
_1114175235.unknown
_1114175216.unknown
_1114175223.unknown
_1114175209.unknown
_1114175154.unknown
_1114175177.unknown
_1114175190.unknown
_1114175196.unknown
_1114175184.unknown
_1114175166.unknown
_1114175171.unknown
_1114175160.unknown
_1114175079.unknown
_1114175092.unknown
_1114175098.unknown
_1114175085.unknown
_1114175067.unknown
_1114175070.unknown
_1114175062.unknown
_1114174828.unknown
_1114175029.unknown
_1114175046.unknown
_1114175052.unknown
_1114175040.unknown
_1114174890.unknown
_1114174894.unknown
_1114174835.unknown
_1114174136.unknown
_1114174682.unknown
_1114174822.unknown
_1114174613.unknown
_1114171284.unknown
_1114171536.unknown
_1114171254.unknown