Hi everyone,

On Tuesday we introduced the idea of greatest common divisor and we looked at several theorems about properties of the gcd.

Definition. The greatest common divisor of integers $a$ and $b$, denoted $\gcd(a,b)$, is the largest integer that divides both $a$ and $b$.

In your homework, you are asked to prove propositions that involve the gcd. It may help to keep the following in mind:

To prove that a number $x$ is the gcd of $a$ and $b$

We need to show two things:

1.  $x$ is a common divisor of $a$ and $b$ (that is, $x|a$ and $x|b$)

2.  if  $y|a$ and $y|b$, then $x\geq y$ (“if $y$ is a common divisor of $a$ and $b$, then $x\geq y$”

Here is an example, so we can see how it works in practice:

Proposition. If $a, b$ are integers then $\gcd(a,b) = \gcd(a+b,b)$.

VIDEO: Example – proof with gcd