Many ideas in number theory can be interpreted profitably in terms of prime factorizations. For example, the gcd of two numbers depends directly and simply on their factorizations, and this approach gives us significant new information.

Theorem 3.6.1 Suppose $n$ and $m$ are positive integers, with prime factorizations $n = p_1^{i_1}p_2^{i_2}\cdots p_k^{i_k}$ and $m = p_1^{j_1}p_2^{j_2}\cdots p_k^{j_k}$, where the $p_i$ are distinct and the exponents are non-negative. Then:

a) A positive integer $d=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is a common divisor of $n$ and $m$ if and only if $$ e_1\le \min \{i_1,j_1\}, e_2\le \min \{i_2,j_2\},\ldots, e_k\le \min \{i_k,j_k\}. $$

b) $\displaystyle (n,m)= p_1^{\min \{i_1,j_1\}}p_2^{\min \{i_2,j_2\}}\cdots p_k^{\min \{i_k,j_k\}}. $

c) Any common factor of $n$ and $m$ divides $(n,m)$.

**Proof.**
Although the notation is admittedly rather formidable, this
result is a simple consequence of theorem 3.5.2, which says that one number divides another if and only if the
primes in the factorization of the first are present to lower powers
than those in the second. So if $d$ divides both $n$ and $m$ then any
prime in its factorization must occur less often than it occurs in
either the factorization of $n$ or the factorization of $m$; this is
just what (a) says. Now to get the largest possible common factor, we
clearly should choose the largest exponent possible for each prime,
which is exactly what (b) says. Finally, (c) follows immediately from
(a), (b) and theorem 3.5.2.$\qed$

You may have used the algorithm implied by (b) to compute gcd's in the past. Recall that we have seen (c) before, in exercise 6 of section 3.3.

We define now another number which is `dual' to the gcd.
If $m$ and $n$ are positive numbers, we let $[m,n]$ or $\lcm(m,n)$
denote their **least common multiple**, or "lcm'', that is, the smallest positive
number that is a multiple of both $m$ and $n$.
There is an obvious similarity
between theorem 3.6.1 and the following
result.

Theorem 3.6.2 Suppose $n$ and $m$ are positive integers, with prime factorizations $n = p_1^{i_1}p_2^{i_2}\cdots p_k^{i_k}$ and $m = p_1^{j_1}p_2^{j_2}\cdots p_k^{j_k}$, where the $p_i$ are distinct and the exponents are non-negative. Then:

a) A positive integer $s=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is a common multiple of $n$ and $m$ if and only if $$ e_1\ge \max \{i_1,j_1\}, e_2\ge \max \{i_2,j_2\},\ldots, e_k\ge \max \{i_k,j_k\}. $$

b) $\displaystyle [n,m]= p_1^{\max \{i_1,j_1\}}p_2^{\max \{i_2,j_2\}}\cdots p_k^{\max \{i_k,j_k\}}. $

c) $[n,m]$ divides any common multiple of $n$ and $m$.

**Proof.**
Entirely analogous to the proof of theorem 3.6.1.$\qed$

The following consequence of the last two results is perhaps a bit surprising, although it is not hard to prove.

**Proof.**
Suppose
$n =p_1^{i_1}p_2^{i_2}\cdots p_k^{i_k}$ and
$m =p_1^{j_1}p_2^{j_2}\cdots p_k^{j_k}$;
then
$$nm= p_1^{i_1+j_k}p_2^{i_2+j_2}\cdots p_k^{i_k+j_k}
$$
and
$$\eqalign{
(n,m)\cdot [n,m] &= p_1^{\min \{i_1,j_1\}+\max \{i_1,j_1\}}
p_2^{\min \{i_2,j_2\}+\max \{i_2,j_2\}}\cdots\cr
&\qquad\qquad \cdots p_k^{\min \{i_k,j_k\}+\max \{i_k,j_k\}}.\cr}
$$
These are equal because
$i+j = \min \{i,j\} + \max \{i,j\}$.$\qed$

Example 3.6.4 Let $m=4$ and $n=6$. Then it is easy to see that $(4,6)=2$ and $[4,6]=12$, and $2\cdot 12 = 4\cdot 6$. $\square$

## Exercises 3.6

**Ex 3.6.1**
If $a=2\cdot 3^2\cdot 7^3\cdot 13^4$ and $b=2^5\cdot
3^2\cdot 5\cdot 7^2\cdot 11^3$, find $(a,b)$, $[a,b]$ and $ab$.

**Ex 3.6.2**
Suppose $p$ is a prime, $(a, p^3)=p^2$ and $(b, p^3)=
p$. Find $(a+b, p^3)$.

**Ex 3.6.3**
Suppose $a> 0$, $(a, 42)=6$ and $[a, 42]= 420$. Find $a$.

**Ex 3.6.4**
Show $(na,nb)=n(a,b)$ and $[na,nb]=n[a,b]$.

**Ex 3.6.5**
Show that $a$ and $b$ are relatively prime if and only if $ab=[a,b]$.

**Ex 3.6.6**
Let $d=(a,b)$. Show that there exist $d_1$, $d_2$ such that $d=d_1d_2$
and $(a/d_1,b/d_2)=1$.

**Ex 3.6.7**
Show $(a^2,b^2)=(a,b)^2$.

**Ex 3.6.8**
Suppose $g$ and $L$ are positive integers. Show that
there are integers $a$ and $b$ with $(a,b)=g$ and $[a,b]=L$ if and only if
$g\vert L$.

**Ex 3.6.9**
Suppose $[a,b]=a^2$. What can you conclude?

**Ex 3.6.10**
Prove theorem
3.6.2.

**Ex 3.6.11**
In the proof of 3.6.3 we said, "These are
equal because $i+j = \min \{i,j\} + \max \{i,j\}$.'' Explain carefully
why this is true; pay attention to the case that $i=j$.