bc1405 – Equações diofantinas lineares

Observemos o seguinte

{\mathrm{mdc}(42,12)=6}:

\displaystyle  42= 12\cdot 3 + 6

\displaystyle  12= 6\cdot 2 + 0

\displaystyle \boxed{42\cdot 1 + 12 \cdot(- 3) = 6}

{\mathrm{mdc}(41,12)=1}:

\displaystyle  41= 12\cdot 3 + 5

\displaystyle  12= 5\cdot 2 + 2

\displaystyle  5= 2\cdot 2 + 1

\displaystyle  2= 1\cdot 2 + 0

\displaystyle  1 = 5 - 2\cdot 2

\displaystyle  = 5 - (12-5\cdot 2) 2 = 5 \cdot 5 - 12 \cdot 2

\displaystyle  = (41-12\cdot 3) \cdot 5 - 12\cdot 2 = 41\cdot 5 -12\cdot 17

\displaystyle  \boxed{1 = 41\cdot 5 +12\cdot (-17)}

{\mathrm{mdc}(81,57)=3}:

\displaystyle  81 = 57\cdot 1 + 24 \Longrightarrow 24 = 81 - 57\cdot 1

\displaystyle  57 = 24\cdot 2 + 9 \Longrightarrow 9 = 57 - 24\cdot 2

\displaystyle  24 = 9\cdot 2 + 6 \Longrightarrow 6= 24 - 9\cdot 2

\displaystyle  9 = 6\cdot 1 + 3 \Longrightarrow 3 = 9 - 6

\displaystyle  6 = 3\cdot 2 + 0.

\displaystyle  3 = 9 - 6 = 9 - 24 +9\cdot 2 = (9)3 - 24

\displaystyle  = (57 - 24\cdot 2) 3 - 24 = 57\cdot 3 - (24) 7

\displaystyle  =57\cdot 3 - ( 81 - 57\cdot 1) 7 = 81\cdot (-7) +57\cdot 10

\displaystyle \boxed{ 3 = 81\cdot (-7) + 57 \cdot 10}

Obs.: {1 = 41\cdot 17 +12\cdot (-58)} e { 3 =81\cdot (12) + 57 \cdot (-17)}, i.e., o modo de escrever não é único.

Definimos

\displaystyle   a\cdot {\mathbb Z} + b\cdot {\mathbb Z}:= \{a\cdot n+b\cdot m\colon n,m\in{\mathbb Z}\} \ \ \ \ \ (36)

o conjunto de todos os números que são combinações lineares inteiras de {a} e {b}, ou seja, o conjunto dos inteiros da forma {ax+by} para algum {x} e algum {y} inteiros. Vamos provar que o menor elemento positivo desse conjunto é o mdc de {a} e {b}.

Teorema 18 (Teorema de Bézout) Se {a,b\in{\mathbb Z}} então existem inteiros {x} e {y} tais que

\displaystyle  ax+by =\mathrm{mdc}(a,b) \ \ \ \ \ (37)

Demonstração: O caso {a=b=0} é trivial. Vamos supor que {a\neq 0} ou {b\neq 0}, portanto {(a\cdot {\mathbb Z} + b\cdot {\mathbb Z})\cap {\mathbb Z}^+\neq\emptyset} (justifique com detalhes) e podemos usar o PBO e tomarmos

\displaystyle d:=\min [(a\cdot {\mathbb Z} + b\cdot {\mathbb Z})\cap {\mathbb Z}^+]

o menor elemento positivo de {a\cdot {\mathbb Z} + b\cdot {\mathbb Z}}. Existem {x_0,y_0\in{\mathbb Z}} tais que {d=ax_0+by_0}.

Mostraremos que {d} divide qualquer elemento de {a\cdot {\mathbb Z} + b\cdot {\mathbb Z}}.

Seja {c\in a\cdot {\mathbb Z} + b\cdot {\mathbb Z}}. Existem inteiros {x_1} e {y_1} tais que {c=ax_1+by_1}. Pelo Teorema da Divisão existem inteiros {q} e {r} tais que {c=dq+r}, onde {0\leq r < d}, e

\displaystyle  r=c-dq=ax_1+by_1-(ax_0+by_0)q=a(x_1-x_0q)+b(y_1-y_0q), \ \ \ \ \ (38)

ou seja, {r\in a\cdot {\mathbb Z} + b\cdot {\mathbb Z}}. Como {0\leq r<d} e {d} é mínimo deduzimos que {r=0}, portando {d|c}.

Em particular, {d|a} e {d|b}, isto é, {d\in D(a)\cap D(b)} por definição de mdc temos {d\leq \mathrm{mdc}(a,b)}. Por outro lado, {d=ax_0+by_0} e como {\mathrm{mdc}(a,b)|ax_0+by_0} segue que {\mathrm{mdc}(a,b) | d} (veja exerc. 31, item 7). Do exercício 31 (item 2) {\mathrm{mdc}(a,b)\leq d}, logo, {\mathrm{mdc}(a,b)=d}. \Box

