Problem Frobeniusa

Problem Frobeniusa: Dane są 2 liczby względnie pierwsze, $a$ i $b.$ Wtedy dla każdej liczby naturalnej $c⩾(a-1)(b-1)$ istnieją nieujemne liczby całkowite $x$ i $y$ takie, że: $ax+by=c.$

Dowód przeprowadza się przez indukcję względem $c.$

Dowód alternatywny

Weźmy taką parę liczb całkowitych $x_0,y_0,$ która spełnia równanie $ax+by=c.$ Taka para istnieje, można ją znaleźć rozszerzonym algorytmem Euklidesa. Załóżmy bez straty ogólności, że $x_0<0$ i $y_0>0$ (jeśli oba są dodatnie, to znaleźliśmy już rozwiązanie, a oba ujemne być nie mogą). Zauważmy, że wszystkie pary $x_0+bn,y_0-an$ także spełniają to równanie (istotnie, $a(x_0+nb)+b(y_0-na)=a{x}_0+nba+b{y}_0-nba=c$). Weźmy takie $x=x_0+nb,$ że $x$ jest już dodatnie, ale $x-b$ jeszcze nie (a więc bierzemy najmniejsze dodatnie $x_0+nb$). Wtedy $x\in <0,b-1>.$ Weźmy też $y=y_0-na.$ Gdyby $y$ było ujemne, to znaczyłoby, że $y\in <-a,-1>$ (bo $y+a$ jeszcze było dodatnie). Ale wtedy mamy, że $ax+by⩽a(b-1)+b(-1)=ab-a-b=(a-1)(b-1)-1,$ co leży w sprzeczności z założeniem, że $ax+by=c⩾(a-1)(b-1).$ Zatem $y$ musi być dodatnie i para $x,y$ jest rozwiązaniem równania $ax+by=c$ w liczbach naturalnych.

Zobacz też

• Georg Ferdinand Frobenius (matematyk niemiecki)