# Let a,b be coprime inegers. Prove that every integer x>ab-a-b can be written as na-mb where n,m where are non-negative inegers. Prove that ab-a-b connot be expressed ib this form.

Let a,b be coprime inegers. Prove that every integer x>ab-a-b can be written as na-mb where n,m where are non-negative inegers. Prove that ab-a-b connot be expressed ib this form.

• Questions are typically answered in as fast as 30 minutes

### Plainmath recommends

• Get a detailed answer even on the hardest topics.
• Ask an expert for a step-by-step guidance to learn to do it yourself.

Latisha Oneil

In the following, a and b are coprime positive integers, Note that , by Euclidean algorithm, ANY integer x is an integral linear combination na+mb. The point is we seek sufficient condtions on the integer x ( namely $$x>ab-a-b) na+nb=x$$ with both n and m non-negative,For instance , consider $$a =10, b =3$$, clearly relatively prime positive integers . Now $$x=10+3=13$$ is a non-negative integral linear combination of a and b , but 14,16, 17 are not. The theorem asserts that whenver $$x > 10 \cdot 3-10-3=17$$,x can be expressed as $$10n+3m$$ , with n and m non-negative integers.
General solution of (1) is derived , using the fact that a and b are relatively prime.
Let $$\displaystyle{x}\in\mathbb{Z}$$
As gcda,b)=1, $$\displaystyle\exists\alpha,\beta\in\mathbb{Z}$$, with $$\displaystyle{a}\alpha+{b}\beta={x}$$ (1)
Let (n,m) be any solution of (1): $$an+bm=x$$
Then $$\displaystyle{a}{n}+{b}{m}={a}\alpha+{b}\beta\Rightarrow{a}{\left({n}-\alpha\right)}={b}{\left(\beta-{m}\right)}$$
As $$gcd(a,b)=1$$, this $$\displaystyle\Rightarrow\mathbb{R}{t}\in\mathbb{Z}$$. with $$\displaystyle{n}-\alpha={b}{t}{\quad\text{and}\quad}\beta-{m}={a}{t}\Leftrightarrow{n}=\alpha+{b}{t},{m}=\beta-{a}{t}$$(2)
1) Observe that from (2), any two solutions for m differ by a multiple of a . So there exists a unique solution for m which lies in among $$\{0,1,2,...a-1\}.$$
2) We have characterized when we can obtain non-negative solutions.
General solution for $$an+bm=x$$ (1)
$$\displaystyle{n}=\alpha+{b}{t},{m}=\beta-{a}{t},{t}\in\mathbb{Z}$$ (2)
Fix m for which $$\displaystyle{m}=\beta-{a}{t}\in{\left\lbrace{0},{1},{2},..{a}-{1}\right\rbrace}$$
Consider the corresponding solution (n,m).
Claim: $$\displaystyle\alpha\ge{0}\Leftrightarrow{n}\ge{0},{m}\ge{0}$$
Proof: If $$\displaystyle\alpha{<}-{b}{t}$$, then $$\displaystyle{n}-\alpha+{b}{t}{<}{0}\forall{t}{<}{0}{\quad\text{and}\quad}{m}={m}=\beta-{a}{t}{<}{0}\forall{t}\ge{0}.$$
So, $$\displaystyle\alpha{<}{0}\Rightarrow$$ at least one ofm,n less than 0.
We have thus demonstrated that whenver x is an integer $$> ab-a-b$$, there exists non-negative integer solutions to the equation $$x =na +mb$$. This proves the first part of the problem.
We have shown $$\displaystyle{\left\lbrace{x}\in\mathbb{Z}:{a}{n}+{b}{m}={x}\Rightarrow{n}{\quad\text{or}\quad}\in{m}{<}{0}\right\rbrace}={\left\lbrace{x}:{x}-{a}{n}+{b}{m}:{n}{<}{0},{m}\in{\left\lbrace{0},{1},{2},\ldots,{a}-{1}\right\rbrace}\right.}$$
The maximum such value corresponds to in $$n=-1, m=a-1$$, that is, when $$x=-1(a)+(a-1)b=ab-a-b$$,
Proof: The second part of the problem: with $$(a,b) =1$$ , ie a and b are relatively prime implies that ab-a-b is not a non-negative integer linear combination of a and b.
Now, $$an+bm=ab-a-b$$, admits $$n=-1, m=a-1$$ as a particular solution. As above, the genaral solution is $$n=-1+tb, m=(a-1)-ta$$
Claim:$$\displaystyle{n}\ge{0}\Leftrightarrow{m}{<}{0}.$$
Proof: n$$\displaystyle\ge{0}\Leftrightarrow{t}{b}\ge{1}\Leftrightarrow{t}\ge{1}\Leftrightarrow{t}{a}\ge{a}\Leftrightarrow{m}={\left({a}-{1}\right)}-{t}{a}{<}{0}$$
Conclusion" ab-a-b is not a non-negative linearinegral combination of a and b.
Answer: 1) $$\displaystyle{\left({a},{b}\right)}={1},{a},{b}{>}{0},{x}{>}{a}{b}-{a}-{b}\Leftrightarrow\exists{n},{m}\in\mathbb{Z}$$ with $$\displaystyle{a}{n}_{{b}}{m}={x}$$
2) $$(a,b)=1,a,b>0,$$
then $$an+bm=ab-a-b$$ cannot be solved with both $$m,n>=0$$