Online Course Discussion Forum
MC II A 3.30 Help please?
Version:1.0 StartHTML:000000223 EndHTML:000097520 StartFragment:000038525 EndFragment:000097417 StartSelection:000038559 EndSelection:000097381 SourceURL:https://classes.areteem.org/mod/quiz/review.php?attempt=7397 Lecture 3 Quick Response Quiz and Practice Problems
Question 3.30:
Use the following outline to prove Bezout's Identity.
(a) There are positive integers of the form j=am+bnj=am+bn .
(b) If there are positive integers of the form j=am+bnj=am+bn there is a smallest positive integer ee of the form e=a′m+b′ne=a′m+b′n for integers a′,b′a′,b′ .
(c) Use the division algorithm to show that ee divides both mm and nn .
(d) Show that gcd(m,n)gcd(m,n) must divide ee , hence e=gcd(m,n)e=gcd(m,n) .
Feedback
Step (a) is clear.
Step (b) is also intuitive, but is actually a fairly strong principle (usually referred to as the well-order principle of the natural numbers).
For step (c), let ee be as in step (b). By the division algorithm, we can write m=q⋅e+rm=q⋅e+r for 0≤r<e0≤r<e . Note, however, that if r>0r>0 , then r=m−q⋅e=m−q⋅(a′m+b′n)=(a′q−1)m+b′n<er=m−q⋅e=m−q⋅(a′m+b′n)=(a′q−1)m+b′n<e which contradicts the fact that ee was the smallest number of the form am+bnam+bn . Hence r=0r=0 and so e∣me∣m . An identical argument shows e∣ne∣n .
For step (d), first note gcd(m,n)∣m,gcd(m,n)∣ngcd(m,n)∣m,gcd(m,n)∣n by definition, so gcd(m,n)∣a′m+b′n=egcd(m,n)∣a′m+b′n=e . Using step (c) we know e∣m,e∣ne∣m,e∣n so e∣gcd(m,n)e∣gcd(m,n) . Thus, e=gcd(m,n)e=gcd(m,n) as needed.
How did you get " m−q⋅(a′m+b′n)=(a′q−1)m+b′n"?
Thanks
The solution should say instead $$\begin{aligned} r &= m - qe \\ &=m - q(a'm + b'n) \\ &= (1-qa')m + (-qb')n < e \end{aligned}$$
Note the main point in this part of the proof is that if $r > 0$, there is a number of the form $am + bn$ that is smaller than $e$, but $e$ was supposed to be the smallest. Thus, $r = 0$ and $e | m$.
Social networks