Corolário 19 Prove que se {a} e {b} são inteiros não ambos nulos, então {d=\mathrm{mdc}(a,b)} se, e somente se,

  1. {d\geq 0};
  2. {d|a} e {d|b};
  3. para todo inteiro {c}, {c|a} e {c|b} {\Rightarrow} {c|d}.

Demonstração: Exercício. \Box

Corolário 20 Se {a,b,c} são inteiros tais que {a|bc} e {\mathrm{mdc}(a,b)=1}, então {a|c}.

Demonstração: Exercício. \Box

Exercício 32 Se {a|c} e {b|c}, {c\neq 0}, e {\mathrm{mdc}(a,b)=1} então {ab|c}.

Exercício 33 Se {a} e {b} são inteiros, pelo menos um não-nulo, e {d=\mathrm{mdc}(a,b)}, então {\mathrm{mdc}(\frac ad,\frac bd)=1}.

Demonstração: Existem {n,m} tais que {an+bm=d}, portanto { \frac adn+ \frac bd m=1}, que é o menor positivo de { \frac ad{\mathbb Z}+ \frac bd {\mathbb Z}=1}, portanto {\mathrm{mdc}(\frac ad,\frac bd)=1}. \Box

— Equações diofantinas lineares —

Estudaremos as equações da forma

\displaystyle  aX+bY=c \ \ \ \ \ (39)

em que {a,b,c\in{\mathbb Z}}; uma solução para tal equação é um par de inteiros {(x_0,y_0)} para o qual a igualdade acima vale quando {X=x_0} e {Y=y_0}.

Proposição 21 Dados inteiros {a}, {b} e {c} a equação (39) admite solução inteira se e somente se {\mathrm{mdc}(a,b)|c}.

Demonstração: Denotemos por {d:=\mathrm{mdc}(a,b)} e por {(n,m)} uma solução de {aX+bY=d} caso exista.

De {d|(ax+by)} para quaisquer {x,y\in{\mathbb Z}}, em particular, caso (39) tenha solução, {d|an+bm} e portanto {d|c}.

Por outro lado, se {d|c} então existe {q} tal que {dq=c}. Pelo Teorema de Bézout existem {x,y\in{\mathbb Z}} tais que {ax+ by=d}, portanto {(qx,qy)} é solução de {aX+bY=c}. \Box

O resultado acima estabelece a seguinte iguldade de conjuntos

\displaystyle  a\cdot {\mathbb Z} + b\cdot {\mathbb Z} = \mathrm{mdc}(a,b) \cdot {\mathbb Z}

Notemos que se {a} e {b} são coprimos então (39) tem solução qualquer que seja o inteiro {c}. Também vale a recíproca.

Corolário 22 Dois inteiros {a}, {b} são coprimos se, e só se, a equação (39) admite solução inteira, qualquer que seja {c\in{\mathbb Z}}.

Demonstração: Se {a} e {b} são coprimos então, pela proposição 21 a equação (39) tem solução qualquer que seja o inteiro {c}.

Agora, se existem {x,y\in{\mathbb Z}} que satisfazem a equação para {c=1}, então todo divisor {d} de {a} e {b} divide {ax+ay=1}, portanto, {d=\pm 1}, logo {\mathrm{mdc}(a,b)=1}. \Box

Notemos que para {a} ou {b} não-nulo e {d=\mathrm{mdc}(a,b)\neq 0}

\displaystyle ax+by=c \Longleftrightarrow \frac ad x+ \frac bd y = \frac cd

para quaiquer {x,y\in{\mathbb Z}} ({d|c} como provamos acima, logo {\frac cd} tem sentido). Ademais {\mathrm{mdc}(\frac ad,\frac bd)=1}, portanto toda equação diofantina linear

\displaystyle aX+bY=c

é equivalente — tem as mesmas soluções — de uma equação reduzida

\displaystyle \frac ad X+ \frac bd Y = \frac cd

na qual os coeficientes são coprimos.

Ainda, se {(x_0,y_0)} é uma solução de {\frac ad X+ \frac bd Y = 1} então {(x_0\frac cd,y_0\frac cd)} é uma solução de {\frac ad X+ \frac bd Y = \frac cd}.

Por exemplo, para achar uma solução de {81X+57Y=27} basta achar uma solução de {27X+19Y=9} e para achar uma solução dessa equação, primeiro procuramos por uma solução de {27X+19Y=1}.

Usando o algoritmo de Euclides para calcular o mdc e substituindo-se os restos, como fizemos anteriormente {\mathrm{mdc}(27,19)=1}:

