Se
e
são dois inteiros positivos quaisquer, prove que existe um inteiro positivo
tal que
. (Use o PBO).
Passo 1
O problema pede para mostrar que, dados inteiros positivos
e
, existe
tal que
. Vamos usar o Princípio da Boa Ordenação, que diz que todo subconjunto não vazio de inteiros positivos tem um menor elemento.
Passo 2
Suponha, para chegar a uma contradição, que não exista
com
. Então, para todo
temos
, ou seja,
. Defina o conjunto
$$S={,b - n a:,n\in\mathbb{Z}^+,}.
$$
Esse conjunto é não vazio e consiste só de inteiros positivos.
Esse conjunto é não vazio e consiste só de inteiros positivos.
Passo 3
Pelo Princípio da Boa Ordenação,
tem um menor elemento. Seja
$$m=\min S = b - k a,
$$
o que contradiz o fato de ser o menor elemento de
.
o que contradiz o fato de
Passo 4
Portanto nossa hipótese inicial estava errada: deve existir algum
tal que
.
Resposta
Concluímos que existe um inteiro positivo
satisfazendo
.