MA14 - Unidade 8 Equaes Diofantinas Lineares Semana de 29/08 a 04/09

A resoluo de vrios problemas de aritmtica recai na resoluo, em nmeros naturais, de equaes do tipo aX bY = c, ou, ainda, do tipo aX + bY = c, com a, b, c N. Tais equaes so chamadas equaes diofantinas lineares em homenagem a Diofanto de Alexandria (aprox. 300 DC). Nem sempre estas equaes possuem soluo. Por exemplo, as equaes 4X 6Y = 3 e 4X + 6Y = 2 no possuem nenhuma soluo em nmeros naturais x0 , y0 pois, caso contrrio, para a primeira equao, teramos 4x0 6y0 par e, portanto, nunca igual a 3; e, para a segunda equao, teramos 4x0 + 6y0 > 2.

2 MA 14 Unidade 8 , ento, natural perguntar-se em que condies tais equaes possuem solues e, caso tenham, como determin-las? A resposta para as equaes do tipo aX bY = c relativamente fcil e ser dada nas duas proposies a seguir. Proposio 1. Sejam a, b N e c N. A equao aX bY = c admite soluo em nmeros naturais se, e somente se, (a, b)|c. Demonstrao Pelo Teorema 1, Unidade 6, temos que J (a, b) = {na mb N; n, m N} = (a, b)N. claro que a equao aX bY = c possui soluo se, e somente se, c J (a, b), o que equivalente a c (a, b)N, que, por sua vez, equivalente a (a, b)|c. 2 Se a equao aX bY = c tem soluo, ento ela equivalente equao a1 X b 1 Y = c 1 , onde a1 = a b c , b1 = , c1 = . (a, b) (a, b) (a, b)

Note que (a1 , b1 ) = 1 e, portanto, podemos nos retringir s equaes do tipo aX bY = c, que sempre tm solues. Uma soluo minimal de aX bY = c uma soluo x0 , y0 da equao, tal que, se x1 , y1 uma soluo qualquer da equao, ento x0 x1 . Mostraremos a seguir como as solues da equao diofantina aX bY = c, com (a, b) = 1, podem ser determinadas a partir da soluo minimal x0 , y0 . com (a, b) = 1,

Equaes Diofantinas Lineares

Proposio 2. Seja x0 , y0 a soluo minimal da equao aX bY = c, onde (a, b) = 1. Ento, as solues x, y em N da equao so x = x0 + tb, y = y0 + ta, t N.

Demonstrao Seja x, y uma soluo de aX bY = c, logo, ax0 by0 = ax by = c. Conseqentemente, a(x x0 ) = b(y y0 ). Como (a, b) = 1, segue-se que b|(x x0 ). Logo, x x0 = tb, t N. Substituindo a expresso de x x0 acima em (1), segue-se que y y0 = ta, o que prova que as solues so do tipo exibido. Por outro lado, x, y , como no enunciado, soluo, pois ax by = a(x0 + tb) b(y0 + ta) = ax0 by0 = c. 2 Note que a equao aX bY = c, com (a, b) = 1, admite innitas solues. A seguir, descreveremos um mtodo para encontrar a soluo minimal de uma equao do tipo aX bY = c, quando (a, b) = 1. Se a, b e c so nmeros pequenos, a soluo pode ser encontrada por inspeo. Em geral, o mtodo descrito abaixo sempre permitir achar a soluo minimal. (1)

4 MA 14 Unidade 8 Usando o algoritmo euclidiano, possvel escrever na mb = (a, b) = 1 ou m b n a = (a, b) = 1. No caso em que 1 = m b n a, escolha N tal que b > n e a > m , logo, 1 = (b n )a (a m )b. Portanto, pode-se sempre escrever 1 = na mb, para alguns n, m N. Multiplicando ambos os membros da igualdade acima por c, obtemos c = cna cmb. Logo, x1 = cn e y1 = cm uma soluo particular da equao. Pela Proposio 2, temos que a soluo minimal x0 = x1 tb e y0 = y1 ta para o maior valor de t, de modo que ainda se tenha cn tb = x1 tb 0 e cm ta = y1 ta 0. Exemplo 1. Resolvamos a equao 24X 14Y = 18. A equao tem soluo, pois (24, 14)|18; e equivalente a 12X 7Y = 9. Vamos, em seguida, achar a soluo minimal x0 , y0 desta ltima equao. Pelo algoritmo euclidiano, temos 12 = 7 1 + 5 7=51+2 5=22+1 Substituindo as equaes acima umas nas outras, obtemos 1 = 12 3 7 5, e, portanto, 9 = 12 27 7 45. Logo, x1 = 27 e y1 = 45 soluo particular da equao. A partir desta soluo, vamos, com o auxlio do mtodo acima exposto, determinar a soluo minimal. Ponhamos x = 27 t7, y = 45 t12,