\displaystyle  27 = 19 \cdot 1 + 8

\displaystyle  19 = 8 \cdot 2 + 3

\displaystyle  8 = 3\cdot 2 + 2

\displaystyle  3 = 2\cdot 1 + 1 \Leftrightarrow 1 = 3 - 2\cdot 1

\displaystyle  \Leftrightarrow 1 = 3 - ( 8 - 3\cdot 2 ) \cdot 1

\displaystyle  \Leftrightarrow 1 = -8+3\cdot 3 = -8+ (19 - 8 \cdot 2 ) \cdot 3

\displaystyle  \Leftrightarrow 1 = 8\cdot (-7) + 19 \cdot 3

\displaystyle  \Leftrightarrow 1 = (27 - 19 \cdot 1 ) \cdot (-7) + 19 \cdot 3

\displaystyle  \Leftrightarrow \boxed{1 = 27\cdot (-7) +19 \cdot 10}

logo {(-7,10)} é solução de {27X+19Y=1}, portanto {(-7\cdot 9,10 \cdot 9)} é solução de {27X+19Y= 9} e, consequentemente, de {81X+57Y=27}.

Teorema 23 Se {(x_0,y_0)} é uma solução particular de (39) com {a\neq 0} e {b\neq 0}, então o conjunto de todas as soluções de (39) é

\displaystyle   \left\{ \left(x_0+\frac bdt, y_o- \frac adt\right)\colon t\in{\mathbb Z}\right\} \ \ \ \ \ (40)

em que {d=\mathrm{mdc}(a,b)}.

Demonstração: É um exercício verificar que { \left(x_0+\frac bdt, y_o- \frac adt\right)} é solução de (39).

Agora, suponha que {(x,y)} seja uma solução de (39), então

\displaystyle ax+by=c=ax_0+by_0

portanto

\displaystyle a(x-x_0)=b(y_0-y).

Se {a=dr} e {b=sd},

\displaystyle  r(x-x_0)=s(y_0-y) \ \ \ \ \ (41)

com {\mathrm{mdc}(r,s)=1}. Ainda, {s|r(x-x_0)}, portanto, {s|(x-x_0)}, ou seja, existe {t\in{\mathbb Z}} tal que {x-x_0 = st}, portanto

\displaystyle  x=x_0+\frac b{d}t. \ \ \ \ \ (42)

Substituindo {x-x_0 = st} em (41) {s(y_0-y)= r(x-x_0) = rst}, logo

\displaystyle  y=y_0-\frac{a}{d}t \ \ \ \ \ (43)

como queríamos. \Box

Exercício 34 De quantas maneiras podemos comprar selos de 3 e 5 reais de modo a gastar 50 reais?

Exercício 35 Mostre que se {(x_0,y_0)} é solução de {aX+bY=c}, então

  1. {(-x_0,y_0)} é solução de {-aX+bY=c};
  2. {(x_0,-y_0)} é solução de {aX-bY=c};
  3. {(-x_0,-y_0)} é solução de {-aX-bY=c}.

Exercício 36 Sejam {a,b,c,d} inteiros. Defina {\mathrm{mdc}(a,b,c) := \mathrm{mdc}(\mathrm{mdc}(a,b),c)}. Estabeleça e prove um critério para existência de solução de

\displaystyle aX+bY+cZ=d.

— Exercícios —

  1. Deduza do Teorema de Bézout:

    1. se {a|c} então {\mathrm{mdc}(a,b)|\mathrm{mdc}(c,b)}.
    2. se {a} e {b} são coprimos então {\mathrm{mcd}(ac,b)=\mathrm{mdc}(c,b)}.
  2. Sejam {a} e {b} inteiros positivos e coprimos. Mostre que para todo inteiros {c > ab-a-b}, a equação {aX+bY=c} admite soluções inteiras não-negativas.
  3. Sejam {a} e {b} inteiros positivos e coprimos. Mostre que equação {aX - bY=c} admite infinitas soluções nos naturais.
  4. Determine as soluções inteiras de
    1. {3x+4y=20}
    2. {5x-2y=2}
    3. {18x-20y=-8}
  5. Ache todos inteiros positivos que deixam resto 6 quando divididos por 11 e resto 3 quando divididos por 7.
  6. Ache todos os naturais que quando divididos por 18 deixam resto 4 e que quando divididos por 14 deixam resto 6.
  7. Um parque cobra ingresso de 1 real de crianças e 3 de adultos. Para que a arrecadação de um dia seja 200 reais qual o menor numero de pessoas, adultos e crianças, que frequentam o parque?

  8. Um fazendeiro dispõe de 1.770 reais pra gastar em boi e cavalo. Um cavalo custa 31 reais e boi 21 reais. Qual o maior número de animais que pode comprar?

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s