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.

Amari Flowers 2021-02-11 Answered
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.

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Plainmath recommends

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

Expert Answer

Latisha Oneil
Answered 2021-02-12 Author has 14092 answers

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\)

Have a similar question?
Ask An Expert
30
 

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Relevant Questions

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.

asked 2021-10-09
If a, b are elements of a ring and m, n ∈ Z, show that (na) (mb) = (mn) (ab)
asked 2021-06-18

If a, b are elements of a ring and m, \(n \in Z\), show that \((na) (mb) = (mn) (ab)\)

asked 2020-11-09

Show that if \(\displaystyle{K}\subseteq{F}\) is an extension of degree k, every element \(\displaystyle\alpha\in{F}\) has a minimal polynomial over K of degree <=k. Find theminimal polymials of complex numers over \(\displaystyle\mathbb{R}\) explicitly to verify this fact

asked 2021-05-12
One property of Laplace transform can be expressed in terms of the inverse Laplace transform as \(L^{-1}\left\{\frac{d^nF}{ds^n}\right\}(t)=(-t)^n f(t)\) where \(f=L^{-1}\left\{F\right\}\). Use this equation to compute \(L^{-1}\left\{F\right\}\)
\(F(s)=\arctan \frac{23}{s}\)
asked 2021-05-01

The graph below expresses a radical function that can be written in the form \(f(x) = a(x + k)^{\frac{1}{n}} + c\). What does the graph tell you about the value of c in this function?

asked 2021-08-12
Discrete math.
Prove the following fact by induction:
For every non-negative integer n, 2 evenly divides \(\displaystyle{n}^{{{2}}}-{7}{n}+{4}\).

Plainmath recommends

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