\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen, filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts,amsthm}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in \leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf On a Generalization of the Coin Exchange \\
\vskip .05in
Problem for Three Variables
}
\vskip 1cm
\large
Amitabha Tripathi \\
Department of Mathematics \\
Indian Institute of Technology \\
Hauz Khas \\
New Delhi - 110016 \\
India \\
\href{mailto:atripath@maths.iitd.ac.in}{\tt atripath@maths.iitd.ac.in} \\
\ \\
Sujith Vijay\footnote{This work was done while the second
author was at the Department of
Mathematics, Indian Institute of Technology, Delhi.}\\
Department of Mathematics \\
Rutgers University -- New Brunswick \\
Piscataway, NJ 08854 \\
USA  \\
\href{mailto:sujith@math.rutgers.edu}{\tt sujith@math.rutgers.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
Given relatively prime and positive integers $a_1,a_2,\ldots,a_k$,
let ${\Gamma}$ denote the set of nonnegative integers representable
by the form $a_1x_1+a_2x_2+\cdots+a_kx_k$, and let
${\Gamma}^{\star}$ denote the positive integers in ${\Gamma}$. Let
${\cal S}^{\star}(a_1,a_2,\ldots,a_k)$ denote the set of all
positive integers $n$ not in ${\Gamma}$ for which
$n+{\Gamma}^{\star}$ is contained in ${\Gamma}^{\star}$. The purpose
of this article is to determine an algorithm which can be used to
obtain the set ${\cal S}^{\star}$ in the three variable case. In
particular, we show that the set ${\cal S}^{\star}(a_1,a_2,a_3)$ has
at most two elements. We also obtain a formula for $g(a_1,a_2,a_3)$,
the largest integer not representable by the form
$a_1x_1+a_2x_2+a_3x_3$ with the $x_i$'s nonnegative integers.
\end{abstract}

\def\sm{\setminus}
\def\G{\Gamma}
\def\N{\mathbb N}
\def\S{\cal S}
\def\Liff{\Longleftrightarrow}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\lc{\lceil}
\def\rc{\rceil}
\def\pr{\prime}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}

\section{Introduction}

Given relatively prime and positive integers $a_1,a_2,\ldots,a_k$
and a positive integer $N$, consider the equation
\begin{equation}
a_1x_1+a_2x_2+\ldots+a_kx_k=N
\end{equation}
If each $x_i$ is a nonnegative integer, it is well known and easy to show that (1) has a
solution for all sufficiently large $N$. Hence, if we denote by ${\G}$ the set
$\{a_1x_1+a_2x_2+ \cdots+a_kx_k:x_j \ge 0\}$, then ${\G}^c:={\N} \sm {\G}$ is a finite set.
A natural problem that then arises is finding the largest $N$ such that (1) has no solution
in nonnegative integers, or in other words, of the largest element in ${\G}^c$. This problem
was first posed by Frobenius, who is believed to have been the first person to show that
$a_1a_2-a_1-a_2$ is the largest element in ${\G}^c$ in the two variable case. Frobenius was
also responsible in introducing the notation $g(a_1,a_2,\ldots,a_k)$ to denote the
{\em largest\/} number in ${\G}^c$. It is for this reason that the problem is also known as the
linear Diophantine problem of Frobenius.
The coin exchange problem derives its name from the
obvious interpretation of this problem in terms of exchanging coins
of arbitrary denomination
with an infinite supply of coins of certain fixed denominations.
The number of elements in
${\G}^c$, denoted by $n(a_1,a_2,\ldots,a_k)$, was later introduced by 
Sylvester \cite{Syl84},
and it was shown that $n(a_1,a_2)=\frac{1}{2}(a_1-1)(a_2-1)$.
Another related function is
$s(a_1,a_2,\ldots,a_k)$, which stands for the sum of elements in ${\G}^c$,
introduced by
Brown and Shiue \cite{BS93a}, wherein it was shown that
$s(a_1,a_2)=\frac{1}{12}(a_1-1)(a_2-1)(2a_1a_2-a_1-a_2-1)$. 

An explicit solution for the functions $g$ and $n$ in more than two variables has met with
little success over the years except in special cases. There is a simple formula for each of
these functions when the $a_j$'s are in {\em arithmetic progression\/}
\cite{Bat58,Gra73,Rob56,Tri94}, but results obtained in other cases usually give upper bounds,
deal with a special case or give an algorithmic solution
\cite{Bra42,BS54,BS62,Hof66,Joh60,Lev56,NW72,Rob57,Rod78,Rod79,SB78,Sel77}. 
We refer to the book
\cite{Ram05} where a complete account of the Frobenius problem can be found. 

A variation of the coin exchange problem which also leads to its generalization was introduced
by Tripathi \cite{Tri03}. We employ the notation used in \cite{Tri03}, and denote by
${\S}^{\star}(a_1,a_2,\ldots,a_k)$ the set of all $n \in {\G}^c$ such that
\[ n+{\G}^{\star} \subseteq {\G}^{\star}, \]
where ${\G}^{\star}={\G} \sm \{0\}$. Let $g^{\star}(a_1,a_2,\ldots,a_k)$ (respectively,
$n^{\star}(a_1,a_2,\ldots,a_k)$ and $s^{\star}(a_1,a_2,\ldots,a_k)$) denote the {\em least\/}
(respectively, the {\em number\/} and {\em sum\/} of) elements in ${\S}^{\star}$. It is
apparent that $g(a_1,a_2,\ldots,a_k)$ is the {\em largest\/} element in ${\S}^{\star}$, so
that
\[ g^{\star}(a_1,a_2,\ldots,a_k) \le g(a_1,a_2,\ldots,a_k), \]
and $n^{\star}(a_1,a_2,\ldots,a_k) \ge 1$, with equality if and only if $g^{\star}=g$. It is
interesting to note that this problem also arises from looking at the generators for the
derivation modules of certain monomial curves \cite{PS90,PS99} and also in comparing numerical
semigroups \cite{DM01}, and has been extensively studied in a more algebraic setting. 

For each $j$, $1 \le j \le a_1-1$, let $m_j$ denote the {\em least\/} number in ${\G}$
congruent to $j$ mod $a_1$. Then $m_j-a_1$ is the largest number in ${\G}^c$ congruent to $j$
mod $a_1$, and no number less than this in this residue class can be in ${\S}^{\star}$, for
they would differ by a multiple of $a_1$, an element in ${\G}^{\star}$. Therefore
\begin{equation}
{\S}^{\star}(a_1,a_2,\ldots,a_k) \subseteq \{m_j-a_1: 1 \le j \le a_1-1\}, \end{equation}
\begin{equation}
g^{\star}(a_1,a_2,\ldots,a_k) \le \left(\max_{1 \le j \le a_1-1}\: m_j\right) - a_1 =
g(a_1,a_2,\ldots,a_k),
\end{equation}
\begin{equation}
n^{\star}(a_1,a_2,\ldots,a_k) \le a_1-1,
\end{equation}
and
\begin{equation}
s^{\star}(a_1,a_2,\ldots,a_k) \le \sum_{j=1}^{a_1-1}\:m_j - a_1(a_1-1).
\end{equation}
More precisely,
\begin{equation}
m_j-a_1 \in {\S}^{\star}(a_1,a_2,\ldots,a_k) \Liff (m_j-a_1)+m_i \ge m_{j+i}
\end{equation}
for $1 \le i \le a_1-1$. The expression for $g(a_1,a_2,\ldots,a_k)$ in (3) is due to
Brauer \& Shockley \cite{BS62}. It is known \cite{BDF97} that if the semigroup ${\G}$ is
{\em symmetric\/} then ${\S}^{\star}=\big\{g(a_1,a_2,\ldots,a_k)\big\}$. 

The purpose of this article is to determine the set ${\S}^{\star}$ together with the related
functions in the three variable case. We shall use the variables $a,b,c$, and assume that
$a,b,c$ are coprime. 

Given $a,b,c$, we define the matrix ${\cal M}$ by
\[ {\cal M}:= \left( \begin{array}{ccc}
                      x_a & y_a & z_a \\
                      x_b & y_b & z_b \\
                      x_c & y_c & z_c \\
                     \end{array}
              \right), \]
where the entries are nonnegative integers. Let $x_a$, $y_b$, $z_c$ be the {\em least\/}
positive integers such that

\begin{equation}
ax_a=by_a+cz_a \;\;\mbox{for some integers}\;\; y_a \ge 0, z_a \ge 0;
\end{equation}
\begin{equation}
by_b=ax_b+cz_b \;\;\mbox{for some integers}\;\; x_b \ge 1, z_b \ge 0;
\end{equation}
\begin{equation}
cz_c=ax_c+by_c \;\;\mbox{for some integers}\;\; x_c \ge 1, y_c \ge 0.
\end{equation}

\noindent The matrix ${\cal M}$, with the entries at $x_b$ and $x_c$
allowed to be $0$, was used in \cite{Den03,Her70} in order to give
an expression for $g(a,b,c)$; see also [Proposition 4.7.1,
\cite{Ram05}]. For the sake of completeness, we state the
proposition
below. 

\begin{proposition}
Let $x_a,y_b,z_c$ be the least positive integers
such that there exist integers $x_b,x_c,y_a,y_c,z_a,z_b \ge 0$ with
\[ ax_a=by_a+cz_a, \quad by_b=ax_b+cz_b, \quad cz_c=ax_c+by_c. \]
\begin{itemize}
\item[{\rm (a)}]
If $x_b,x_c,y_a,y_c,z_a,z_b$ are all greater than $0$, then
\[ x_a=x_b+x_c, \quad y_b=y_a+y_c, \quad z_c=z_a+z_b. \]
\item[{\rm (b)}]
\begin{itemize}
\item[{\rm (i)}]
If $x_b=0$ or $x_c=0$, then $by_b=cz_c$ and $ax_a=by_a+cz_a$ with $y_a,z_a>0$.
\item[{\rm (ii)}]
If $y_a=0$ or $y_c=0$, then $ax_a=cz_c$ and $by_b=ax_b+cz_b$ with $x_b,z_b>0$.
\item[{\rm (iii)}]
If $z_a=0$ or $z_c=0$, then $ax_a=by_b$ and $cz_c=ax_c+by_c$ with $x_c,y_c>0$.
\end{itemize}
\end{itemize}
\end{proposition}

\noindent We now state and prove our main result where we determine the set
${\S}^{\star}(a,b,c)$ in terms of the entries of the matrix ${\cal M}$. 

