$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 6.2: GCD, LCM and Prime factorization

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

We have already discussed GCD and LCM in chapter 4. In this section, we will explore another method for finding GCD and LCM using prime factorization. In this method, we must find the prime factorization of the given integers first.

Example $$\PageIndex{1}$$

Determine $$gcd( 3^9, 3^8)$$  and  $$lcm( 3^9,3^8)$$.

Solution

$$gcd( 3^9 3^8)= 3^8$$  (the lowest powers of all prime factors that appear in both factorizations)  and  $$lcm( 3^9,3^8)=3^9$$  (the largest powers of each prime factors that appear in factorizations).

Example $$\PageIndex{2}$$

Determine $$gcd( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)$$  and  $$lcm( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)$$.

Solution

$$gcd( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)= 2^4 \times 3^8$$ (the lowest powers of all prime factors that appear in  both factorizations)  and  $$lcm( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)= 2^6 \times 3^9 \times 5^2$$  (the largest powers of each prime factors that appear in factorizations).

Example $$\PageIndex{3}$$

Find $$gcd(3915, 825)$$ and $$lcm(3915, 825).$$

Solution

Since $$3915 = 3^3 \times 5 \times 29$$ and $$825 = 3\times 5^2 \times 11$$,  $$gcd(3915, 825)= 3 \times 5$$  and $$lcm(3915, 825)= 3^3 \times 5^2 \times 11 \times 29.$$

Example $$\PageIndex{4}$$

Find $$gcd(2420, 230)$$ and $$lcm(2420, 230).$$

Solution

Since $$2420 = 2^2 \times 5 \times 11^2$$ and $$230 = 2 \times 5 \times 23$$,  $$gcd(2420, 230)= 2 \times 5$$  and $$lcm(2420, 230)= 2^2 \times 5 \times 11^2 \times 23.$$