Encontrar o menor inteiro da forma
, onde
e
são inteiros.
Passo 1
O enunciado pede o menor inteiro da forma
onde
são inteiros.
Isto é um clássico problema de Teorema de Bézout: o menor inteiro positivo expressável como combinação linear de dois números é o seu máximo divisor comum, o .
Isto é um clássico problema de Teorema de Bézout: o menor inteiro positivo expressável como combinação linear de dois números é o seu máximo divisor comum, o
Passo 2
Vamos calcular
pelo Algoritmo de Euclides:
Quando o resto fica zero, o divisor anterior é o
. Logo
Passo 3
O Teorema de Bézout garante que existem
tais que
e que nenhum inteiro positivo menor que 16 pode ser obtido dessa forma.
Passo 4
Para encontrar uma combinação explícita, voltamos um passo no Algoritmo de Euclides:
Isto mostra que podemos escolher
,
e obter
Resposta
O menor inteiro positivo da forma
é
.