MA14 - Unidade 8

Equaes Diofantinas Lineares

Semana de 29/08 a 04/09

A resoluo de vrios problemas de aritmtica recai na resoluo, em nmerosnaturais, de equaes do tipo

aX bY = c,

ou, ainda, do tipoaX + 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 contr-rio, para a primeira equao, teramos 4x0 6y0 par e, portanto, nunca iguala 3; e, para a segunda equao, teramos 4x0 + 6y0 > 2.

2 MA 14 Unidade 8

, ento, natural perguntar-se em que condies tais equaes possuemsolues e, caso tenham, como determin-las?

A resposta para as equaes do tipo aX bY = c relativamente fcile ser dada nas duas proposies a seguir.

Proposio 1. Sejam a, b N e c N. A equao aX bY = c admitesoluo em nmeros naturais se, e somente se, (a, b)|c.

Demonstrao Pelo Teorema 1, Unidade 6, temos que

J(a, b) = {namb 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, equivalentea (a, b)|c.

2

Se a equao aX bY = c tem soluo, ento ela equivalente equao

a1X b1Y = c1,

ondea1 =

a

(a, b), b1 =

b

(a, b), c1 =

c

(a, b).

Note que (a1, b1) = 1 e, portanto, podemos nos retringir s equaes dotipo

aX bY = c, com (a, b) = 1,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.

Equaes Diofantinas Lineares 3

Proposio 2. Seja x0, y0 a soluo minimal da equao aXbY = 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). (1)

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 infinitassolues.

A seguir, descreveremos um mtodo para encontrar a soluo minimal deuma equao do tipo aX bY = c, quando (a, b) = 1.

Se a, b e c so nmeros pequenos, a soluo pode ser encontrada porinspeo. Em geral, o mtodo descrito abaixo sempre permitir achar asoluo minimal.

4 MA 14 Unidade 8

Usando o algoritmo euclidiano, possvel escrever

namb = (a, b) = 1 ou mb na = (a, b) = 1.No caso em que 1 = mb na, escolha N tal que b > n e a > m,

logo,1 = (b n)a (am)b.

Portanto, pode-se sempre escrever 1 = namb, 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 parao 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 + 57 = 5 1 + 25 = 2 2 + 1Substituindo 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 soluominimal. Ponhamos

x = 27 t7, y = 45 t12,

Equaes Diofantinas Lineares 5

e determinemos o maior valor de t N, de modo que x, y N. Isto ocorrequando 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 equaesdo tipo aX + bY = c, vamos precisar do resultado a seguir.

Proposio 3. Sejam a, b N, com (a, b) = 1. Todo nmero natural c podeser escrito (de modo nico) de uma e, somente uma, das seguintes formas:

c = na+mb, ou c = namb, com n < b.

Demonstrao Existncia: Sabemos que existem u, v N tais que uavb = (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 = namb.Unicidade: Suponhamos que

namb = namb, com n, n < b.

Temos trs possibilidades para analisar:

na+mb = namb, na+mb = na+mb, namb = namb.

Inicialmente, mostraremos que a primeira possibilidade s ocorre quandon = n e m = m = 0. Para isto, basta mostrar que n = n, pois teramos

0 = na+mb (namb) = mb+mb = 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 6= 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 eso deixadas como exerccio para o leitor.

2

Sejam a, b N. Definimos o conjunto

S(a, b) = {xa+ yb; x, y N}.

claro que aX + bY = c, com (a, b) = 1, tem soluo se, e somentese, c S(a, b). Portanto, de fundamental importncia caracterizar oselementos do conjunto S(a, b).

Equaes Diofantinas Lineares 7

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 outrolado, 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 igualdadena igualdade acima, obtemos que c = na+mb, onde n < b, e m = aq + y.

2

Definamos 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) = {namb 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 emnmeros naturais se, e somente se,

c 6 L(a, b) = {namb N; n < b, m N}.

Demonstrao Como a equao aX + bY = c tem soluo se, e somentese, c S(a, b), o resultado segue-se do Corolrio.

2

Note que o conjunto L(a, b) finito e o seu maior elemento

maxL(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 noadmite soluo.

Na prtica, no difcil decidir se a equao aX+bY = c admite soluo.Se (a, b) 6 |c, a equao no tem soluo. Se (a, b)|c, a equao equiva-

lente a uma outra com (a, b) = 1. Com o algoritmo euclidiano, escreva

1 = (a, b) = namb.

Logo,c = cna cmb.

Agora, com a diviso euclidiana, escreva cn = qb+ n com n < b, logo,

c =

{na+ (qa cm)b S(a, b), se qa cmna (cm qa)b L(a, b), 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 soluominimal, 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, tenhasoluo e seja x0 = n, y0 = m a soluo minimal. As solues x, y da equaoso 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 Pro-posio 2, implica no resultado.

2

Equaes Diofantinas Lineares 9

Note que este tipo de equao tem, no mximo, um nmero finito desolues, correspondentes aos seguintes valores de t:

0, 1, . . . ,[ma

],

onde[ma

]representa o quociente da diviso euclidiana de m por a.

Exemplo 3. Vamos determinar para quais valores de c N a equao11X + 7Y = c tem solues em N.

O conjunto de lacunas de S(11, 7) o conjunto

L(11, 7) = {n11m7 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 6 L(11, 7).Exemplo 4. Resolvamos a equao 11X + 7Y = 58.

Como, de acordo com o Exemplo 3, 58 6 L(11, 7), a equao possuisolues. Para determin-las, considere o algoritmo euclidiano,

11 = 7 1 + 47 = 4 1 + 34 = 3 1 + 1Logo,

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, assolues 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 soluox0 = 4, y0 = 2.

Para resolver equaes como as acima, no necessrio usar toda a tcnicaque desenvolvemos, pois os nmeros envolvidos so suficientemente pequenospara que seja vivel achar as solues por inspeo.

No exemplo acima, basta testar os valores x = 1, 2, 3, 4 e 5 para verificarque apenas x = 4 possvel.

Problemas

1. Resolva as equaes:a) 90X 28Y = 22 b) 50X 56Y = 74c) 40X 65Y = 135 d) 8X 13Y = 232. Para quais valores de c a equao 90X + 28Y = c no possui solues?

3. Resolva as equaes:a) 16X + 7Y = 601 b) 30X + 17Y = 201c) 47X + 29Y = 1288 d) 8X + 13Y = 23

4. Dispondo de 100 reais, quais so as quantias que se podem gastar com-prando selos de 5 reais e de 7 reais?

5. Determine todos os mltiplos de 11 e de 9 cuja soma igual aa)79 b) 80 c) 270

6. Determine o menor inteiro positivo que tem restos 11 e 35 quando divi-dido, respectivamente, por 37 e 48.

7. Numa criao de coelhos e galinhas, contaram-se 400 ps. Quantas soas galinhas e quantos so os coelhos, sabendo que a diferena entre esses doisnmeros a menor possvel?

8. Subindo uma escada de dois em dois degraus, sobra um degrau. Subindoa 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 7e est compreendido entre 40 e 100.

9.(ENC 2002) Em certo pas, as cdulas so de $4 e $7. Com elas, possvelpagar, sem troco, qualquer quantia inteiraa) 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 mltiplode $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 demodo que se gaste 50 reais?