Skip to main content
\(\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

6.2: GCD, LCM and Prime factorization

  • Page ID
    7593
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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.\)