Proposition 2: The Division Algorithm • Statement ○ Let a,b∈Z, where b 0 ○ Then ∃!q,r∈Z s.t. a=qb+r, and 0≤r b • Proof (Existence) ○ Let S≔{a−bq│q∈Za−bq≥0}⊆Z(≥0) ○ S is not empty § Let q∈Z s.t. q≤a/b § Then bq≤a § ⇒0≤a−bq § i.e. a−bq∈S ○ Thus S contains a unique minumum elemtent: call it r ○ Choose q∈Z s.t. § a−bq=r § ⇒a=bq+r ○ We still need to show 0≤r b § We know 0≤r, since r∈S, so we just need to show r b § If r≥b, then a−b(q+1)=a−bq−b=r−b≥0 § But a−b(q+1)∈S, and it is less than r § This is impossible, since r is minimum element of S § Thus, r b ○ Therefore we ve proven the existence of q and r • Proof (Uniqueness) ○ Suppose ∃q,q′,r,r′∈Z s.t. § a=bq+r, where 0≤r b § a=bq′+r′, where 0≤r^′ b ○ We must show q=q′ and r=r^′ ○ Suppose r≠r^′ § Without loss of generality, assume r^′ r § Then 0 r′−r=(a−bq′ )−(a−bq)=b(q−q^′ ) § Thus, ├ b┤|├ (r^′−r)┤, but 0 r′−r≤r′ b. § This is impossible, thus r=r^′ ○ We have bq+r=bq′+r⇒q=q′ ○ Therefore we ve proven the uniqueness of q and r • Note we can prove the following stronger statement ○ If a,b∈Z, and b≠0, then ∃!q,r∈Z ○ s.t. a=bq+r, and 0≤r |b| • Proof (Existence) ○ Assume b 0 ○ Choose q,r∈Z s.t. a=(−b)q+r, and 0≤r −b ○ Then a=b(−q)+r, and 0≤r |b| ○ This proves existence • Proof (Uniqueness) ○ Assume b 0 ○ Suppose ∃q,q′,r,r′∈Z s.t. § a=bq+r, where 0≤r b § a=bq′+r′, where 0≤r^′ b ○ Then § a=(−b)(−q)+r, where 0≤r |b|=−b § a=(−b)(−q′)+r^′, where 0≤r^′ |b|=−b ○ Since −b 0, our previous result implies −q=−q^′ ○ ⇒q=q′ and r=r^′ Greatest Common Divisor • If a,b∈Z, where either a≠0 or b≠0 • A greatest common divisor of a and b is a positive integer d s.t. ○ d|a and d|b ○ If e∈Z s.t. e|a and e|b then e|d • We write the g.c.d. of a and b, if it exists, as (a,b) • As a convention (0,0)≔0 Proposition 3: Uniqueness of Greatest Common Divisor • Statement ○ Let a,b∈Z, where either a≠0 or b≠0 ○ Suppose ∃d,d^′∈Z( 0) s.t. (1) d and d′ both divide a and b (2) If e∈Z s.t. e|a and e|b, then e|d and e|d^′ ○ Then d=d^′ • Proof ○ Combining properties (1) and (2), we have d|d′ and d^′ |d ○ Choose q,q^′∈Z s.t. dq=d′ and d^′ q^′=d ○ By substitution, we get dqq^′=d ○ Then qq′=1⇒q=q′=±1 ○ If q=q^′=−1, then d=−d^′ 0. ○ This is impossible since d and d′ are both positive ○ Therefore q=q^′=1 and d=d^′ Proposition 4 • Statement ○ Suppose a,b∈Z, where b≠0 ○ Choose q,r∈Z s.t. a=qb+r, and 0≤r |b| ○ If (b,r) exists, then (a,b) exists and (a,b)=(b,r) • Proof ○ Set d≔(b,r) ○ d|a and d|b § Choose q_1,q_2∈Z s.t. dq_1=b and dq_2=r § Then a=qb+r=qq_1 d+q_2 d=d(qq_1+q_2 ), so d|a § And we already know d|b ○ If e∈Z s.t. e|a and e|b, then e|d § Let e∈Z s.t. e|a and e|b § Choose q_3,q_4∈Z s.t. eq_3=a and eq_4=b § a=qb+r § ⇒a−qb=r § ⇒eq_3−qeq_4=r § ⇒e(q_3−qq_4 )=r § Thus e|r § Since e|b and d=(b,r) § We can conclude that e|d ○ By Proposition 3, (a,b)=(b,r) Proposition 5 • Statement ○ (a,0)=|a|,∀a∈Z • Proof ○ If a=0 § This is true by our convention ○ If a≠0 § Certainly ├ |a|┤|├ a┤, and ├ |a|┤|├ 0┤ § If e∈Z s.t. e|a and ├ e┤|├ 0┤, then ├ e┤|├ |a|┤ § Therefore (a,0)=|a|
