View source for SP20:Lecture 15 GCD algorithm

We finished the proof that the [[base b representation]] exists.  We also discussed [[base b arithmetic]].  Finally we introduced [[Euclid's GCD algorithm]], and listed the properties we need to prove to justify calling it the [[greatest common divisor]].

* [[FA18:Lecture 14 Base b|Last semester's notes]]
* [[Media:sp20-lec15-slides.pdf|slides]]

= Base b representation =

We started this lecture by further discussion of [[base b representation]], which we started last lecture.  Recall that the [[base b interpretation]] of a [[sequence notation|sequence]] of [[digit]]s is:

{{Definition:Base b interpretation}}

== Existence ==

{{:Proof:Base b representation}}

== Uniqueness ==

{{:Proof:The base b representation is unique}}

== Arithmetic in base b ==

{{:Base b arithmetic}}

= GCD algorithm =

{{:Euclid's GCD algorithm}}