Proposition 6 • Statement ○ If a,b∈Z, then (a,b) exists • Proof ○ By Proposition 5, we may assume b≠0 ○ Choose q,r∈Z s.t. a=bq+r, where 0≤r |b| ○ We argue by induction on r ○ Inductive hypothesis § If a′,b′∈Z s.t. b^′≠0, and a′=b′ q′+r′, where 0≤r^′ r § Then (a′,b′) exists ○ Base case § Suppose r=0, then a=bq § We have ├ |b|┤|├ a┤ and ├ |b|┤|├ b┤ § If e∈Z s.t. e|a and e|b, then ├ e┤|├ |b|┤ § Therefore (a,b) exists, and is |b| ○ Inductive step § Suppose r 0 § Choose q′,r′∈Z s.t. b=q^′ r+r′, where 0≤r^′ r § By induction, (b,r) exists § By Proposition 4, (a,b) exists, and euqals (b,r) The Euclidean Algorithm • Input ○ a,b∈Z with |b|≤|a| • Output ○ (a,b) • Algorithm (0) If b=0, output |a| Else, proceed to step (1) (1) If b≠0, find q,r∈Z s.t. a=bq+r, where 0≤r |b| (2) If r=0, output |b| Otherwise, repeat step (1) with b and r playing the roles of a and b • Note ○ The algorithm terminates ○ Since the remainder decreases at each application of step (1) ○ By Proposition 4, the output will be (a,b) • Example: use the Euclidean Algorithm to compute (4148, 2057) ○ Take a=4148, b=2057 ○ ⏟4148┬a=⏟2057┬b×⏟2┬q+⏟34┬r ○ ⏟2057┬a=⏟34┬b×⏟60┬q+⏟17┬r ○ ⏟34┬a=⏟17┬b×⏟2┬q+⏟0┬r ○ Here r=0, so the algorithm terminates ○ Thus, (4148, 2057)=17 Proposition 7 • Statement ○ If a,b∈Z, then ∃x,y∈Z s.t. (a,b)=ax+by • Note ○ x,y need not to be unique • Proof ○ If a=b=0 § We may take x=y=0 § In fact, any pair of (x,y) works ○ If a=0 or b=0 § Without loss of generality, assume b=0 § Then (a,b)=|a|=±a+b § Take x=±1, y=1 ○ If a≠0 and b≠0 § Without loss of generality, assume |a|≥|b| § Choose q,r∈Z s.t. a=qb+r, where 0≤r |b| § We argue by induction on r § Base case □ Suppose r=0, then (a,b)=|b|=0⋅a+(±1)⋅b □ So take x=0, y=±1 § Inductive step □ Suppose r 0 □ Choose q′,r′∈Z s.t. b=q^′ r+r^′, where 0≤r^′ r □ By induction, ∃x′,y′∈Z s.t. (b,r)=bx′+ry′ □ Thus, by Proposition 4 □ (a,b)=(b,r)=bx^′+(a−bq) y′=ay′+b(x^′−qy′) □ Take x=y′ and y=x′−qy′ • Example: express (4148, 2057) as 4148x+2057y where x,y∈Z ○ Recall when we computed (4148, 2057), we had § 4148=2057×2+34 § 2057=34×60+17 § 34=17×2+0 ○ Let s now find x,y∈Z s.t. (4148, 2057)=17=4148x+2057y ○ Start with the second to last equation, and “back-fill” § 17=2057−34×60 § =2057−(4148−2×2057)×60 § =4148×(−60)+2057×121 ○ Therefore x=−60, y=121
