Skip to main content
Mathematics LibreTexts

6.2: GCD, LCM and Prime factorization

  • Page ID
    7593
  • This page is a draft and is under active development. 

    \( \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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    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.\)


    6.2: GCD, LCM and Prime factorization is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by LibreTexts.

    • Was this article helpful?