The greatest common divisor and least common multiple

In this section, we introduce two commonly used and useful notations in number theory, the greatest common divisor and least common multiple.

Definition 1.2.11   Let $a>0$ and $b>0$ be integers. The greatest common divisor of $a,b$ is the largest integer $d>0$ satisfying both $d\vert a$ and $d\vert b$. The greatest common divisor is denoted by either $gcd(a,b)$ or simply by $(a,b)$ when there is no ambiguity.

The greatest common divisor of $a$ and $b$ is simply the largest positive integer which divides both $a$ and $b$.

Definition 1.2.12   When $gcd(a,b)=1$ then we say that $a,b$ are relatively prime.

Example 1.2.13   $gcd(12,15)=3$, $gcd(3,5)=1$, $gcd(100,46)=2$.

To return to the question above, we now know that the set of all possible sums and differences of two integers $a>0$ and $b>0$ is of the form $c\mathbb{Z}$, for some $c>0$. What is $c$? This question is answered in the section on the Euclidean algorithm later in this chapter

As we saw above, the gcd is the largest integers which divides both $a$ and $b$. Somewhat analogous to this is the least integer which both $a$ and $b$ divide.

Definition 1.2.14   Let $a>0$ and $b>0$ be integers. The least common multiple of $a,b$ is the smallest integer $m>0$ satisfying both $a\vert m$ and $b\vert m$. The least common multiple is denoted by either $lcm(a,b)$ or sometimes simply by $[a,b]$ (also, $\{a,b\}$ is sometimes used).

Example 1.2.15   $lcm(12,15)=60$, $lcm(3,5)=15$, $lcm(100,46)=2300$.

The lcm can be computed from the gcd (which can be computed using the Euclidean algorithm) using the following fact.

Proposition 1.2.16   Let $a,b,c$ be integers.

(1)

$gcd(a,b)lcm(a,b)=ab$.

(2)

If $a\vert bc$ then $a\vert gcd(a,b)c$.

(3)

If $a\vert bc$ and $gcd(a,b)=1$ then $a\vert c$.

(4)

If $a\vert c$ and $b\vert c$ and $gcd(a,b)=1$ then $ab\vert c$.

(5)

$gcd(ab,c)=1$ if and only if $gcd(a,c)=1$ and $gcd(b,c)=1$.

(6)

If $c\vert a$ and $c\vert b$ then $c\vert gcd(a,b)$.

(7)

If $a\vert c$ and $b\vert c$ then $lcm(a,b)\vert c$.

(8)

If $d=gcd(a,b)$ then $gcd(a/d,b/d)=1$.

(9)

For any integers $m,n$ we have $gcd(a,b)\vert(ma+nb)$.

The reader can use the examples above to verify (1) in the cases $(a,b)=(12,15),(3,5),(100,46)$.

proof of (1): We will show that $\frac{ab}{(a,b)}=lcm(a,b)$. Note that $\frac{b}{(a,b)}\in \mathbb{Z}$, since $(a,b)$ divides $b$. Therefore, $a \cdot \frac{b}{(a,b)} \in \mathbb{Z}$.

Since $\frac{\frac{ab}{(a,b)}} {a}=\frac{b}{(a,b)} \in \mathbb{Z}$, we know that $\frac{ab}{(a,b)}$ is a multiple of $a$. Similarly, $\frac{\frac{ab}{(a,b)}}{b}=\frac{a}{(a,b)} \in \mathbb{Z}$ (why?) implies that $\frac{ab}{(a,b)} \geq lcm(a,b)$.

Now $\frac{ab}{lcm(a,b)} \in \mathbb{Z}$ (why?) and $\frac{a}{\frac{ab}{lcm(a,b)}}=\frac{lcm(a,b)}{b} \in \mathbb{Z}$ since $b$ divides $lcm(a,b)$. Therefore, $\frac{ab}{lcm(a,b)}$ divides $a$. Similarly, $\frac{ab}{lcm(a,b)}$ divides $b$. Thus:

$$\frac{ab}{lcm(a,b)} \leq (a,b) \quad {\rm i.e.,}\ \ \ \ \frac{ab}{(a,b)} \leq lcm(a,b).$$

Since we have shown the inequality in both directions, we must have equality. $\Box$

Later, part (1) of this proposition shall be proven again, but as a consequence of the Fundamental Theorem of Arithmetic.

We prove (2) below since it will be used in the proof of the Fundamental Theorem of Arithmetic.

proof of (2): Assume $a\vert bc$. Let $d=gcd(a,b)$. There are integers $x,y$ such that $ax+by=d$, so $acx+bcy=dc$. Since $a$ divides $acx$ and $bcy$ (by assumption), it divides $acx+bcy$, hence $a\vert gcd(a,b)c$. $\Box$

Part (4) shall also be proven later as a consequence of the Fundamental Theorem of Arithmetic. Parts (3), (6), (8), (9) are left as exercises.

proof of (7): We will prove this by contradiction. Suppose that $lcm(a,b) \nmid c$. Then $\frac{c}{lcm(a,b)}$ is not an integer, and we may write it as:

$$\frac{c}{lcm(a,b)}=q+\alpha, \quad {\rm where} \quad 0 < \alpha < 1 .$$

Multiplying both sides of the above inequality by the positive integer $lcm(a,b)$ gives: $c=q\cdot lcm(a,b)+ \alpha \cdot lcm(a,b)$. Let $r=c-q\cdot lcm(a,b)$. Then:

$$c=q\cdot lcm(a,b)+r, \quad {\rm with} \quad 0 < r < lcm(a,b).$$

But $a \mid r$ and $b \mid r$, so $r$ is a common multiple of $a$ and $b$ which is less than the least common multiple $lcm(a,b)$, by the above inequality. Thus we have reached a contradiction, and our original assumption was false. We conclude that $lcm(a,b) \mid c$. $\Box$