[obm-l] Inteiros da forma ax + by

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

Dados inteiros positivos a, b com mdc(a,b) = 1, o problema é encontrar todos os inteiros positivos que podem ser representados na forma ax + by, onde x e y são inteiros não-negativos.

 

Nesse caso:

1) ab - a - b não pode ser representado;

2) todo inteiro maior do que ab - a - b pode ser representado;

3) exatamente metade dos inteiros no intervalo [0,ab - a - b] pode ser representada.

 

Tudo isso está provado em:

http://www.cut-the-knot.org/blue/Byzantine.shtml

 

[]s,

Claudio.