Wednesday, July 11, 2018

Least Common Multiple

We can use prime factorization to find the smallest common multiple of two positive integers.

Definition 1. The least common multiple (l.c.m.) of two positive integers is the smallest positive integer that is a multiple of both. We denote the least common multiple of two positive integers a an b by [a, b] .

Example:
  • [2, 8] = 8
  • [5, 8] = 40
We can figure out a, b once we have the prime factorization of a and b. To do that, let
$a = {p_1}^{a_1} {p_2}^{a_2} ... {p_m}^{a_n}$ and $b = {p_1}^{b_1} {p_2}^{b_2} ... {p_m}^{b_n}$, where (as above) we exclude any prime with 0 power in both a and b. Then
$[a,b]= {p_1}^{max (a_1,b_1)} {p_2}^{max(a2,b2)} ... {p_m}^{max(a_n,b_n)}$, where $max(a, b)$  is the maximum of the two integers $a$ and $b$.


We now prove a theorem that relates the least common multiple of two positive integers to their greatest common divisor. In some books, this theorem is adopted as the definition of the least common multiple. To prove the theorem we present a lemma:

Lemma 1. If a and b are two real numbers, then $min(a, b) + max(a, b) = a + b$

Proof. Assume without loss of generality that $a \ge b$. Then $max(a, b) = a$ and $min(a, b) = b$, and the result follows.

Theorem 1. Let a and b be two positive integers. Then

  1. $[a, b] \ge 0$;
  2. $[a, b] = \frac{ab}{(a, b)} $; where $(a,b)$ is GCD of a and b.
  3. If $a | m$ and $b | m$, then $[a, b] | m$

close
CLOSE to read Least Common Multiple !

0 komentar

Post a Comment

Equation Calculator Site