MA14 U8

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,


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


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


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


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?

Documents

MA14 U8