GCD: Greatest Common Divisor

AKA: Euclid has been dominant for millenia...

Dense roadmap:

• Division number theory style: $$ \forall a,b \in \mathbb{Z} ~ \exists q,r ~\mbox{s.t.}~ a = q \cdot b + r ~\mbox{where}~ r \in {0, \ldots, b-1} $$
• We say \(b | a\) (read: \(b\) divides \(a\)) iff there exists some \(k\) such that \(a = b \cdot k \)
• If \(n | a\) and \(n | b\) then \(n | (s \cdot a + t \cdot b)\) for every \(s,t \in \mathbb{Z}\)
• The \( \gcd(a,b)\) is the largest common divisor of \(a\) and \(b\)
• Let \(d = \gcd(a,b)\) then \(d = \min(\{ a \cdot s + b \cdot t \ge 0 ~ \forall ~ s,t \in \mathbb{Z} \})\)
• If \(n | a\) and \(n | b\) then \(n | \gcd(a,b)\)
• For intuition just think of two even numbers, no matter how you combine them you'll have an even number. If you can combine them and try to get to something as small as possible that number is their GCD, which is definitely divisible by 2.
• Also for intuition look at the animated gif
• We say \(a\) and \(b\) are co-prime when \(\gcd(a,b) = 1\)
• When working with GCD in practice write down stuff like \(d = a \cdot s + b \cdot t\) and start working the math

OK the Euclidean Algorithm and Extended Euclidian Algorithm:

GCD Competition: Find me two three digit numbers where that thing calls itself as many times as you can manage.

Let's talk the WORST CASE for GCD

Let's implement an Extended Euclidean Algorithm (xgcd)

Let's talk inverse modulo \(n\)?