Let $g(a_1,...,a_n)$ be Frobenius number of $a_1,....a_n$ where $gcd(a_1,....a_n) = 1$ and $\Gamma(a_1,...,a_n) = \{x_1a_1+...+x_na_n : x_i \geq 0 \forall i\}$. Then Frobenius number,$g(a_1,...,a_n)$,is the largest number such that $g(a_1,...,a_n) \notin \Gamma(a_1,...,a_n)$

According to A. Tripathi's paper on Frobenius on three variables,[Lemma 1] He shows that

if $a,b$ are coprime such that $a<b$ and $c = g(a,b)$

$$g(a,b,c) = c - a$$

I try to understand and I have written the proof of my version as follow:

Note that, if $n < c = g(a,b)$, then $n \in \Gamma(a,b,c)$ if and only if $n \in \Gamma(a,b).$

Since $(c-a) < c$ and $(c-a) \notin \Gamma(a,b)$, $(c-a) \notin \Gamma(a,b,c)$. It leave to show that $c-a$ is the largest integer not in $\Gamma(a,b,c)$

Ok, there is a Theorem that $g(a,b,c) = bx_0 + cy_0 - a$ for some $x_0,y_0\geq 0$. We will show that $x_0 = 0$ and $y_0 = 1$.

if $x_0,y_0\geq 1$ $$bx_0 + cy_0 - a > (b-a) + c > c = g(a,b),$$

hence $bx_0 + cy_0 - a \in \Gamma(a,b) \subset \Gamma(a,b,c)$ contradiction. Since $g(a,b,c) \notin \Gamma(a,b,c)$

if $y_0 \geq 2$ and $x_0 = 0$, $$cy_0 - a > c + (c - a) > c = g(a,b),$$

hence $cy_0 - a \in \Gamma(a,b) \subset \Gamma(a,b,c)$

It leaves to show where $x_0 \geq 1$ and $y_0 = 0$ which I have been stuck for a while now for completing the proof.

Actually, A.Tripathi's proof uses another theorem (Theorem 1 in his paper) to claim but I do not get his argument also if someone could give me some explanations I'd be glad for your help.


1 Answer 1


The last case require the face that $g(a,b) = ab - a - b$

suppose that $g(a,b,c) = bx_0 + cy_0 - a \geq c - a$ where $x_0\geq 1$ and $y_0 = 0$ then $g(a,b,c) = bx_0 - a \geq c - a$. So $bx_0 \geq c = g(a,b) =ab-a-b$

hence $x_0 \geq a -\frac{a}{b} - 1$. Since $x_0$ must be integer greater that $a -\frac{a}{b} - 1$, $x_0 \geq a-1$

And then, $bx_0 \geq ba - b = c + a$.

So, $bx_0 -a \geq c$.

But we assume that $g(a,b,c) = bx_0 - a$ and by above give that $g(a,b,c) \geq c$ but If $g(a,b,c) = c$ then $g(a,b,c)\in \Gamma(a,b,c)$ and if $g(a,b,c) > c$ $g(a,b,c)\in \Gamma(a,b) \subset \Gamma(a,b,c)$ contradiction.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .