Demonstrar as seguintes questões:
Corolário 2: A equação a x+b y=1 tem solução se, e somente se, a e b são inteiros primos entre si.

Passo 1

O que o enunciado pede: demonstrar o Corolário 2, que afirma uma equivalência entre duas propriedades. Em palavras claras: precisamos provar que a equação diofantina linear
a x + b y = 1
tem solução em inteiros x e y se, e somente se, a e b são inteiros primos entre si (ou seja, \gcd(a,b)=1).
Informações dadas (assumidas do enunciado): a e b são inteiros; queremos soluções x,y também inteiros. O objetivo é provar duas implicações:
  1. Se existem inteiros x,y tais que a x + b y = 1 então \gcd(a,b)=1.
  2. Se \gcd(a,b)=1 então existem inteiros x,y tais que a x + b y = 1.

Passo 2

Definições e conceitos básicos que vamos usar (explicados devagar):
  • Dizemos que um inteiro d divide um inteiro n (escrevemos d\mid n) quando existe inteiro k com n = d k. Ex.: 3\mid 12 porque 12 = 3\cdot 4.
  • O máximo divisor comum de a e b, escrito \gcd(a,b), é o maior inteiro positivo que divide simultaneamente a e b.
  • Se um inteiro d divide a e divide b, então dizemos que d é um divisor comum. A propriedade chave que usaremos é: se um divisor comum divide uma combinação linear a x + b y, então divide cada membro dessa combinação (porque se d\mid a e d\mid b, então d\mid (a x + b y) para quaisquer inteiros x,y).
Vamos também lembrar uma ideia útil (não precisamos aqui provar o algoritmo completo): o método clássico para mostrar que \gcd(a,b) pode ser escrito como combinação linear de a e b usa o argumento do “menor elemento positivo” de um conjunto de combinações lineares — esse é o caminho que vou seguir porque é construtivo e elementar.

Passo 3

Prova da implicação fácil (necessidade): se existe solução então \gcd(a,b)=1.
Suponha que existam inteiros x_0,y_0 tais que
a x_0 + b y_0 = 1.
Se d é qualquer divisor comum de a e b, então d divide a x_0 e d divide b y_0, logo d divide a soma a x_0 + b y_0. Ou seja, d\mid 1. Os únicos divisores inteiros de 1 são 1 e -1, portanto o único divisor positivo comum possível é 1. Assim o máximo divisor comum é \gcd(a,b)=1. Isso prova que a existência de solução implica que a e b são primos entre si.
Comentário amigável: essa parte é direta — qualquer divisor comum “passa” para a combinação linear e acaba dividindo 1, então só pode ser 1.

Passo 4

Estratégia para a implicação difícil (suficiência): se \gcd(a,b)=1 então existe solução. Plano: construir inteiros x,y com a x + b y = 1. Vou usar o argumento do menor elemento positivo do conjunto das combinações lineares de a e b.
Defina o conjunto
S = \{\,a u + b v \mid u,v\in\mathbb{Z},\\ a u + b v > 0\,\}.
Note que S é um subconjunto não vazio dos inteiros positivos (por exemplo, se u=1,v=0 então a u + b v = a; se a for negativo podemos escolher u=-1 etc.; enfim, existe alguma combinação não nula e podemos considerar valor absoluto se precisar — o que importa é que existem combinações não nulas). Pelo princípio do menor elemento em \mathbb{Z}_{>0}, S tem um menor elemento; denote esse menor elemento por d:
d = \min S.

Passo 5

Mostrar que d divide a e d divide b.
Pela definição de d, existem inteiros u_0,v_0 tais que
d = a u_0 + b v_0.
Agora use o algoritmo da divisão entre inteiros: divida a por d. Existem inteiros q e r com 0\le r < d tais que
a = q d + r.
Substituindo d = a u_0 + b v_0 obtemos
r = a - q d = a - q(a u_0 + b v_0) = a(1 - q u_0) + b(-q v_0).
Portanto r é uma combinação inteira de a e b. Se r>0, então r\in S, mas isso contradiz a minimalidade de d pois 0\le r < d. Logo só é possível r=0. Assim d\mid a. Pelo mesmo argumento (dividindo b por d) obtemos d\mid b.
Comentário: a ideia é clássica — o resto da divisão de a por d também é combinação linear; se fosse positivo seria menor que d, contradizendo a escolha de d.

Passo 6

Concluir que d=\gcd(a,b) e terminar a prova.
Como d divide a e b, d é um divisor comum. Logo d\le \gcd(a,b). Por outro lado, \gcd(a,b) divide qualquer combinação linear de a e b, então \gcd(a,b) divide d. Como d e \gcd(a,b) são inteiros positivos e cada um divide o outro, necessariamente d=\gcd(a,b).
Agora use a hipótese \gcd(a,b)=1. Então d=1. Mas lembrando que d foi obtido como combinação linear d = a u_0 + b v_0, concluímos que existem inteiros u_0,v_0 tais que
a u_0 + b v_0 = 1.
Isso é exatamente o que queríamos: existência de solução inteira para a x + b y = 1.
Comentário simpático: essa parte é a essência do Lema de Bézout — quando duas entradas são primos entre si, 1 aparece como combinação linear delas.

Passo 7

Exemplo prático (para fixar e para você levar pra prova): tome a=14 e b=5. Aqui \gcd(14,5)=1. Aplicando o algoritmo descrito (ou o algoritmo extendido de Euclides) encontra-se, por exemplo, 14\cdot (-1) + 5\cdot 3 = 1. De fato,
14\cdot(-1) + 5\cdot 3 = -14 + 15 = 1.
Então x=-1,y=3 é solução. Esse tipo de construção é exatamente a aplicação prática do argumento anterior; no exame, se pedirem os coeficientes, você pode executar o algoritmo estendido de Euclides para obtê-los.

Resposta

A equação a x + b y = 1 tem solução em inteiros x,y se, e somente se, \gcd(a,b)=1.

Exercícios relacionados