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$.