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

4 Greatest Common Divisor, least common multiple and Euclidean Algorithm

  1. Last updated
  2. Save as PDF
  • Page ID
    7529

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    • 4.1 Greatest Common Divisor
      The greatest common divisor of two integers, also known as GCD, is the greatest positive integer that divides the two integers.
    • 4.2 Euclidean algorithm and Bezout's algorithm
      The Euclidean Algorithm is an efficient way of computing the GCD of two integers. It was discovered by the Greek mathematician Euclid, who determined that if n goes into x and y, it must go into x-y. Therefore, we can subtract the smaller integer from the larger integer until the remainder is less than the smaller integer. We continue using this process until the remainder is 0, thus leaving us with our GCD.
    • 4.3 Least Common Multiple
      The least common multiple , also known as the LCM, is the smallest number that is divisible by both integer a and b.
    • 4.4 Relatively Prime numbers
    • 4.E: Exercises