### Demo 2
Prove: $$\gcd(a,\gcd(b,c)) = \gcd(\gcd(a,b),c)$$
### Notes
- LHS|a
- LHS|gcd(b,c)|c
LHS is the _greatest_ number which divides both.
etc
Idea: prove LHS<=RHS and RHS<=LHS. Show LHS<=RHS by showing LHS is _some_ common divisor of gcd(a,b) and c
Lemma 2a: If a | b and b | c then a | c
### Proof
Fix integers $$a,b,c$$. By the definition of gcd, $$\gcd(a,\gcd(b,c)) \mid \gcd(b,c)$$, and also $$\gcd(b,c)$$ is a divisor of $$b$$ and $$c$$. Then by Lemma 2a, $$\gcd(a,\gcd(b,c))$$ is a divisor of $$b$$ and $$c$$.
Next, since $$\gcd(a,\gcd(b,c))$$ divides both $$a$$ and $$b$$, by Demo 1's lemma, it divides $$\gcd(a,b)$$.
Then, since $$\gcd(a, \gcd(b,c))$$ is a common divisor of $$c$$ and $$\gcd(a,b)$$, it must be no greater than their _greatest_ common divisor, so $$\gcd(a,\gcd(b,c)) \le \gcd(\gcd(a,b),c)$$.
Next, we need to show $$\gcd(a,\gcd(b,c)) \ge \gcd(\gcd(a,b),c)$$. [Proof is similar and left as an exercise]
Finally, $$\gcd(a,\gcd(b,c)) \le \gcd(\gcd(a,b),c)$$ and $$\gcd(a,\gcd(b,c)) \ge \gcd(\gcd(a,b),c)$$, and so $$\gcd(a,\gcd(b,c)) = \gcd(\gcd(a,b),c)$$.