Joni Kenny

2021-01-05

Let a,b be coprime integers. Prove that every integer $x>ab-a-b$ can be written as $na+mb$ where n,m are non negative integers. Prove that $ab-a-b$ cannot be expressed in this form.

Mayme

We work under the given condtions, a, b positive coprime integers, gcd $\left(a,b\right)=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\left(x>17=ab-a-b\right)$ 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 $\left(\alpha ,\beta \right)$ , we have crucially used that a and b are relatively prime.
Given: a,b positive integers, $\left(a,b\right)=1$
By Euclidean algorithm, $\mathrm{\exists }\alpha ,\beta \in \mathbb{Z}$, with $a\alpha +b\beta =xZ$
Consider any general solution
$an+bm=x$ Then $an+bm=a\alpha +b\beta rAr\mathtt{a}\left(n-\alpha \right)=b\left(\beta -m\right)$
But $\left(a,b\right)=1⇒\mathrm{\exists }t\in \mathbb{Z}$, with $n-\alpha =tb,\beta -m=ta$,
So, $n=\alpha +tb,m=\beta =ta\left(t\in \mathbb{Z}\right)$
Thus, if $\alpha ,\beta \in \mathbb{Z}$ with $a\alpha +b\beta =x$, then all solutions $an+bm=x$, given by $n=\alpha +tb,m=\beta =ta\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 $\alpha <0⇒\alpha +tb<0\mathrm{\forall }t\le -\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}\beta -ta<0\mathrm{\forall }t\ge 0.$
Thus, the set of all x not admitting non-negative solutions for $an+bm=x$ is $\left\{a\alpha +b\beta :\alpha <0,\beta \in \left\{0,1,2,\dots ,a-1\right\}$
The largest such x corresponds to $\alpha =-1,\beta =a-1$, with $x=\left(-1\right)a+\left(a-1\right)b=ab-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=\left(a-1\right)-at$
$n\ge 0⇒tb\ge 1⇒t\ge 1$
But $t\ge 1⇒\left(a-1\right)-at<0$
So $x=ab-a-b$ cannot be expressed as $x=an+bm$,n,m,non-negative integers.

Do you have a similar question?