\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{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\DeclareMathOperator{\lcm}{lcm}


\def\mod{\!\pmod}
\def\a{\alpha}
\def\b{\beta}
\def\g{{\rm g}}
\def\m{\bf m}
\def\n{{\rm n}}
\def\ov{\overline}
\def\s{{\rm s}}
\def\C{\mathscr C}
\def\G{\Gamma}
\def\S{\mathcal S}
\def\Z{\mathbb Z}
\def\ts{\textstyle}
\def\sig{\sigma}
\def\es{\emptyset}
\def\imp{\rightarrow}
\def\pr{\prime}
\def\sm{\setminus}

\begin{document}

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

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\begin{center}
\vskip 1cm{\LARGE\bf 
On a Special Case of the Frobenius Problem
}
\vskip 1cm
\large
Amitabha Tripathi \\
Department of Mathematics \\
Indian Institute of Technology \\
Hauz Khas \\
New Delhi -- 110016 \\
India \\
\href{atripath@maths.iitd.ac.in}{\tt atripath@maths.iitd.ac.in} \\
\end{center}

\vskip .2 in

\begin{abstract}
For any set of positive and relatively prime integers $A$, the set of
positive integers that are not representable as a nonnegative integral
linear combination of elements of $A$ is always a non-empty finite set.
Thus we may define ${\g}(A)$, ${\n}(A)$, ${\s}(A)$ to denote the
largest integer in, the number of integers in, and the sum of integers
in this finite set, respectively. We determine ${\g}(A)$, ${\n}(A)$,
${\s}(A)$ when $A=\{a,b,c\}$ with $a \mid \lcm(b,c)$. A particular case
of this is when $A=\{k\ell,\ell m,mk\}$, with $k,\ell,m$ pairwise
coprime. We also solve a related problem when $a \mid \lcm(b,c)$,
thereby providing another proof of the formula for ${\g}(A)$.
\end{abstract}


\section{Introduction}
\label{section1}

The following problem was the third of the six problems in the Twenty-Fourth International Mathematical Olympiad, held in Paris on July 6--7, 1983: 
\begin{quote}
Let $a,b,c$ be positive integers satisfying $(a,b)=(b,c)=(c,a)=1$. Show that $2abc-ab-bc-ca$ is the largest integer not representable as 
\[ xbc + yca + zab \]
with nonnegative integers $x,y,z$. 
\end{quote}

This is a special case of the well-known linear Diophantine problem, posed by Sylvester \cite{Syl84}, but known as the {\it Frobenius problem}, after G. Frobenius who was largely instrumental in popularizing the problem. Consider a finite set $A=\{a_1,\ldots,a_k\}$ of positive integers with $\gcd\,A:=\gcd(a_1,\ldots,a_k)=1$. Let $\G(A):=\{a_1x_1+\cdots+a_kx_k: x_i \in {\Z}_{\ge 0}\}$. Then ${\G}^c(A):={\Z}_{\ge 0} \sm \G(A)$ can be shown to be a {\it finite\/} set, and this allows us to define the {\it Frobenius number} ${\g}(A)$ 
and the {\it Sylvester number} ${\n}(A)$: 
\[ {\g}(A):= \max {\G}^c(A), \quad {\n}(A):= \big| {\G}^c(A) \big|. \]
Here, and elsewhere, $|X|$ denotes the cardinality of the finite set $X$. The 
Frobenius problem is to determine ${\g}(A)$ and ${\n}(A)$ in the general case.  

For $A=\{a,b\}$, $\gcd(a,b)=1$, Sylvester \cite{Syl84} showed 
\[ {\g}(a,b) = ab-a-b, \quad {\n}(a,b) = \frac{1}{2}(a-1)(b-1). \]
Exact values for ${\g}(A)$ have been known only for few cases when $|A|>2$ -- in some cases when the elements of $A$ satisfy a specific condition. For instance, ${\g}(k\ell,\ell m,mk)=2k\ell m-k\ell-\ell m-mk$ whenever $\gcd(k,\ell)=\gcd(\ell,m)=\gcd(m,k)=1$. On the other hand, bounds and algorithms to compute ${\g}(A)$, especially in the case $|A|=3$, have been a major source of research. Corresponding results for ${\n}(A)$ have been much rarer, even in special cases; refer to \cite{Ram05}. 
 
Brown and Shiue \cite{BS93} introduced the related problem of determining the function 
\[ {\s}(A):= \sum_{n \in {\G}^c(A)} n, \]
and found 
\[ {\s}(a,b) = \frac{1}{12}(a-1)(b-1)(2ab-a-b-1) \]
when $\gcd(a,b)=1$; also see \cite{Tri08}.  

Tripathi \cite{Tri03} introduced the following variation on the Frobenius 
problem. The set ${\G}(A)$ is closed under addition, and so $n+{\G}(A) \subseteq {\G}(A)$ whenever $n \in {\G}(A)$. It is conceivable that $n \in {\G}^c(A)$ satisfy a slightly modified condition, replacing ${\G}(A)$ by ${\G}(A) \sm \{0\}$. In fact, ${\g}(A)$ is clearly the largest number satisfying such a condition. Thus we study the set given by 
\[ {\S}^{\star}(A):= \big\{n \,\in\, {\G}^c(A): n+{\G}^{\star}(A) \subset {\G}^{\star}(A) \big\}, \]
where ${\G}^{\star}(A)={\G}(A) \sm \{0\}$. 

In this note, we consider the set $A=\{a,b,c\}$ with $\gcd(a,b)=1$, where $a$ divides $\lcm(b,c)$. Observe that the IMO problem introduced at the beginning of this article, involving triples $a=k\ell$, $b=\ell m$, $c=mk$ with $k,\ell,m$ pairwise coprime, satisfies the condition $a$ divides $\lcm(b,c)$. We determine ${\g}(A)$, ${\n}(A)$, ${\s}(A)$, and the set ${\S}^{\star}(A)$, giving more than one proof for each of the results for ${\g}(A)$ and ${\n}(A)$. We list all results that we will base our study on in Section~\ref{prelim}, and prove our main results, listed as Theorem \ref{main} and Corollary \ref{main_corollary}, 
in Section~\ref{section3}. The results of Corollary \ref{main_corollary} follow directly from those of Theorem \ref{main}, and the results for ${\g}(A)$, ${\n}(A)$ and ${\S}^{\star}(A)$ are also special cases of \cite[Theorem 1, 2]{Tri06}. The proofs of the results in Corollary \ref{main_corollary} are omitted. 

\begin{theorem} \label{main}
Let $A=\{a,b,c\}$, where $\gcd(a,b,c)=1$ and $a \mid \lcm(b,c)$. Then 
\begin{itemize}
\item[{\rm (a)}] 
\[ {\g}(a,b,c) = \lcm(a,b) + \lcm(a,c) - (a+b+c). \]
\item[{\rm (b)}] 
\[ {\n}(a,b,c) = \frac{1}{2}\Big( \lcm(a,b) + \lcm(a,c) - (a+b+c) + 1\Big). \]
\item[{\rm (c)}] 
\begin{eqnarray*}
{\s}(a,b,c) & = & \frac{1}{12} \Big( a^2 + b^2 + c^2 + 3abc + 3(ab+bc+ca) - 3(a+b+c)\big(\lcm(a,b)+\lcm(a,c)\big)  \\
& & + 2\big( \big(\lcm(a,b)\big)^2+\big(\lcm(a,c)\big)^2 \big) - 1 \Big). 
\end{eqnarray*}
\item[{\rm (d)}] 
\[ {\S}^{\star}(\{a,b,c\}) = \Big\{\lcm(a,b) + \lcm(a,c) - (a+b+c)\Big\}. \]
\end{itemize}
\end{theorem}

\begin{corollary} \label{main_corollary}
Let $k,\ell,m$ be pairwise coprime, positive integers. If ${\sig}_1=k+\ell+m$, ${\sig}_2=k\ell+\ell m+mk$, and ${\sig}_3=k\ell m$, then 
\begin{eqnarray*}
{\g}(k\ell,\ell m,mk) = 2{\sig}_3 - {\sig}_2, \quad {\n}(k\ell,\ell m,mk) = \frac{1}{2}\big(2{\sig}_3 - {\sig}_2 + 1\big), \\
{\s}(k\ell,\ell m,mk) = \frac{1}{12} \big( 7{\sig}_3^2 - 6{\sig}_2\, {\sig}_3 + {\sig}_2^2 + {\sig}_1\,{\sig}_3 - 1 \big), \quad 
{\S}^{\star}\big(\{k\ell,\ell m,mk\}\big) = \big\{2{\sig}_3 - {\sig}_2\big\}.  
\end{eqnarray*}
\end{corollary}

\section{Preliminary results} 
\label{prelim}

Suppose $A$ is any set of positive integers with $\gcd A=1$, and let $a \in A$. For each residue class ${\bf C}$ modulo $a$, let ${\m}_{\bf C}$ denote the least integer in ${\G}(A) \cap {\bf C}$. It is well known that the functions ${\g}$, ${\n}$ and ${\s}$ are easily determined from the values of ${\m}_{\bf C}$. The following result, part (i) of which is due to Brauer and Shockley \cite{BS62}, part (ii) to Selmer \cite{Sel77}, and part (iii) to Tripathi \cite{Tri08}, is often a key step in this determination. 

\begin{proposition} {\bf \cite{BS62,Sel77,Tri08}} \label{BSST} \\
Let $A$ be any set of positive integers with $\gcd (A)=1$. For any $a \in A$, 
\begin{eqnarray*} 
{\g}(A) = \left(\max_{\bf C}\: {\m}_{\bf C}\right) - a, \quad {\n}(A) = \frac{1}{a} \sum_{\bf C}\: {\m}_{\bf C} - \frac{1}{2}(a-1), \\
{\s}(A) = \frac{1}{2a} \sum_{\bf C} {{\m}_{\bf C}}^2 - \frac{1}{2} \sum_{\bf C} {\m}_{\bf C} + \frac{1}{12}(a^2-1), 
\end{eqnarray*}
where the maximum and the sums are taken over all nonzero classes $\bf C$ modulo $a$.
\end{proposition}

Generating functions naturally enter as a tool in the study of the 
Frobenius problem. The results in Proposition \ref{SBS} are the
combinatorial analogues of the corresponding results in Proposition
\ref{BSST}. The generating function $f_A$ for the set $A$ can be used
to evaluate the functions ${\g}$ and ${\n}$ (this is almost folklore,
but the evaluation of ${\n}$ in this manner actually appears in
\cite{Syl84}). The use of the function $f_A$ to evaluate ${\s}(A)$ is
due to Brown and Shiue \cite{BS93}; in fact, they used this method to
determine ${\s}(a,b)$.

\begin{proposition} {\bf \cite{BS93,Syl84}} \label{SBS} \\
Let $A$ be any set of positive integers with $\gcd (A)=1$. Set 
\[ f_A(t) = \sum_{a \in A} t^a. \]
Then 
\[ f_{{\G}^c(A)}(t) = \frac{1}{1-t} - f_{{\G}(A)}(t), \]
and 
\[ {\g}(A) = \text{deg}\,f_{{\G}^c(A)}(t), \quad {\n}(A) = \lim_{t \imp 1} f_{{\G}^c(A)}(t), \quad {\s}(A) = \lim_{t \imp 1} f_{{\G}^c(A)}^{\pr}(t). \]
\end{proposition}

The following reduction formulae for ${\g}(A)$, due to Johnson \cite{Joh60} for the three variable case and to Brauer and Shockley \cite{BS62} for the general case, and for ${\n}(A)$ due to R{\o}dseth \cite{Rod78}, are useful in cases when all but one member of $A$ share a common divisor greater than $1$. 

\begin{proposition} {{\bf \cite{BS62,Rod78}}} \label{BSR} \\
Let $A$ be any set of positive integers with $\gcd (A)=1$. If $a \in A$ is such that $\gcd (A \sm \{a\})=d$, and $A^{\pr}=\frac{1}{d}\big(A \sm \{a\}\big)$, then 
\[ {\g}\big(A\big) = d \cdot {\g}\big(A^{\pr} \cup \{a\}\big) + a(d-1), \quad {\n}\big(A\big) = d \cdot {\n}\big(A^{\pr} \cup \{a\}\big) 
    + \ts\frac{1}{2}(a-1)(d-1). 
\]
\end{proposition}

The set ${\S}^{\star}(A)$ consists of integers $n$ in ${\G}^c(A)$ such that translating the set of positive integers in ${\G}(A)$ by $n$ results in a subset of ${\G}(A)$. Since ${\g}(A) \in {\S}^{\star}(A)$, determining ${\S}^{\star}(A)$ ensures that ${\g}(A)$ is also determined.  The following result is due to Tripathi \cite{Tri03}. 

\begin{proposition} {\bf \cite{Tri03}} \label{T} \\
Let $A$ be any set of positive integers with $\gcd (A)=1$. Let $a \in A$, and let ${\m}_x$ denote the least integer in ${\G}(A)$ congruent to $x$ modulo $a$, $1 \le x \le a-1$. Then 
\[ {\S}^{\star}(A) = \big\{{\m}_x-a: {\m}_x + {\m}_y \ge {\m}_{x+y} +a \;\mbox{for}\; 1 \le y \le a-1 \big\}. \]
\end{proposition}

\section{Main results}
\label{section3}

Throughout this section, we consider the set $A=\{a,b,c\}$ with $\gcd(a,b,c)=1$ and $a \mid \lcm(b,c)$. We prove Theorem \ref{main} by using the results in 
Section~\ref{prelim}. More specifically, we use Proposition \ref{BSST} and Proposition \ref{BSR} to determine both ${\g}(A)$ and ${\n}(A)$. 
We also use Proposition \ref{BSST} to determine ${\s}(A)$. We use Proposition \ref{SBS} to determine ${\g}(A)$ and ${\n}(A)$ via the proofs using Proposition \ref{BSST}. Finally, we use Proposition \ref{T} to determine ${\S}^{\star}(A)$, which incidentally also provides another proof for the formula for ${\g}(A)$. The result of Corollary \ref{main_corollary} is a direct consequence of Theorem \ref{main}; the details are omitted. 

\subsection{Determining ${\g}(A)$ and ${\n}(A)$ from Proposition \ref{BSR}} \label{one}

We first use the reduction formula given in Proposition \ref{BSR} to determine both ${\g}(A)$ and ${\n}(A)$. The following lemma is crucial to many results in this section. 

\begin{lemma} \label{a=rs}
Suppose $a,b,c$ are positive integers, with $\gcd(a,b,c)=1$. If $a \mid \lcm(b,c)$, then $a=\gcd(a,b) \cdot \gcd(a,c)$.  
\end{lemma}

\begin{proof}
Let $p$ be a prime divisor of $a$, and let $p^{\a}$, $p^{\b}$, $p^{\gamma}$ be the highest power of $p$ dividing $a$, $b$, $c$, respectively. Then $0=\min \{\b,\gamma\}<\a \le \max\{\b,\gamma\}$. Thus $a=rs$, where $r=\gcd(a,b)$, $s=\gcd(a,c)$ and $\gcd(r,s)=1$.
\end{proof}
 
\noindent{\bf Proof of Theorem \ref{main}, (a) and (b).} 

\noindent From Lemma \ref{a=rs} we have $a=rs$, where $r=\gcd(a,b)$, $s=\gcd(a,c)$ and $\gcd(r,s)=1$. Note that $bs=ab/r=\lcm(a,b)$ and $cr=ac/s=\lcm(a,c)$. 

If $1 \in A$, then ${\G}(A)={\Z}_{\ge 0}$, and so we define ${\g}(A)=-1$ in this case. We apply Proposition \ref{BSR}. 
\begin{itemize}
\item[{\rm (a)}]
\begin{eqnarray*} 
{\g}(a,b,c) & = & r \cdot {\g}\left(\ts\frac{a}{r},\ts\frac{b}{r},c\right) + c(r-1) \\
& = & r \Big( s \cdot {\g}\left(1,\ts\frac{b}{r},\ts\frac{c}{s}\right) + \ts\frac{b}{r}(s-1) \Big) + c(r-1) \\
& = & a \cdot {\g}\left(1,\ts\frac{b}{r},\ts\frac{c}{s}\right) + b(s-1) + c(r-1)  \\
& = & bs + cr - a - b - c \\
& = & \lcm(a,b) + \lcm(a,c) - (a+b+c). 
\end{eqnarray*} 
\item[{\rm (b)}]
\begin{eqnarray*} 
{\n}(a,b,c) & = & r \cdot {\n}\left(\ts\frac{a}{r},\ts\frac{b}{r},c\right) + \ts\frac{1}{2}(c-1)(r-1) \\
& = & r \Big( s \cdot {\n}\left(1,\ts\frac{b}{r},\ts\frac{c}{s}\right) + \ts\frac{1}{2}\left(\ts\frac{b}{r}-1\right)(s-1) \Big) + \ts\frac{1}{2}(c-1)(r-1) \\
& = & a \cdot {\n}\left(1,\ts\frac{b}{r},\ts\frac{c}{s}\right) + \ts\frac{1}{2}(b-r)(s-1) + \ts\frac{1}{2}(c-1)(r-1)  \\
& = & \ts\frac{1}{2}(b-r)(s-1) + \ts\frac{1}{2}(c-1)(r-1) \\
& = & \ts\frac{1}{2}\big( bs + cr - rs - b - c + 1 \big) \\
& = &  \ts\frac{1}{2}\Big( \lcm(a,b) + \lcm(a,c) - (a+b+c) + 1\Big). 
\end{eqnarray*} 
\end{itemize}
\hfill $\square$

\subsection{Determining ${\g}(A)$, ${\n}(A)$ and ${\s}(A)$ from Proposition \ref{BSST}} \label{two}

We next use Proposition \ref{BSST} to determine ${\g}(A)$, ${\n}(A)$, and ${\s}(A)$. This requires the determination of ${\m}_{\bf C}$ for each nonzero residue class ${\bf C}$ modulo $a$. We note that the maximum and the sum in Proposition \ref{BSST} may also be taken to include ${\m}_0=0$.  

\begin{theorem} \label{m_i}
Let $A=\{a,b,c\}$, where $\gcd(a,b,c)=1$ and $a \mid \lcm(b,c)$. Let ${\m}_i$ denote the least integer in ${\G}(\{a,b,c\})$ which is congruent to $i$ modulo $a$. Then 
\[ \big\{ {\m}_i: 0 \le i \le a-1 \big\} = \big\{ bx+cy: 0 \le x \le s-1, 0 \le y \le r-1 \big\},\] 
where $r=\gcd(a,b)$ and $s=\gcd(a,c)$. 
\end{theorem}

\begin{proof}
Suppose $bx_1+cy_1 \equiv bx_2+cy_2\mod{a}$ with $0 \le x_1, x_2 \le s-1$ and $0 \le y_1, y_2 \le r-1$. Then $bx_0 \equiv cy_0\mod{a}$ with $|x_0|<s$ and $|y_0|<r$. Since $r=\gcd(a,b)$ and $s=\gcd(a,c)$, $bx_0 \bmod{a} \in \{0,r,2r,3r,\ldots,a-r\}$ and $cy_0 \bmod{a} \in \{0,s,2s,3s,\ldots,a-s\}$. Since $rs=a$ and $\gcd(r,s)=1$, it follows that $bx_0 \bmod{a}=cy_0 \bmod{a}=0$. This is only possible if $x_0=y_0=0$ since $|x_0|<s$ and $|y_0|<r$, which in turn implies $x_1=x_2$ and $y_1=y_2$. Since $rs=a$, it follows that the set $\{bx+cy: 0 \le x \le s-1, 0 \le y \le r-1\}$ is a complete residue system modulo $a$. 

Fix $x_0 \in \{0,\ldots,s-1\}$ and $y_0 \in \{0,\ldots,r-1\}$. We show that $bx_0+cy_0-a \notin {\G}(\{a,b,c\})$. Suppose, to the contrary, that $bx_0+cy_0-a=az+bx+cy$ for some nonnegative integers $x,y,z$. Let $x=x_1+\l s$, $0 \le x_1 \le s-1$, $\l \ge 0$, and $y=y_1+\mu r$, $0 \le y_1 \le r-1$, $\mu \ge 0$. Then $bx_1+cy_1 \equiv bx+cy \equiv bx_0+cy_0\mod{a}$. By the argument in the preceding paragraph, $x_1=x_0$ and $y_1=y_0$. But this is clearly impossible since $bx_0+cy_0-a=az+bx+cy \ge bx+cy \ge bx_1+cy_1=bx_0+cy_0$. Therefore $bx_0+cy_0-a \notin {\G}(\{a,b,c\})$ for each $0 \le x_0 \le s-1$ and $0 \le y_0 \le r-1$. 
\end{proof}

\noindent{\bf Proof of Theorem \ref{main}, (a), (b), and (c).}  
\begin{itemize}
\item[{\rm (a)}]
Recall that $bs=\lcm(a,b)$ and $cr=\lcm(a,c)$. We apply Proposition \ref{BSST}. 
\begin{eqnarray*}
{\g}(a,b,c) & = & \left(\max_{0 \le i \le a-1} {\m}_i\right) - a \\
& = & \left( \max_{0 \le x \le s-1,\,0 \le y \le r-1} (bx+cy) \right) - a \\
& = & b(s-1) + c(r-1) - a \\
& = & \lcm(a,b) + \lcm(a,c) - (a+b+c). 
\end{eqnarray*}

\item[{\rm (b)}]
\begin{eqnarray*}
{\n}(a,b,c) & = & \frac{1}{a} \sum_{i=0}^{a-1} {\m}_i - \frac{1}{2}(a-1) \\
& = & \frac{1}{a} \sum_{x=0}^{s-1} \sum_{y=0}^{r-1} (bx+cy) - \frac{1}{2}(a-1) \\
& = & \frac{1}{a} \sum_{x=0}^{s-1} \left( brx + \frac{1}{2}cr(r-1) \right) - \frac{1}{2}(a-1) \\
& = & \frac{1}{a} \left( \frac{1}{2}brs(s-1) + \frac{1}{2}crs(r-1) \right) - \frac{1}{2}(a-1) \\
& = & \frac{1}{2} \Big( b(s-1) + c(r-1) \Big) - \frac{1}{2}(a-1) \\
& = & \frac{1}{2}\Big( \lcm(a,b) + \lcm(a,c) - (a+b+c) + 1\Big). 
\end{eqnarray*}

\item[{\rm (c)}]
\begin{eqnarray*}
{\s}(a,b,c) & = & \frac{1}{2a} \sum_{i=0}^{a-1} {{\m}_i}^2 - \frac{1}{2} \sum_{i=0}^{a-1} {\m}_i + \frac{1}{12}(a^2-1) \\
& = & \frac{1}{2a} \sum_{x=0}^{s-1} \sum_{y=0}^{r-1} (bx+cy)^2 - \frac{1}{2} \sum_{x=0}^{s-1} \sum_{y=0}^{r-1} (bx+cy) + \frac{1}{12}(a^2-1) \\
& = & \frac{1}{2a} \sum_{x=0}^{s-1} \left( b^2rx^2 + bcr(r-1)x + \frac{1}{6}c^2r(r-1)(2r-1) \right) - \frac{1}{2} \sum_{x=0}^{s-1} 
\left( brx + \frac{1}{2}cr(r-1) \right) \\
& & + \frac{1}{12}(a^2-1) \\
& = &  \frac{1}{12a}b^2rs(s-1)(2s-1) + \frac{1}{4a}bcr(r-1)s(s-1) + \frac{1}{12a}c^2rs(r-1)(2r-1) \\
& & - \frac{1}{4}brs(s-1) - \frac{1}{4}crs(r-1) + \frac{1}{12}(a^2-1) \\
& = & \frac{1}{12} \Big( b^2(s-1)(2s-1) + c^2(r-1)(2r-1) \Big) \\ 
& & + \frac{1}{4} \Big( bc(r-1)(s-1) - ab(s-1) - ac(r-1) \Big) + \frac{1}{12}(a^2-1) \\
& = & \frac{1}{12} \Big( 2\big( (bs)^2+(cr)^2 \big) - 3b(bs) - 3c(cr) + b^2 + c^2 + 3abc \\ 
& & - 3bc(r+s) + 3bc + 3ab + 3ac - 3a(bs+cr) + a^2 - 1\Big) \\
& = & \frac{1}{12} \Big( a^2 + b^2 + c^2 + 3abc + 3(ab+bc+ca) - 3(a+b+c)\big(\lcm(a,b)+\lcm(a,c)\big)  \\
& & + 2\big( \big(\lcm(a,b)\big)^2+\big(\lcm(a,c)\big)^2 \big) - 1 \Big). 
\end{eqnarray*}
\end{itemize}
\hfill $\square$

\subsection{Determining ${\g}(A)$, ${\n}(A)$ and ${\s}(A)$ from Proposition \ref{SBS}} \label{three}

Theorem \ref{m_i} plays a crucial role in determining ${\g}(A)$, ${\n}(A)$, and ${\s}(A)$ using Proposition \ref{SBS}. In each case, however, we are only able to reduce the problem to an expression that we have already evaluated in Subsection \ref{two}, but not able to compute these functions directly. In effect, this is a demonstration of how the results in Proposition \ref{BSST} and Proposition \ref{SBS} are connected.  

From Theorem \ref{m_i} we know that every $n \in {\G}(A)$ may be uniquely expressed as $bx+cy+az$, with $x \in \{0,\ldots,s-1\}$, $y \in \{0,\ldots,r-1\}$, and $z \in {\Z}_{\ge 0}$. Hence 
\begin{eqnarray*}
f_{{\G}^c(A)}(t) & =  & \frac{1}{1-t} - f_{{\G}(A)}(t) \\
& = & \frac{1}{1-t} - \sum_{\substack{0 \le x \le s-1 \\ 0 \le y \le r-1 \\ z \ge 0}} t^{bx+cy+az} \\
& = & \frac{1}{1-t} - \left( \sum_{0 \le x \le s-1} t^{bx} \right) \left( \sum_{0 \le y \le r-1} t^{cy} \right) \left( \sum_{z \ge 0} t^{az} \right) \\
& = & \frac{1}{1-t} - \frac{1-t^{bs}}{1-t^b} \cdot \frac{1-t^{cr}}{1-t^c} \cdot \frac{1}{1-t^a}. 
\end{eqnarray*}
However, it is perhaps more useful to use the equivalent formulation 
\[ f_{{\G}^c(A)}(t) = \frac{1}{1-t^a} \left( \sum_{0 \le z \le a-1} t^z - \sum_{\substack{0 \le x \le s-1 \\ 0 \le y \le r-1}} t^{bx+cy} \right) \]
to see how the computation of ${\g}(A)$ and ${\n}(A)$ would follow from Proposition \ref{SBS} and Theorem \ref{m_i}. Deriving the formulae for ${\g}(A)$, ${\n}(A)$, and ${\s}(A)$ directly from either of the two equivalent versions of $f_{{\G}^c(A)}(t)$ appear to be difficult; instead, we use Proposition \ref{SBS} to reduce the respective formulae to the situation in Subsection \ref{two}. The reduction of the formula for ${\s}(A)$ in Proposition \ref{SBS} to that in Proposition \ref{BSST} in this special case is tedious, and is omitted in this discussion. 

\begin{itemize}
\item[{\rm (a)}]
\[ {\g}(a,b,c) = \text{deg}\:\left(\frac{1}{1-t} - \sum_{\substack{0 \le x \le s-1 \\ 0 \le y \le r-1 \\ z \ge 0}} t^{bx+cy+az}\right) = \max {\G}^c(A) 
= \left(\max_{\bf C}\: {\m}_{\bf C}\right) - a. 
\]

\item[{\rm (b)}]
\begin{eqnarray*}
{\n}(a,b,c) & = & \lim_{t \imp 1} \frac{1}{1-t^a} \left( \sum_{0 \le z \le a-1} t^z - \sum_{\substack{0 \le x \le s-1 \\ 0 \le y \le r-1}} t^{bx+cy} \right) \\
& = & \lim_{t \imp 1} \frac{1}{-at^{a-1}} \left( \sum_{1 \le z \le a-1} zt^{z-1} - \sum_{\substack{0 \le x \le s-1 \\ 0 \le y \le r-1 \\ (x,y) \ne (0,0)}} (bx+cy)t^{bx+cy-1} \right) \\ 
& = & \frac{1}{a} \left( \sum_{\substack{0 \le x \le s-1 \\ 0 \le y \le r-1 \\ (x,y) \ne (0,0)}} (bx+cy) - \sum_{1 \le z \le a-1} z \right) \\
& = & \frac{1}{a} \sum_{\bf C}\: {\m}_{\bf C} - \frac{1}{2}(a-1).   
\end{eqnarray*}
\end{itemize}
\hfill $\square$

\subsection{Deriving ${\n}(A)$ from ${\g}(A)$}

The results of Theorems \ref{main} imply $n \in {\G}(\{a,b,c\})$ if and only if ${\g}(a,b,c)-n \notin {\G}(\{a,b,c\})$. Were this to hold, it would follow by pairing $n$ with ${\g}(a,b,c)-n$ for $n \in \{0,\ldots,{\g}(a,b,c)\}$ that 
\[ {\n}(a,b,c) = \ts\frac{1}{2}\big({\g}(a,b,c) + 1\big). \]
Thus the formula for ${\n}(a,b,c)$ would follow from that of ${\g}(a,b,c)$, and vice-versa, in this case. 

It is easy to see that at least one of $n$ and ${\g}(a,b,c)-n$ must belong to ${\G}^c(\{a,b,c\})$; if both belonged to ${\G}(\{a,b,c\})$, it would lead to their sum ${\g}(a,b,c)$ belonging to ${\G}(\{a,b,c\})$. Therefore we always have the inequality 
\[ {\n}(a,b,c) \ge \ts\frac{1}{2}\big({\g}(a,b,c) + 1\big), \] 
with equality precisely when 
\[ n \notin {\G}(\{a,b,c\}) \;\;\text{implies}\;\; {\g}(a,b,c)-n \in {\G}(\{a,b,c\}) \]
holds. 

Suppose $n \notin {\G}(\{a,b,c\})$. Then $n=bx+cy-az$ for some $x \in [0,s-1]$, $y \in [0,r-1]$, and $z \ge 1$ by Theorem \ref{m_i}. Hence 
\[ {\g}(a,b,c) - n = b(s-1) + c(r-1) - a - (bx+cy-az) = b(s-1-x) + c(r-1-y) + a(z-1) \in {\G}(\{a,b,c\}). \]

Therefore ${\n}(a,b,c)=\frac{1}{2}\big({\g}(a,b,c) + 1\big)$ holds for $A=\{a,b,c\}$ with $a \mid \lcm(b,c)$. 

\subsection{Determining the set ${\S}^{\star}(A)$}

Determining the set ${\S}^{\star}(A)$ is dependent on being able to compute each ${\m}_{\bf C}$. Since Theorem \ref{m_i} determines the set of all ${\m}_{\bf C}$, we may use Proposition \ref{T} to determine ${\S}^{\star}(A)$, which in turn gives us ${\g}(A)$. \\

\noindent{\bf Proof of Theorem \ref{main} (d).} 

\noindent Each ${\m}_{\bf C}$ is of the form $bx+cy$ with $0 \le x \le s-1$ and $0 \le y \le r-1$ by Theorem \ref{m_i} (a); note that ${\m}_0=0$. Note that $bx_1+bx_2 \equiv b\big((x_1+x_2)\bmod{s}\big)\mod{a}$ since $bs=\lcm(a,b)$ and $cy_1+cy_2 \equiv c\big((y_1+y_2)\bmod{r}\big)\mod{a}$ since $cr=\lcm(a,c)$. So if ${\m}_i=bx_1+cy_1$ and ${\m}_j=bx_2+cy_2$, then ${\m}_{i+j}=b\big((x_1+x_2)\bmod{s}\big)+c\big((y_1+y_2)\bmod{r}\big)$. 

Although it is apparent from the definition of ${\S}^{\star}(A)$ that ${\g}(A) \in {\S}^{\star}(A)$, we nevertheless provide a direct proof using Proposition \ref{T}. We recall that $\lcm(a,b)=bs$ and $\lcm(a,c)=cr$, so that ${\g}(A)=\lcm(a,b)+\lcm(a,c)-(a+b+c)=b(s-1)+c(r-1)-a$. 

Let $x \in \{0,\ldots,s-1\}$ and $y \in \{0,\ldots,r-1\}$, with $(x,y) \ne (0,0)$. If $x>0$ and $y>0$, then 
\[ \big(b(s-1)+c(r-1)\big) + (bx+cy) = b(x-1)+c(y-1) + \lcm(a,b) + \lcm(a,c)  \ge  b(x-1)+c(y-1) + 2a. \]
If $x=0$, then $y>0$ and
\[ \big(b(s-1)+c(r-1)\big) + (bx+cy) = b(s-1)+c(y-1) + \lcm(a,c) \ge b(s-1)+c(y-1) + a. \]
If $y=0$, then $x>0$ and
\[ \big(b(s-1)+c(r-1)\big) + (bx+cy) = b(x-1)+c(r-1) + \lcm(a,b) \ge b(x-1)+c(r-1) + a. \]
Hence $b(s-1)+c(r-1)-a \in {\S}^{\star}$ by Proposition \ref{T}. 

Suppose $x_0 \in [0,s-1]$ and $y_0 \in [0,r-1]$, with $(x_0,y_0) \ne (0,0), (s-1,r-1)$. Then $b(s-1-x_0)+c(r-1-y_0)$ is of form ${\m}_x$ and  
\[ (bx_0+cy_0) + b(s-1-x_0)+c(r-1-y_0) = b(s-1)+c(r-1), \]
so that Proposition \ref{T} fails to hold for at least one $x \in [1,a-1]$. Hence $bx_0+cy_0-a \notin {\S}^{\star}$ if $(x_0,y_0) \ne (s-1,r-1)$. 

This completes the proof of this theorem.  
\hfill $\square$

\begin{remark}
For any set of positive integers $A$ with $\gcd A=1$, it can be shown that ${\n}(A)=\frac{1}{2}\big(1+{\g}(A)\big)$ implies ${\S}^{\star}(A)=\{{\g}(A)\}$. 
\end{remark}

\begin{remark}
The results of this paper cannot be easily extended to the case $A=\{a,b_1,\ldots,b_k\}$ where $\gcd(a,b_1,\ldots,b_k)=1$ and $a \mid \lcm(b_1,\ldots,b_k)$ for $k>2$. This is because the divisibility condition $a \mid \lcm(b_1,\ldots,b_k)$ does not imply $a=r_1\cdots r_k$ where $r_i=\gcd(a,b_i)$ for $1 \le i \le k$. 
\end{remark}

\section{Acknowledgments}

The author wishes to thank two anonymous referees for several helpful suggestions, including for the results using generating functions. 

\begin{thebibliography}{99}

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

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

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

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

\bibitem{Rod78} \O. J. R\o dseth, On a linear diophantine problem of
Frobenius, {\it J. Reine Angew. Math.\/} {\bf 301} (1978), 171--178.

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

\bibitem{Syl84} J. J. Sylvester, Problem 7382, in W. J. C. Miller, ed.,
Mathematical Questions, with their Solutions, from the ``Educational
Times" {\bf 41} (1884), p.~21. Solution by W. J. Curran Sharp.

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

\bibitem{Tri06} A. Tripathi, On a linear diophantine problem of
Frobenius, {\it Integers\/} {\bf 6} (2006), Article A14.

\bibitem{Tri08} A. Tripathi, On sums of positive integers that are not
of the form $ax+by=n$, {\it Amer. Math. Monthly\/} {\bf 115} (2008),
363--364.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11D07.

\noindent \emph{Keywords: } linear Diophantine equation, Frobenius problem.


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 27 2017;
revised versions received  May 1 2017; June 15 2017; June 26 2017.
Published in {\it Journal of Integer Sequences}, July 2 2017.

\bigskip
\hrule
\bigskip

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


\end{document}



.