We work under the given condtions, a, b positive coprime integers, gcd \((a,b)=1\). By Euclidean algorithm, we know that ANY integer x can be represented as \(an+bm\) . The point is that we require that n and m be non-negative integers. To explain this, consider the example \(a =10,b=3\). The statement says that every integer \(x > 30-10-3=17\) can be represented thus. Note that the integer 13 (less than 17) is also of this form , but 17 cannot be represented thus. We need to prove it in the general case.

Example: \(a=10, b=3\).

The following are representable in the required form 3,6,9,10,12,13,15,16

The following are not representable in the required form 1,2,4,5,7,8,11,14,17.

But, as per theorm. all \(x=18,19 (x>17=ab-a-b)\) are representable in the required form.

Describing all integral solutions (no conditions) of the equation \(an+bm =x\). The last line expresses all the solutions (n,m) in terms of a particular solution \(\displaystyle{\left(\alpha,\beta\right)}\) , we have crucially used that a and b are relatively prime.

Given: a,b positive integers, \((a,b)=1\)

By Euclidean algorithm, \(\displaystyle\exists\alpha,\beta\in\mathbb{Z}\), with \(\displaystyle{a}\alpha+{b}\beta={x}{Z}\)

Consider any general solution

\(an+bm=x\) Then \(\displaystyle{a}{n}+{b}{m}={a}\alpha+{b}\beta{r}{A}{r}{\mathtt{{a}}}{\left({n}-\alpha\right)}={b}{\left(\beta-{m}\right)}\)

But \(\displaystyle{\left({a},{b}\right)}={1}\Rightarrow\exists{t}\in\mathbb{Z}\), with \(\displaystyle{n}-\alpha={t}{b},\beta-{m}={t}{a}\),

So, \(\displaystyle{n}=\alpha+{t}{b},{m}=\beta={t}{a}{\left({t}\in\mathbb{Z}\right)}\)

Thus, if \(\displaystyle\alpha,\beta\in\mathbb{Z}\) with \(\displaystyle{a}\alpha+{b}\beta={x}\), then all solutions \(an+bm=x\), given by \(\displaystyle{n}=\alpha+{t}{b},{m}=\beta={t}{a}{\left({t}\in\mathbb{Z}\right)}\)

Note, that the m's can be brought to {0,1,2,...,a-1} In particular, m are all non-negative

We have shown that the largest x for which the representation \(an+bm=x\) with n, m non-negative is not possible is \(x=ab-a-b\). In other words, if \(x>ab-a-b\), then x can be represented as \(an+bm\) , for some non-negative integers a and b.

Now, note that \(\displaystyle\alpha{<}{0}\Rightarrow\alpha+{t}{b}{<}{0}\forall{t}\le-{\quad\text{and}\quad}\beta-{t}{a}{<}{0}\forall{t}\ge{0}.\)

Thus, the set of all x not admitting non-negative solutions for \(an+bm=x\) is \(\displaystyle{\left\lbrace{a}\alpha+{b}\beta:\alpha{<}{0},\beta\in{\left\lbrace{0},{1},{2},\ldots,{a}-{1}\right\rbrace}\right.}\)

The largest such x corresponds to \(\displaystyle\alpha=-{1},\beta={a}-{1}\), with \(\displaystyle{x}={\left(-{1}\right)}{a}+{\left({a}-{1}\right)}{b}={a}{b}-{a}-{b}.\)

We have already proved that x=ab-a-b is not representable in the required form. Here is another proof.

Now, the equation \(an+bm=ab-a-b\), has a particular solution \(n=-1, m=a-1\).

So, the general solution is \(n=-1+tb, m=(a-1)-at\)

\(\displaystyle{n}\ge{0}\Rightarrow{t}{b}\ge{1}\Rightarrow{t}\ge{1}\)

But \(\displaystyle{t}\ge{1}\Rightarrow{\left({a}-{1}\right)}-{a}{t}{<}{0}\)

So \(x=ab-a-b\) cannot be expressed as \(x=an+bm\),n,m,non-negative integers.