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:

$\displaystyle \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): For the proof of this part, we shall use a result which will not be proven until later in this chapter. Assume $ a\vert bc$. Let $ d=gcd(a,b)$. By the Euclidean algorithm (Theorem 1.4.3 below), 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:

$\displaystyle \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:

$\displaystyle 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$

Exercise 1.2.17   Find $ gcd(24,78)$ and $ lcm(24,78)$ and verify that their product is $ 24\cdot 78$.

Exercise 1.2.18   Find all integers $ d>0$ such that $ 12 \mid d$ and $ d \mid 260$.

Exercise 1.2.19   Find $ q$ and $ r$ guaranteed by the division algorithm for $ a=28$ and $ b=160$.

Exercise 1.2.20   Show that if $ a=bq+r$ then $ gcd(a,b)=gcd(r,b)$.

Exercise 1.2.21   Prove the claim in the first proof of the division algorithm, theorem 1.2.7.

Exercise 1.2.22   For any integer $ n$, prove that:

(a) $ 2$ divides $ n(n+1)$,

(b) $ 3$ divides $ n(n+1)(n+2)$.

Exercise 1.2.23   Prove that if $ d=gcd(a,b)$ then $ gcd(\frac{a}{d},\frac{b}{d})=1$. (In other words, $ \frac{a}{d}$ and $ \frac{b}{d}$ are relatively prime.)

Exercise 1.2.24   Show that for any integers $ m$ and $ n$, $ gcd(a,b)$ divides $ ma+nb$.

Exercise 1.2.25   Prove that every square integer is of the form $ 4k$ or $ 4k+1$, where $ k$ is an integer.

Exercise 1.2.26   Prove that $ 4$ does not divide $ n^2+2$, for any integer $ n$.

Exercise 1.2.27   Prove that if $ 3$ does not divide an odd integer $ n$, then 24 divides $ n^2-1$.

Exercise 1.2.28   Find

(a) $ lcm(6,21)$,

(b) $ lcm(10,15)$,

(c) $ gcd(99,100)$.

(d) $ gcd(24,78)$,

(e) $ lcm(24,78)$.

Exercise 1.2.29   Suppose $ a>1$ is an odd integer. Find a formula for $ lcm(a,a+2)$.

Suppose $ a>1$ is an even integer. Find a formula for $ lcm(a,a+2)$.

Exercise 1.2.30   Verify that (6) in Proposition 1.2.16 is true.

Exercise 1.2.31   Verify that (8) in Proposition 1.2.16 is true.

Exercise 1.2.32   Verify that (9) in Proposition 1.2.16 is true.

Exercise 1.2.33   Suppose $ a>1$ is an integer. Find $ gcd(a,a+1)$.

Exercise 1.2.34   Suppose $ a>1$ is an odd integer. Find $ gcd(a,a+2)$.

Suppose $ a>1$ is an even integer. Find $ gcd(a,a+2)$.

Exercise 1.2.35 (a)   Find $ gcd(51,15)$.

(b) Find $ gcd(51,105)$.

(c) Find $ gcd(501,105)$.

Exercise 1.2.36   Let \begin{displaymath}\left( \begin{array}{c} n \ k \end{array}\right)={n!\over k!(n-k)!}\end{displaymath} denote the combinatorial symbol $ n$ choose $ k$ (also called a binomial coefficient), where $ m!=1\cdot 2\cdot ... \cdot m$ is $ m$ factorial. This is the coefficient of $ x^ky^{n-k}$ in the binomial expansion of $ (x+y)^n$,

\begin{displaymath} (x+y)^n=x^n+\left( \begin{array}{c} n \ 1 \end{array}\righ... ...ft( \begin{array}{c} n \ n-1 \end{array}\right)x^{n-1}y+y^n. \end{displaymath}

These can be computed by hand using Pascal's triangle,

$\displaystyle 1 $

$\displaystyle 1 \ \ \ \ \ \ 1 $

$\displaystyle 1 \ \ \ \ \ \ 2 \ \ \ \ \ \ 1 $

$\displaystyle 1 \ \ \ \ \ \ 3 \ \ \ \ \ \ 3 \ \ \ \ \ \ 1 $

$\displaystyle 1 \ \ \ \ \ \ 4 \ \ \ \ \ \ 6 \ \ \ \ \ \ 6 \ \ \ \ \ \ 4 \ \ \ \ \ \ 1 $

$\displaystyle 1 \ \ \ \ \ \ 5 \ \ \ \ \ \ 10 \ \ \ \ \ \ 10 \ \ \ \ \ \ 5 \ \ \ \ \ \ 1 $

$\displaystyle 1 \ \ \ \ \ \ 6 \ \ \ \ \ \ 15 \ \ \ \ \ \ 20 \ \ \ \ \ \ 15 \ \ \ \ \ \ 6 \ \ \ \ \ \ 1 $

$\displaystyle ... $

Check \begin{displaymath}5\vert \left( \begin{array}{c} 5 \ k \end{array}\right)\end{displaymath}, for $ k=1,2,3,4$.

Exercise 1.2.37   Factor all the integers $ 100,101,102,103,104,105$.

Exercise 1.2.38   Show that \begin{displaymath}7\vert \left( \begin{array}{c} 7 \ k \end{array}\right)\end{displaymath}, for $ k=1,2,3,4,5,6$. Show that \begin{displaymath}11\vert \left( \begin{array}{c} 11 \ k \end{array}\right)\end{displaymath}, for $ k=1,2,...,10$. Is there some $ k=1,2,...,8$ such that \begin{displaymath}9\vert \left( \begin{array}{c} 9 \ k \end{array}\right)\end{displaymath}?


David Joyner 2007-09-03