Problem Frobeniusa

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

Dowód przeprowadza się przez indukcję względem ${\displaystyle c.}$

Dowód alternatywny

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

Zobacz też

• Georg Ferdinand Frobenius (matematyk niemiecki)