A Sample of a Proof of a $\gcd$ Fact

Hello everyone. So in this video, I'd like to prove the following proposition. I didn't prove this in class, but I alluded to its truth. Now I'll actually demonstrate it.

Prove that if $d \mid a$ and $d\mid b$ then $d\mid\gcd(a,b)$

Proof

Now to start a question like this, it's perhaps kind of tough to know where to start; it really is. $d\mid a$ and $d\mid b$ doesn't really tell us too much, right? We need to use something about the $\gcd$ here in order to get the last division.

So we're going to start with the $\gcd$. I usually write a letter for the $\gcd$, just to make my life easier, and so that I don't have to write $\gcd$ a hundred times.

Let $e=\gcd(a,b)$.

Now what am I going to do? Well we have some hammers from class, so let's try to use one, and the one I'm going to use is Bezout's Lemma, so the back substitution.

By Bezout's Lemma, there exist integers $x$ and $y$ such that

$$e=ax+by$$

Alright so that's what Bezout's Lemma says. It says that you can write the $\gcd$ as a linear combination of $a$ and $b$. Okay, so now with this hammer in place, the proof is in good shape.

So now, let's actually use the hypothesis, which is $d\mid a$ and $d\mid b$.

Since $d\mid a$ and $d\mid b$, by Divisibility of Integer Combinations, we have

$$d\mid ax+by=e=\gcd(a,b)$$

Thus, $d\mid gcd(a,b)$

And that's it. A quick little theorem here. So here we didn't have to use too too much but we did use a combination of some of the hammers that we have: Bezout's Lemma and Divisibility of Integer Combinations. Those two things combined, take us home in this problem.

So again, it's tough to know where to start in a problem like this. Again sometimes it helps to look at the conclusion, sometimes it doesn't, it really just depends. But here since we want $d\mid\gcd(a,b)$, it makes sense to try to do something with the $\gcd(a,b)$, and what can we do? Well, back substitution, or Bezout's Lemma or whatever you want to call it, that gives us integers $x$ and $y$; we can get the ball rolling with that. Hopefully this has been enlightening. Thank you very much for your time. Good luck.