\begin{theorem}
Let $a<b<c$ with $\gcd(a,b,c)=1$. With the entries of the matrix
${\cal M}$ as defined in {\rm (7)}, {\rm (8)}, {\rm (9)},
\[ {\S}^{\star}(a,b,c) = \left\{ \begin{array}{l}
   \Big\{b(y_b-1)+c(z_a-1)-a,b(y_a-1)+c(z_c-1)-a\Big\}, \\
   \mbox{if}\;\; y_a,z_a \ge 1; \\[5pt]
   \Big\{b(y_b-1)+c(z_a-1)-a\Big\}, \;\;\mbox{if}\;\; y_a=0; \\[5pt]
   \Big\{b(y_a-1)+c(z_c-1)-a\Big\}, \;\;\mbox{if}\;\; z_a=0.
                              \end{array}
                      \right. \]
\end{theorem}

\begin{proof}
For any integer $j$, with $1 \le j \le a-1$, let
$m_j=by+cz$, where $y,z$ are nonnegative integers. Recall that $m_j$
is the smallest integer in ${\G}$ congruent to $j$ mod $a$. Now $y
\le y_b-1$, since otherwise $b(y-y_b)+c(z+z_b) \equiv j$ mod $a$
and, by equation (8), it
is less than $m_j$. Similarly, by using equation (9), we have $z \le z_c-1$. 

If $y_a>y_b$, then $a(x_a-x_b)=b(y_a-y_b)+c(z_a+z_b)>0$, contradicting the minimality of
$x_a$. Thus, $y_a \le y_b$, and similarly $z_a \le z_c$. Note that these inequalities follow
immediately from the above Proposition, and that the former inequality is strict if $z_a>0$
and the latter if $y_a>0$. 

If $y \ge y_a$ and $z \ge z_a$, then $m_j-(by_a+cz_a)$ would be a positive integer less than
$m_j$ and congruent to $j$ mod $a$. Therefore, {\em at least\/} one of
\begin{equation}
0 \le y \le y_a-1 \quad \mbox{and} \quad 0 \le z \le z_c-1
\end{equation}
or
\begin{equation}
0 \le y \le y_b-1 \quad \mbox{and} \quad 0 \le z \le z_a-1
\end{equation}
holds. 

\noindent {\sc Case I:} $(y_a,z_a \ge 1)$ We claim that $m_i^{\star}:=b(y_a-1)+c(z_c-1)=m_i$
and $m_j^{\star}:=b(y_b-1)+c(z_a-1)=m_j$, with $y_a<y_b$ and $z_a<z_c$. If
$m_i^{\star}>m_i=by+cz$, then $b(y_a-y-1)+c(z_c-z-1)=\big(b(y_a-1)+c(z_c-1)\big)-(by+cz)
\in a{\N}$. Since $0 \le z \le z_c-1$, we have $0 \le z_c-z-1<z_c$, so that from the
definition of $z_c$ we conclude $y_a-y-1 \ge 1$. Hence, $b(y_a-y-1)+c(z_c-z-1)=(by_a+cz_a)+ma$
for some $m \in {\N}$. But then $ma+b(y+1)=c(z_c-z_a-z-1)$, which contradicts the minimality
of $z_c$. This contradiction proves that $m_i^{\star}=m_i$, and we have $y_a<y_b$ since $z_a>0$
by an earlier argument in this proof. A similar argument shows that $m_j^{\star}=m_j$, with
$z_a<z_c$. 

We now claim that if $m_k=by+cz \ne b(y_a-1)+c(z_c-1)$, $b(y_b-1)+c(z_a-1)$, then
$m_k-a \notin {\S}^{\star}$. To prove this, we exhibit $m^{\pr}_k \in {\G}^{\star}$ such that
$(m_k-a)+m^{\pr}_k \notin {\G}^{\star}$. If $0 \le y \le y_a-1$ and $0 \le z \le z_c-1$, set
$m^{\pr}_k:=b(y_a-y-1)+c(z_c-z-1)$; and if $0 \le y \le y_b-1$ and $0 \le z \le z_a-1$, set
$m^{\pr}_k:=b(y_b-y-1)+c(z_a-z-1)$. In the first case, $(m_k-a)+m^{\pr}_k$ equals
$m_i^{\star}-a$, and in the second case, it equals $m_j^{\star}-a$. So, in both cases,
$(m_k-a)+m^{\pr}_k \notin {\G}^{\star}$. This proves that
${\S}^{\star} \subseteq \big\{b(y_a-1)+c(z_c-1)-a,b(y_b-1)+c(z_a-1)-a\big\}$. 

To complete the first case of our proof, it remains to show that each of the two numbers
$m_i^{\star}-a$, $m_j^{\star}-a$ belong to ${\S}^{\star}$. We show this for $m_i^{\star}-a$;
a similar argument shows that $m_j^{\star}-a \in {\S}^{\star}$. Consider
$N=\big(b(y_a-1)+c(z_c-1)-a\big)+n$, where $n=ax_0+by_0+cz_0$ with $x_0,y_0,z_0$ nonnegative,
not all zero. Observe that $y_a-1 \ge 0$ by assumption, and that $z_c-1 \ge 0$ by definition.
If $x_0 \ge 1$, then it is clear that $N \in {\G}^{\star}$. If $y_0 \ge 1$, then $N=a(x_a-1+x_0)+b(y_0-1)+c(z_c-z_a-1+z_0) \in {\G}^{\star}$. If $z_0 \ge 1$, then $N=a(x_c-1+x_0)+b(y_a+y_c-1+y_0)+c(z_0-1) \in {\G}^{\star}$.
This proves $m_i^{\star}-a \in {\S}^{\star}$, and completes Case I. 

\noindent {\sc Case II:} $(y_a=0$ or $z_a=0)$ If $z_a=0$, equation
(10) must hold. We show that $m_i^{\star}-a=b(y_a-1)+c(z_c-1)-a$ is
the only element in ${\S}^{\star}$ in this case. Indeed, the
argument in Case I shows that $m_i^{\star}=m_i$, that $m_i^{\star}-a
\in {\S}^{\star}$, and that ${\S}^{\star}$ has {\em at most\/} two
elements. Thus, it only remains to show that
$m_j^{\star}-a=b(y_b-1)-c-a \notin {\S}^{\star}$. In fact,
$m_j^{\star}=b(y_b-1)-c=by+cz=m_j$ implies $b(y_b-y-1)=am+c(z+1)$
for some $m \in {\N}$. Since this contradicts the minimality of
$y_b$, $m_j^{\star}>m_j$ and so $m_j^{\star}-a=b(y_b-1)-c-a \notin
{\S}^{\star}$. In case $y_a=0$, equation (11) must hold, and a
similar argument will show that $b(y_b-1)+c(z_a-1)-a$ is the only
element in ${\S}^{\star}$ in this case. This completes the proof of
our theorem.
\end{proof}

\begin{corollary}
Let $a<b<c$ with $\gcd(a,b,c)=1$. With the notation of Theorem~1,
\[ g(a,b,c) = \left\{ \begin{array}{l}
              \max\big\{b(y_b-1)+c(z_a-1)-a,b(y_a-1)+c(z_c-1)-a\big\}, \\
              \mbox{if}\;\; y_a,z_a \ge 1; \\[5pt]
              b(y_b-1)+c(z_a-1)-a, \;\;\mbox{if}\;\; y_a=0; \\[5pt]
              b(y_a-1)+c(z_c-1)-a, \;\;\mbox{if}\;\; z_a=0.
                      \end{array}
              \right.
\]
\end{corollary}

\begin{remark}
{\rm
A variation of Corollary 1 is due to Johnson \cite{Joh60}. In
\cite{Joh60}, the variables $a,b,c$ are assumed to be {\it pairwise
coprime\/}, so that $x_b,y_b,z_b$ and $x_c,y_c,z_c$ are defined
analogously to $x_a,y_a,z_a$, and therefore taken as nonnegative. In
the case of Theorem 1 we only assume that $a,b,c$ are coprime, and
need the positivity of $x_b,y_b,z_b$ and $x_c,y_c,z_c$. If we assume
that $a,b,c$ are pairwise coprime, $y_a>0$ and $z_a>0$, so that
only the first case in Theorem 1 holds; see also [Theorem 2.2.3, \cite{Ram05}]: \\[5pt]
Let $a<b<c$ with $a,b,c$ pairwise coprime.  With the notation of Theorem 1,
\[ g(a,b,c) = \max\big\{b(y_b-1)+c(z_a-1)-a,b(y_a-1)+c(z_c-1)-a\big\} \]
}
\end{remark}

\begin{corollary}
Let $a<b<c$ be such that $\gcd(a,b,c)=1$ and $a|(b+c)$. Then
\[ {\S}^{\star}(a,b,c) = \left\{b\left\lf \frac{ac}{b+c} \right\rf -a,
   c\left\lf \frac{ab}{b+c} \right\rf -a\right\}.
\]
\end{corollary}

\begin{proof}
Observe that $a|(bx-cy)$ if and only if $a|(x+y)$ since $a|(b+c)$ and $\gcd(a,b,c)=1$ forces
$\gcd(a,b)=1=\gcd(a,c)$. If we write $y=ma-x$, then $bx>cy$ reduces to $x>\frac{mac}{b+c}$.
The least such $x$ is clearly $y_b=\lc\frac{ac}{b+c}\rc$. Similarly,
$z_c=\lc\frac{ab}{b+c}\rc$, and it is easy to see that $(y_a,z_a)=(1,1)$. Observe that $b+c$
cannot divide either $ab$ or $ac$ since $\gcd(b,c)=1$. Therefore, $y_b-1=\lf\frac{ac}{b+c}\rf$
and $z_c-1=\lf\frac{ab}{b+c}\rf$, and the result now follows from Theorem 1.
\end{proof}

\begin{remark}
{\rm
Corollary 2 implies that
\[ g(a,b,c) = \max\left\{b\left\lf \frac{ac}{b+c} \right\rf -a,
   c\left\lf \frac{ab}{b+c} \right\rf-a \right\}
\]
when $a|(b+c)$. This result is well-known and due to Brauer \&
Shockley; see \cite{BS62,Tri89}.
}
\end{remark}

\begin{corollary}
If $\gcd(a,d)=1$, then
\[ {\S}^{\star}(a,a+d,a+2d) = \left\{ \begin{array}{l}
   \left\{\frac{1}{2}a(a-2)+d(a-1)\right\}, \;\;\mbox{if}\;\; a \;\;
   \mbox{is even}; \\[5pt]
   \left\{\frac{1}{2}a(a-3)+d(a-1),\frac{1}{2}a(a-3)+d(a-2)\right\}, \\
   \mbox{if}\;\; a \;\;\mbox{is odd}.
                                    \end{array}
                            \right.
\]
\end{corollary}

\begin{proof}
Observe that $a|\{(a+d)x+(a+2d)y\}$ if and only if $a|(x+2y)$. Therefore, $(y_a,z_a)$ equals
$(0,\frac{1}{2}a)$ if $a$ is {\em even\/} and $(1,\frac{1}{2}(a-1))$ if $a$ is {\em odd\/}.
If $a$ is {\em even\/}, it is easy to see that $y_b=2$, and the only element in the set is
$(a+d)+\frac{1}{2}(a+2d)(a-2)-a=d(a-1)+\frac{1}{2}a(a-2)$. If $a$ is {\em odd\/}, the required
conditions to determine $z_c$ reduce to minimizing $y$ such that $(a+2d)y>(a+d)x$ and
$2y \equiv x$ mod $a$. This gives $z_c=\frac{1}{2}(a+1)$ and the set thus consists of the two
elements $(a+d)+\frac{1}{2}(a+2d)(a-3)-a=d(a-2)+\frac{1}{2}a(a-3)$ and
$\frac{1}{2}(a+2d)(a-1)-a=d(a-1)+\frac{1}{2}a(a-3)$. This completes the proof.
\end{proof}

\begin{remark}
{\rm
Corollary 3 is the three variable version of the main result of
\cite{Tri03}. Determination of $g(a,a+d,a+2d)$ is an immediate
consequence of Corollary 3 and is also a special case of a more
general result when there is no restriction on the number of
variables in arithmetic progression, and is due to Roberts; see
\cite{Bat58,Rob56,Tri94}. Corollary 3 implies
\[ g(a,a+d,a+2d) = a\left\lf\frac{a-2}{2}\right\rf + d(a-1). \]
}
\end{remark}

A description of the set ${\S}^{\star}(a,b,c)$, and hence of the several related functions,
including $g(a,b,c)$ and $g^{\star}(a,b,c)$, involves at least a partial knowledge of the
matrix ${\cal M}$. The description of ${\cal M}$ is a known result due to Morales \cite{Mor87},
and is described in [Claim 8.4.3, \cite{Ram05}]. 

\bigskip

\section{Acknowledgement}

The authors wish to thank the referee for several suggestions and
references that have helped improve an earlier version of their
paper.

\begin{thebibliography}{99}

\bibitem{BDF97}
V. Barucci, D. E. Dobbs and M. Fontana,
Maximality properties of one-dimensional analytically
irreducible local domains, {\em Memoires Amer. Math. Soc.\/},
{\bf 125/598}, 1997.

\bibitem{Bat58}
P. T. Bateman, Remark on a recent note on linear forms, {\em Amer.
Math. Monthly\/}, {\bf 65} (1958), 517--518.

\bibitem{Bra42}
A. Brauer, On a problem of partitions -- I, {\em Amer. J. Math.\/},
{\bf 64} (1942), 299--312.

\bibitem{BS54}
A. Brauer and B. M. Seelbinder, On a problem of partitions -- II,
{\em Amer. J. Math.\/}, {\bf 76} (1954), 343--346.

\bibitem{BS62}
A. Brauer and J. E. Shockley, On a problem of Frobenius, {\em J.
reine Angew. Math.\/}, {\bf 211} (1962), 215--220.

\bibitem{BS93a}
T. C. Brown and P. J. Shiue, A remark related to the Frobenius
problem, {\em Fibonacci Quart.\/}, {\bf 31} (1993), 31--36.

\bibitem{Den03}
G. Denham, Short generating functions for some semigroup algebras,
{\em The Electronic Journal of Combinatorics\/}, {\bf 10}, Research
paper 36 (2003), 7 pages.

\bibitem{DM01}
D. E. Dobbs and G. L. Matthews, On comparing two chains of numerical
semigroups and detecting Arf semigroups, {\em Semigroup Forum\/},
{\bf 63}, \#2 (2001), 237--246.

\bibitem{Gra73}
D. D. Grant, On linear forms whose coefficients are in arithmetic
progression, {\em Israel J. Math.\/}, {\bf 15} (1973), 204--209.

\bibitem{Her70}
J. Herzog, Generators and relations of abelian semigroups and
semigroup rings, {\em Manuscripta Math.\/}, {\bf 3} (1970),
175--193.

\bibitem{Hof66}
G. R. Hofmeister, Zu einem Problem von Frobenius, {\em Norske
Videnskabers Selskabs Skrifter\/}, {\bf 5} (1966), 1--37.

\bibitem{Joh60}
S. M. Johnson, A linear diophantine problem, {\em Canad. J. Math.\/}
{\bf 12} (1960), 390--398.

\bibitem{Lev56}
R. J. Levit, A minimum solution for a diophantine equation, {\em
Amer. Math. Monthly\/}, {\bf 63} (1956), 646--651.

\bibitem{Mor87}
M. Morales, Syzygies of monomial curves and a linear diophantine problem of Frobenius,
{\em Internal Report, Max Planck Institut f\"{u}r Mathematik, Bonn\/}, 1987.

\bibitem{NW72}
A. Nijenhuis and H. S. Wilf, Representations of integers by linear
forms in non negative integers, {\em J. Number Theory\/}, {\bf 4}
(1972), 98--106.

\bibitem{PS90}
D. P. Patil and Balwant Singh, Generators for the derivation modules
and the relation ideals of certain curves, {\em Manuscripta
Math.\/}, {\bf 68} (1990), 327--335.

\bibitem{PS99}
D. P. Patil and I. Sengupta, Minimal set of generators for the
derivation modules of certain monomial curves, {\em Comm.
Algebra\/}, {\bf 27} (1999), 5619--5631.

\bibitem{Ram05}
J. L. Ram\'{i}rez Alfons\'{i}n, The Diophantine Frobenius Problem, {\em Oxford Lecture Series
in Mathematics and its Applications\/}, {\bf 30}, Oxford Univerity Press, 2005.

\bibitem{Rob56}
J. B. Roberts, Note on linear forms, {\em Proc. Amer. Math. Soc.\/},
{\bf 7} (1956), 465--469.

\bibitem{Rob57}
J. B. Roberts, On a diophantine problem, {\em Canad. J. Math.\/},
{\bf 9} (1957), 219--222.

\bibitem{Rod78}
\"{O}. J. R{\"{o}}dseth, On a linear diophantine problem of
{F}robenius, {\em J. reine Angew. Math.\/}, {\bf 301} (1978),
171--178.

\bibitem{Rod79}
\"{O}. J. R{\"{o}}dseth, On a linear diophantine problem of
Frobenius II, {\em J. reine Angew. Math.\/}, {\bf 307/308} (1979),
431--440.

\bibitem{SB78}
E. S. Selmer and \"{O}. Beyer, On the linear diophantine problem of
Frobenius in three variables, {\em J. reine Angew. Math.\/}, {\bf
301} (1978), 161--170.

\bibitem{Sel77}
E. S. Selmer, On the linear diophantine problem of Frobenius, {\em
J. reine Angew. Math.\/}, {\bf 293/294} (1977), 1--17.

\bibitem{Syl84}
J. J. Sylvester, Mathematical questions with their solutions, {\em
The Educational Times\/}, {\bf 41} (1884), 21.

\bibitem{Tri89}
A. Tripathi, Topics in Number Theory, Ph. D. Thesis, Department of Mathematics, State University
of New York, Buffalo, 1989.

\bibitem{Tri94}
A. Tripathi, The coin exchange problem for arithmetic progressions,
{\em Amer. Math. Monthly\/}, {\bf 101}, (1994), 779--781.

\bibitem{Tri03}
A. Tripathi, On a variation of the coin exchange problem for
arithmetic progressions, {\em Integers\/}, {\bf 3}, \#A01 (2003),
1--5.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11D04.

\noindent \emph{Keywords: } coin exchange problem, linear
diophantine problem of Frobenius.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 20 2005;
revised version received September 12 2006.
Published in {\it Journal of Integer Sequences}, September 12 2006.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


\end{document}

.