Encontrar o menor inteiro da forma 48 x+64 y, onde x e y são inteiros.

Passo 1

O enunciado pede o menor inteiro da forma
48x + 64y
onde x,y 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 gcd.

Passo 2

Vamos calcular gcd(48,64) pelo Algoritmo de Euclides:
64 = 48 cdot 1 + 16,
48 = 16 cdot 3 + 0
Quando o resto fica zero, o divisor anterior é o gcd. Logo
gcd(48,64) = 16

Passo 3

O Teorema de Bézout garante que existem x,yinZ tais que
48x + 64y = gcd(48,64) = 16,
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:
16 = 64 - 48cdot1
Isto mostra que podemos escolher x=-1, y=1 e obter
48cdot(-1) + 64cdot1 = 16

Resposta

O menor inteiro positivo da forma 48x+64y é 16.

Exercícios relacionados