Question

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.

Abstract algebra
ANSWERED
asked 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.

Answers (1)

2021-01-06

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.
image

0
 
Best answer

expert advice

Need a better answer?
...