Problem Frobeniusa: Dane są 2 liczby względnie pierwsze,
i
Wtedy dla każdej liczby naturalnej
istnieją nieujemne liczby całkowite
i
takie, że:
Dowód przeprowadza się przez indukcję względem
Dowód alternatywny
Weźmy taką parę liczb całkowitych
która spełnia równanie
Taka para istnieje, można ją znaleźć rozszerzonym algorytmem Euklidesa. Załóżmy bez straty ogólności, że
i
(jeśli oba są dodatnie, to znaleźliśmy już rozwiązanie, a oba ujemne być nie mogą). Zauważmy, że wszystkie pary
także spełniają to równanie (istotnie,
). Weźmy takie
że
jest już dodatnie, ale
jeszcze nie (a więc bierzemy najmniejsze dodatnie
). Wtedy
Weźmy też
Gdyby
było ujemne, to znaczyłoby, że
(bo
jeszcze było dodatnie). Ale wtedy mamy, że
co leży w sprzeczności z założeniem, że
Zatem
musi być dodatnie i para
jest rozwiązaniem równania
w liczbach naturalnych.