Equaes Diofantinas Lineares

e determinemos o maior valor de t N, de modo que x, y N. Isto ocorre quando t = 3, dando a soluo minimal x0 = 6 e y0 = 9. As solues da equao so, portanto, x = 6 + t7, y = 9 + t12.

Exemplo 2. Resolvamos a equao 14X 24Y = 18. A equao tem soluo, pois (14, 24)|18, e equivalente a 7X 12Y = 9. Vamos, em seguida, achar a soluo minimal x0 , y0 desta ltima equao. Pelos clculos feitos no Exemplo 1, temos que 9 = 12 27 7 45 = 7(4 12 45) 12(4 7 27) = 7 3 12 1, o que nos d a soluo minimal x0 = 3 e y0 = 1. Portanto, as solues da equao so dadas por x = 3 + t12, y = 1 + t7.

Para responder s mesmas perguntas formuladas acima para as equaes do tipo aX + bY = c, vamos precisar do resultado a seguir. Proposio 3. Sejam a, b N , com (a, b) = 1. Todo nmero natural c pode ser escrito (de modo nico) de uma e, somente uma, das seguintes formas: c = na + mb, ou c = na mb, com n < b.

Demonstrao Existncia: Sabemos que existem u, v N tais que ua vb = (a, b) = 1. Multiplicando ambos os lados desta ltima igualdade por c, temos que auc bvc = c. Pela diviso euclidiana, temos que existem q, n N com n < b tais que uc = qb + n. Substituindo esse valor de uc na igualdade acima, obtemos c = na + qab vcb. Se qa vc, pondo m = qa vc, temos que c = na + mb.

6 MA 14 Unidade 8 Se vc qa, pondo m = vc qa, temos que c = na mb. Unicidade: Suponhamos que na mb = n a m b, com n, n < b.

Temos trs possibilidades para analisar: na + mb = n a m b, na + mb = n a + m b, na mb = n a m b.

Inicialmente, mostraremos que a primeira possibilidade s ocorre quando n = n e m = m = 0. Para isto, basta mostrar que n = n , pois teramos 0 = na + mb (n a m b) = mb + m b = b(m + m ), o que implicaria que m + m = 0 e, portanto, que m = m = 0. Para mostrar que n = n , suponhamos, por absurdo, que n = n. Logo, necessariamente, n > n. Portanto, (n n)a = (m + m )b. Como (a, b) = 1, temos que a|(m + m ) e, portanto, m + m = ra. Logo, (n n)a = (m + m )b = rab. Da segue que (n n) = rb, o que absurdo, pois n n < b e rb b. Portanto, n = n , seguindo assim a unicidade. As outras duas possibilidades podem ser tratadas de modo semelhante e so deixadas como exerccio para o leitor. 2 Sejam a, b N . Denimos o conjunto S (a, b) = {xa + yb; x, y N}. claro que aX + bY = c, com (a, b) = 1, tem soluo se, e somente se, c S (a, b). Portanto, de fundamental importncia caracterizar os elementos do conjunto S (a, b).

Equaes Diofantinas Lineares

Proposio 4. c S (a, b) se, e somente se, existem n, m N, com n < b (univocamente determinados) tais que c = na + mb Demonstrao claro que, se c = na + mb, ento c S (a, b). Por outro lado, se c S (a, b), ento c = xa + yb com x, y N. Pela diviso euclidiana, x = bq + n, com n < b; logo, substituindo o valor de x desta ltima igualdade na igualdade acima, obtemos que c = na + mb, onde n < b, e m = aq + y . 2 Denamos o conjunto de lacunas de S (a, b) como sendo o conjunto L(a, b) = N \ S (a, b). Corolrio. Temos que L(a, b) = {na mb N; n < b, m N}. Demonstrao Isto decorre imediatamente das Proposies 3 e 4. 2 Teorema 1. A equao aX + bY = c, onde (a, b) = 1, tem soluo em nmeros naturais se, e somente se, c L(a, b) = {na mb N; n < b, m N}. Demonstrao Como a equao aX + bY = c tem soluo se, e somente se, c S (a, b), o resultado segue-se do Corolrio. 2 Note que o conjunto L(a, b) nito e o seu maior elemento max L(a, b) = (b 1)a b. Portanto, se c (b 1)a b + 1 = (b 1)(a 1),

