Aula 11-Equações Diofantinas

Prévia do material em texto

Equações diofantinas
Uma equação diofantina linear de duas variáveis (denotadas por x e y) é uma equação da
forma
ax+ by = c
onde a, b ∈ Z∗ (ou seja, a e b são números inteiros não nulos) e c ∈ Z. Uma solução da equação
diofantina é um par ordenado de números inteiros (x, y) cujas coordenadas x e y satisfazem a
equação a · x+ b · y = c.
Quando estamos trabalhando com equações diofantinas, estamos interessados apenas em
soluções inteiras, ou seja, estamos interessados apenas em valores de x, y ∈ Z.
Exemplo 1. A equação linear
3x+ 2y = 7
é uma equação diofantina de duas variáveis. O par ordenado (1, 2) é uma solução dessa equação
diofantina, pois
3 · 1 + 2 · 2 = 3 + 4 = 7
O par ordenado (3,−1) também é uma solução dessa equação diofantina, pois
3 · 3 + 2 · (−1) = 9− 2 = 7
O par ordenado (−1, 5) também é uma solução dessa equação diofantina, pois
3 · (−1) + 2 · 5 = −3 + 10 = 7
Observe que as soluções de uma equação diofantina linear nada mais são do que as cons-
tantes x e y das combinações lineares de a e b que resultam no número inteiro c. Logo, para
uma equação diofantina linear ter solução é necessário que c possa ser escrito como combinação
linear de a e de b. Mas (pela demonstração do Teorema de Bèzout) vimos que se c pode ser
escrito como combinação linear dos números a e b, então necessariamente mdc(a, b) | c (ou seja,
c é um múltiplo do máximo divisor comum de a e de b).
Afirmação: Todo múltiplo do mdc(a, b) pode ser escrito como combinação linear de a e de b.
Prova: Seja c um múltiplo de d = mdc(a, b). Então existe n ∈ Z tal que c = d · n.
Pelo Teorema de Bèzout, d pode ser escrito como combinação linear de a e de b. Ou seja,
existem números x0, y0 ∈ Z tais que
d = a · x0 + b · y0
Multiplicando ambos os lados da equação por n, obtemos
d · n = (a · x0 + b · y0) · n
d · n = a · x0 · n+ b · y0 · n
c = a · (x0 · n) + b · (y0 · n)
Logo, se tomarmos x = x0 · n e y = y0 · n, então
c = a · x+ b · y
e, portanto, c pode ser escrito como combinação linear de a e de b.
Proposição 1. A equação diofantina linear ax+ by = c possui solução se, e somente se, c for
um múltiplo do mdc(a, b).
1
Exemplo 2. A equação diofantina linear
9x+ 6y = 7
não possui solução inteira, pois mdc(9, 6) = 3 e 3 ��| 7.
Exemplo 3. A equação diofantina linear
7x+ 3y = 5
possui solução inteira, pois mdc(7, 3) = 1 e 1 | 5.
Se mdc(a, b) = 1, então a equação diofantina linear ax+ by = c necessariamente possui solução.
De fato, como 1 | c para todo c ∈ Z, então a equação diofantina linear ax + by = c possui
solução.
Exemplo 4. Determine (se existir) uma solução para a equação diofantina linear
112x+ 264y = 56
Vamos calcular mdc(112, 264). Temos que
264 = 112 · 2 + 40
112 = 40 · 2 + 32
40 = 32 · 1 + 8
32 = 8 · 4 + 0
Concluímos que mdc(112, 264) = mdc(8, 0) = 8.
Como 56 é múltiplo de 8, então a equação diofantina tem solução.
Para determinar uma solução, vamos escrever 8 = mdc(112, 264) como combinação linear de
112 e de 264.
264 = 112 · 2 + 40 → 40 = 264− 112 · 2
112 = 40 · 2 + 32 → 32 = 112− 40 · 2
40 = 32 · 1 + 8 → 8 = 40− 32
Logo,
8 = 40− 32
= 40− (112− 40 · 2)
= 40− 112 + 40 · 2
= 40 · 3− 112
= (264− 112 · 2) · 3− 112
= 264 · 3− 112 · 6− 112
= 264 · 3− 112 · 7
= 264 · 3 + 112 · (−7)
= 112 · (−7) + 264 · 3
Portanto,
8 = 112 · (−7) + 264 · 3
Como 56 = 8 · 7, então
8 · 7 = (112 · (−7) + 264 · 3) · 7
56 = 112 · (−7) · 7 + 264 · 3 · 7
56 = 112 · (−49) + 264 · 21
Concluímos que (−49, 21) é uma solução da equação diofantina.
2
Proposição 2. Suponha que (x0, y0) é uma solução particular da equação diofantina linear
ax+ by = c. Então a equação diofantina possui infinitas soluções e o conjunto dessas soluções
é
S =
{(
x0 +
b
d
t, y0 − a
d
t
) ∣∣∣∣ t ∈ Z}
onde d = mdc(a, b). Chamamos o conjunto S de solução geral da equação diofantina.
Prova: Nessa proposição, temos que:
Hipótese: (x0, y0) é uma solução da equação diofantina linear ax+ by = c
Tese: O conjunto de todas as soluções da equação diofantina é S =
{(
x0 +
b
d
t, y0 − ad t
) ∣∣ t ∈ Z},
onde d = mdc(a, b).
Observe que temos que provar duas afirmativas. A primeira é: Toda solução da equação
diofantina é da forma
(
x0 +
b
d
t, y0 − ad t
)
para algum t ∈ Z. A segunda é: Todo par ordenado
da forma
(
x0 +
b
d
t, y0 − ad t
)
, t ∈ Z, é solução da equação diofantina.
Vamos provar primeiro que se (x, y) é uma solução da equação diofantina, então existe t ∈ Z
tal que
x = x0 +
b
d
t e y = y0 − a
d
Suponha que (x, y) é uma solução qualquer da equação difantina. Temos que
ax+ by = c
Como (x0, y0) é solução também, então
ax0 + by0 = c
Logo,
ax+ by = c = ax0 + by0
ax+ by = ax0 + by0
ax− ax0 = by0 − by
a(x− x0) = b(y0 − y)
Como d = mdc(a, b), então existem números inteiros n,m tais que a = d · n e b = d ·m
dn(x− x0) = dm(y0 − y)
n(x− x0) = m(y0 − y) ⇒ n | m(y0 − y)
Como d é o maior divisor comum possível de a e de b, então mdc(n,m) = 1. Logo, devemos ter
n|(y0 − y)
Existe então algum t ∈ Z tal que y0 − y = n · t e, posrtanto,
y = y0 − n · t = y0 − a
d
t
Substituindo isso na equação
a(x− x0) = b(y0 − y)
3
obtemos
a(x− x0) = b
(
y0 −
[
y0 − a
d
t
])
a(x− x0) = b
(
y0 − y0 + a
d
t
)
a(x− x0) = b · a
d
t
x− x0 = b
d
t
x = x0 +
b
d
t
Logo (x, y) =
(
x0 +
b
d
t, y0 − ad t
)
é solução da equação diofantina.
Vamos provar agora que todo par ordenado da forma
(
x0 +
b
d
t, y0 − ad t
)
, t ∈ Z, é solução da
equação diofantina.
Suponha que (x0, y0) é solução da equação diofantina. Temos que
a
(
x0 +
b
d
t
)
+ b
(
y0 − a
d
t
)
= ax0 +
�
�
�ab
d
t+ by0 −
�
�
�ba
d
t = ax0 + by0 = c
Logo,
(
x0 +
b
d
t, y0 − ad t
)
é solução da equação diofantina.
Exemplo 5. Determine a solução geral das seguintes equações diofantinas:
(a) 112x+ 264y = 56.
Já sabemos que (−49, 21) é uma solução da equação diofantina e que mdc(112, 264) = 8.
Temos que
a
d
= 112
8
= 14 e b
d
= 264
8
= 33. Logo, a solução geral da equação diofantina é
S =
{(
−49 + b
d
t, 21− a
d
t
) ∣∣∣∣ t ∈ Z} = {(−49 + 33t, 21− 14t) | t ∈ Z}
Para cada valor de t ∈ Z que tomarmos, (−49 + 33t, 21− 14t) será solução da equação
diofantina. Por exemplo,
• Se tomarmos t = 1, obtemos a solução (−49 + 33, 21− 14) = (−16, 7).
• Se tomarmos t = 0, obtemos a solução particular utilizada para construir a solução
geral (−49, 21).
• Se tomarmos t = −1, obtemos a solução (−49− 33, 21 + 14) = (−82, 35).
• Se tomarmos t = 2, obtemos a solução (−49 + 66, 21− 28) = (17,−7).
• Se tomarmos t = −2, obtemos a solução (−49− 66, 21 + 28) = (−115, 49).
4