Olimpíadas ⇒ (África do Sul - 94) Equações diofantinas lineares

[Auto Excluído (ID: 23699)]

Qual é o maior inteiro positivo que não pode ser expresso na forma 5x+7y, com x e y inteiros positivos?

Resposta

---

35

[Auto Excluído (ID: 24633)]

Considere a equação diofantina (em inteiros [tex3]x,y,t[/tex3]) genérica [tex3]5 x + 7y = t~(*).[/tex3] Uma solução trivial é [tex3](x= 3t; ~y=-2t)[/tex3] e logo todas as soluções são da forma [tex3](x=3t -7k;~ y= -2t +5k)[/tex3] onde [tex3]k[/tex3] representa um inteiro qualquer.

Queremos saber o maior valor de [tex3]t[/tex3] para o qual [tex3](*)[/tex3] não admite solução inteira positiva; ou seja o sistema [tex3]\begin{cases} 3t -7k >0 \\ -2t + 5k >0 \end{cases}[/tex3] não possui solução.
[tex3]\begin{cases} 3t - 7k >0 \\ -2t + 5k >0 \end{cases} \iff \dfrac{2t}{5} < k < \dfrac{3t}{7} [/tex3]

Então queremos saber o maior inteiro positivo [tex3]t[/tex3] tal que não existam inteiros entre [tex3]\dfrac{2t}{5}[/tex3] e [tex3]\dfrac{3t}{7}.[/tex3]
A condição necessária (mas não suficiente) para que isso ocorra é [tex3]\dfrac{3t}{7} - \dfrac{2t}{5} \le 1 \iff \dfrac{t}{35} \le 1 \iff t \le 35.[/tex3] Agora basta verificar se [tex3]t = 35[/tex3] está de acordo com o que queremos; de fato não existe [tex3]k[/tex3] inteiro satisfazendo [tex3]14 = \dfrac{2\cdot 35}{5} < k < \dfrac{3\cdot 35}{7} = 15.[/tex3]

Portanto, o número requerido é [tex3]35.[/tex3]