8 MA 14 Unidade 8 a equao aX + bY = c admite soluo; se c = (b 1)(a 1) 1, ela no admite soluo. Na prtica, no difcil decidir se a equao aX + bY = c admite soluo. Se (a, b) |c, a equao no tem soluo. Se (a, b)|c, a equao equivalente a uma outra com (a, b) = 1. Com o algoritmo euclidiano, escreva 1 = (a, b) = n a m b. Logo, c = cn a cm b. Agora, com a diviso euclidiana, escreva cn = qb + n com n < b, logo, c= na + (qa cm )b S (a, b), na (cm qa)b L(a, b), se qa cm se cm > qa

A equao tem soluo no primeiro caso, mas, no no segundo. A soluo n, m da equao aX + bY = c, com n < b, uma soluo minimal, no sentido de que se x, y uma soluo, ento x n. Proposio 5. Suponha que a equao aX + bY = c, com (a, b) = 1, tenha soluo e seja x0 = n, y0 = m a soluo minimal. As solues x, y da equao so dadas pelas frmulas x = n + tb, e y = m ta.

Demonstrao Temos que an + bm = ax + by = c. Logo, a(x n) = b(m y ), que, de modo totalmente anlogo ao que foi feito na demonstrao da Proposio 2, implica no resultado. 2

Equaes Diofantinas Lineares

Note que este tipo de equao tem, no mximo, um nmero nito de solues, correspondentes aos seguintes valores de t: 0, 1, . . . , onde m , a

m representa o quociente da diviso euclidiana de m por a. a Exemplo 3. Vamos determinar para quais valores de c N a equao 11X + 7Y = c tem solues em N. O conjunto de lacunas de S (11, 7) o conjunto L(11, 7) = {n11 m7 N, n, m N, n < 7} = {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15, 16, 17, 19, 20, 23, 24, 26, 27, 30, 31, 34, 37, 38, 41, 45, 48, 52, 59}. Portanto, a equao 11X + 7Y = c admite soluo se, e somente se, c L(11, 7). Exemplo 4. Resolvamos a equao 11X + 7Y = 58. Como, de acordo com o Exemplo 3, 58 L(11, 7), a equao possui solues. Para determin-las, considere o algoritmo euclidiano, 11 = 7 1 + 4 7=41+3 4=31+1 Logo, 1 = 4 3 = 4 (7 4) = 2 4 7 = 2(11 7) 7 = 2 11 3 7. Portanto, 58 = (58 2)11 (58 3)7 = (4 + 16 4)11 174 7 = 4 11 + 2 7. Segue da que x0 = 4 e y0 = 2 a soluo minimal da equao. Logo, as solues so x = 4 + t7, y = 2 t11,

10 MA 14 Unidade 8 que s tm sentido para t = 0, e, portanto, a equao s possui a soluo x0 = 4, y0 = 2. Para resolver equaes como as acima, no necessrio usar toda a tcnica que desenvolvemos, pois os nmeros envolvidos so sucientemente pequenos para que seja vivel achar as solues por inspeo. No exemplo acima, basta testar os valores x = 1, 2, 3, 4 e 5 para vericar que apenas x = 4 possvel.

Problemas 1. Resolva as equaes: a) 90X 28Y = 22 b) 50X 56Y = 74 c) 40X 65Y = 135 d) 8X 13Y = 23 2. Para quais valores de c a equao 90X + 28Y = c no possui solues? 3. Resolva as equaes: a) 16X + 7Y = 601 b) 30X + 17Y = 201 c) 47X + 29Y = 1288 d) 8X + 13Y = 23 4. Dispondo de 100 reais, quais so as quantias que se podem gastar comprando selos de 5 reais e de 7 reais? 5. Determine todos os mltiplos de 11 e de 9 cuja soma igual a a)79 b) 80 c) 270

6. Determine o menor inteiro positivo que tem restos 11 e 35 quando dividido, respectivamente, por 37 e 48. 7. Numa criao de coelhos e galinhas, contaram-se 400 ps. Quantas so as galinhas e quantos so os coelhos, sabendo que a diferena entre esses dois nmeros a menor possvel? 8. Subindo uma escada de dois em dois degraus, sobra um degrau. Subindo a mesma escada de trs em trs degraus, sobram dois degraus. Determine

Equaes Diofantinas Lineares

11

quantos degraus possui a escada, sabendo que o seu nmero mltiplo de 7 e est compreendido entre 40 e 100. 9.(ENC 2002) Em certo pas, as cdulas so de $4 e $7. Com elas, possvel pagar, sem troco, qualquer quantia inteira a) a partir de $11, inclusive. b) a partir de $18, inclusive. c) mpar, a partir de $7, inclusive. d) que seja $1 maior do que um mltiplo de $3. e) que seja $1 menor do que um mltiplo de $5. 10. De quantas maneiras pode-se comprar selos de 3 reais e de 5 reais de modo que se gaste 50 reais?