### Demo 1
Prove: If $$d \mid e$$ and $$d \mid f$$ then $$d \mid \gcd(e,f)$$.

### Notes
- d|e means e=md for some int m
- gcd(e,f) is largest number which divides both e and f
- Lemma 2b: If a | b and a | c then a | bx + cy
- (Bézout’s Lemma). Let a, b be non-zero integers. Then there
exist integers x, y such that ax + by = gcd(a, b)

### Proof
Fix $$d,e,f$$, and assume (towards a direct proof) $$d \mid e$$ and $$d \mid f$$. Then we know by Bezout's Lemma that there is some $$x,y$$ where $$\gcd(e,f)=ex+fy$$. By Lemma 2b, $$d \mid ex+fy$$, so $$d \mid \gcd(e,f)$$.

### Proof (without using Lemma 2b)
Fix $$d,e,f$$, and assume (towards a direct proof) $$d \mid e$$ and $$d \mid f$$. Then we need to show $$d \mid \gcd(e,f)$$. By definition, $$e=md$$ and $$f=nd$$ for some integers $$m,n$$. By Bezout's Lemma, $$\gcd(e,f)=ex+fy$$ for some integers $$x,y$$.

$$\gcd(e,f)=ex+fy=(md)x+(nd)y=d(mx+ny)$$

$$(mx+ny)$$ is an integer because it is a sum of products of integers. Thus, $$d \mid \gcd(e,f)$$.