Universidade Federal do Rio de Janeiro
Instituto de Matemática
Prof. Tulio Gentil
Álgebra I - Números Inteiros
Aula 11 - Equações Lineares e Congruências
1 Equações Diofantinas Lineares
Uma equação da forma
ax + by = c,
onde a, b, c são números inteiros com a e b não ambos nulos é chamada equação diofantina
linear. As soluções para essa equação são os pares de números inteiros (x, y) ∈ Z × Z tais
que ax + by = c.
Exemplo 1.1. a) Para a equação x − 2y = −1, temos que os pares (1, 1) e (−1, 0)
são exemplos de soluções para essa equação.
b) A equação 4x + 6y = 5 não admite solução inteira, pois o lado esquerdo é sempre
par e o lado esquerdo é ímpar.
O resultado a seguir nos fornece condições para a existência de soluções para equações
diofantinas lineares.
Proposição 1.2. Sejam a, b, c ∈ Z e d = mdc(a, b). A equação diofantina ax + b = c
admite solução se, e somente se, d|c.
Demonstração. Defina o I o seguinte subconjunto de Z:
I = {ax + by | x, y ∈ Z}.
Note que I é um ideal de Z. Assim, I = kZ, onde k é um inteiro positivo. Observe que
k ∈ D(a, b) e logo k = d = mdc(a, b). Obviamente, a equação ax + by = c tem solução
se, e somente se c ∈ I, isto é, se, e somente se, d|c.
Teorema 1.3. Sejam a, b, c ∈ Z tais que d = mdc(a, b)|c. Escreva d = ra + sb com
r, s ∈ Z (isso é possível usando o Teorema de Bezout), temos que
c c
x0 = r · , y 0 = s ·
d d
é uma solução da equação ax + by = c. Toda outra solução é da forma
c b c a
x=r· + · t, y = s · − · t, com t ∈ Z.
d d d d
Reciprocamente, para todo t ∈ Z, os valores de x e y dados acima são soluções da equação
ax + by = c.
Demonstração. Multiplicando ambos os membros da equação ra + sb = d por c/d, temos:
c c
r a + s b = c.
d d
Logo,
c c
x0 = r · , y 0 = s ·
d d
é uma solução da equação ax + by = c. Vamos mostrar agora que
c b c a
x=r· + · t, y = s · − · t, com t ∈ Z.
d d d d
é solução para a equação ax + by = c. Com efeito,
c b c a b a
a r · + · t + b s · − · t = a x0 + · t + b y 0 − · t
d d d d d d
ab ab
= ax0 + t + by0 − t = ax0 + by0 = c.
d d
Por fim, vamos mostrar que toda solução de ax + by = c é dessa forma. Seja x′ , y ′ outra
solução de ax + by = c. Então ax′ + by ′ = c = ax0 + by0 . Portanto,
a(x′ − x0 ) = b(y0 − y ′ ).
Como d = mdc(a, b) existem a1 , b1 ∈ Z tais que a = a1 d e b = b1 d e
a b mdc(a, b) d
mdc(a1 , b1 ) = mdc , = = = 1.
d d d d
Dividindo a expressão a(x′ − x0 ) = b(y0 − y ′ ) por d, temos que
a1 (x′ − x0 ) = b1 (y0 − y ′ ).
Em particular, b1 |a1 (x′ − x0 ) e como mdc(a1 , b) = 1, do Teorema de Euclides, segue que
b1 |x′ − x0 e existe t ∈ mZ tal que x′ − x0 = b1 t, isto é,
b
x′ = x0 + t.
d
Substituindo x′ − x0 por b1 t na expressão a1 (x′ − x0 ) = b1 (y0 − y ′ ), temos que
a
y ′ = y0 − t.
d
Exemplo 1.4. Determine, caso existam, todas as soluções da equação diofantina linear
56x + 72y = 40.
Temos que mdc(56, 72) = 8. Como 8|40, pela Proposição 1.2 temos que a equação admite
solução. Pelo Teorema de Bezout, existem r, s ∈ Z tais que r56 + s72 = 8. Usando o
Algoritmo de Euclides, obtemos r = 4 e s = −3 satisfaz essa condição. Pelo Teorema 1.3
c c
x0 = r · = 20, y0 = s · = −15
d d
é uma solução particular. Além disso, o Teorema 1.3 nos fornece que toda outra solução
da nossa equação é
b a
x = x0 + · t = 20 + 9t, y = y0 − · t = −15 − 7t, com t ∈ Z.
d d
Exercício 1.5. Uma pessoa deseja adquirir 125 l de um determinado líquido que é ven-
dido em recipientes de 7 l ou de 15 l. Quais são as possíveis unidades de recipientes de
7 l e 15 l para que essa pessoa compre exatamente os 125 l?
2 Congruências
Definição 2.1. Seja m ̸= 0 um inteiro fixo. Dizemos que a e b são congruentes a m se
m|(a − b). Neste caso, escrevemos
a ≡ b (mod m).
Note que se m|(a − b), então existe q ∈ Z tal que a − b = mq ou ainda, a = b + mq.
Como m|(a − b) se, e somente se |m||(a − b), vamos nos limitar ao caso em que m > 0.
Por exemplo, 3 ≡ 9 (mod 3) e 3 ≡ 9 (mod 2). A proposição seguinte nos dá uma caracte-
rização para definição de congruência.
Proposição 2.2. Seja m um inteiro fixo. Dois inteiros a e b são congruentes módulo m
se, e somente eles têm como resto o mesmo inteiro na divisão por m.
Demonstração. Usando o Algoritmo da Divisão de Euclides, sejam
a = mq1 + r1 , com 0 ≤ r1 < m
b = mq2 + r2 , com 0 ≤ r2 < m.
Então,
a − b = m(q1 − q2 ) + (r1 − r2 ),
logo,
m|(a − b) se e somente se m|(r1 − r2 ) se, e somente se r1 − r2 = 0.
Portanto, a ≡ b (mod m) se, e somente se r1 = r2 .
Uma coleção de m inteiros {a1 , · · · , am } é dita-ser um sistema completo de resíduos
módulo m se cada inteiro é congruente módulo m a um único ai . Obviamente o sistema
completo de resíduos mais simples que podemos obter é {0, 1, · · · , m − 1}, mas não é o
único.
A proposição a seguir nos fornece propriedades importantes da congruência.
Proposição 2.3. Sejam m > 0 um inteiro fixo e a, b, c, d ∈ Z. Então
a) a ≡ a (mod m)
b) Se a ≡ b (mod m), então b ≡ a (mod m)
c) Se a ≡ b (mod m) e b ≡ c (mod m), então a ≡ c (mod m).
d) Se a ≡ b (mod m) e c ≡ d (mod m), então a + c ≡ b + d (mod m).
e) Se a ≡ b (mod m), então a + c ≡ b + c (mod m).
f ) Se a ≡ b (mod m) e c ≡ d (mod m), então ac ≡ bd (mod m).
g) Se a ≡ b (mod m), então an ≡ bn (mod m) para todo inteiro positivo n.
h) Se a + c ≡ b + c (mod m), então a ≡ b (mod m).
Demonstração. c) Suponha que a ≡ b (mod m) e b ≡ c (mod m). Então m|(a − b) e
m|(b − c) e portanto m|((a − b) + (b − c)), isto é, m|(a − b). Portanto, a ≡ c (mod m).
f) Suponha que a ≡ b (mod m) e c ≡ d (mod m). Então existem q1 , q2 ∈ Z tais que
a = b + q1 m e c = d + q2 m.
Logo,
ac = bd + (bq2 + bq1 + q1 q2 m)m,
ou seja, m|(ac − bd), e portanto ac ≡ bd (mod m).
Os demais itens são deixados como exercício.
O item h) da Proposição acima é análoga a Lei do Cancelamento da adição. Em geral,
para a multiplicação, a propriedade cancelativa não vale em congruências. Por exemplo,
3 ̸≡ 0 (mod 6) e 3 · 3 ≡ 3 · 5 (mod 6) mas 3 ̸≡ 5 (mod 6).
Proposição 2.4. Seja m um inteiro fixo e sejam a, b, c ∈ Z. Se mdc(c, m) = 1, então
ac ≡ bc (mod m) implica que a ≡ b (mod m).
Demonstração. Suponha ac ≡ bc (mod m). Então m|(a − b)c. Como mdc(c, a) = 1, então
pelo Teorema de Euclides, m|(a − b) e portanto, a ≡ b (mod m).
Exemplo 2.5. Determine o resto de 560 na divisão por 26.
Pelo Algoritmo da Divisão de Euclides, podemos escrever 560 = 26q + r, onde 0 ≤ r <
26. O problema é encontrar o inteiro r. Note que 560 ≡ r (mod 26).
Observe que 52 = 25 ≡ −1 (mod 26) e pela proposição anterior, 54 ≡ 1 (mod 26).
Analogamente, 560 = (54 )15 ≡ 115 (mod 26). Portanto, o resto de 560 na divisão por 26 é
1.