To prove: If $c \mid a$ and $c \mid b$, then $c \mid d$, where $d = \gcd(a, b)$.

---

Proof:

1. Definition of $\gcd(a, b)$:

By definition, the greatest common divisor $d$ of $a$ and $b$ satisfies: $d = \gcd(a, b) = \text{largest integer that divides both } a \text{ and } b.$ Thus: $d \mid a \quad \text{and} \quad d \mid b.$

2. Assumptions:

It is given that: $c \mid a \quad \text{and} \quad c \mid b.$ This means there exist integers $k_1$ and $k_2$ such that: $a = k_1 c \quad \text{and} \quad b = k_2 c.$

3. Expressing $d$ as a linear combination:

The $\gcd(a, b)$ can always be written as a linear combination of $a$ and $b$: $d = p a + q b,$ for some integers $p$ and $q$.

Substituting $a = k_1 c$ and $b = k_2 c$ into this equation: $d = p (k_1 c) + q (k_2 c).$

Factoring $c$ out: $d = c (p k_1 + q k_2).$

4. Conclusion:

Since $p k_1 + q k_2$ is an integer, we have: $c \mid d.$

Thus, $c \mid d$, as required.

---

Key Points in the Proof:

1. $d$ divides both $a$ and $b$, so it can be expressed in terms of them.
2. $c$ dividing $a$ and $b$ implies that $c$ divides any integer linear combination of $a$ and $b$.
3. Using the linear combination property of the $\gcd$, we conclude that $c \mid d$.

---

Do you want further clarification or a numerical example?

Questions to Deepen Understanding:

1. What are some examples of $a, b, c,$ and $d$ that satisfy this property?
2. Can you extend this proof to more than two integers (e.g., $\gcd(a, b, c)$)?
3. Why is the linear combination property of $\gcd$ critical in this proof?
4. How does this proof depend on $c$ being a divisor of both $a$ and $b$?
5. What happens if $c$ does not divide $a$ or $b$?

Tip:

To test divisibility-related proofs, always try substituting numerical examples to verify each logical step.