What is Least common multiple? — Mathematics

Definition 6.10 University Mathematics — Year 1 · Chapter 6 — Integer Arithmetic

$\operatorname{lcm}(a, b)$ is the generator in $\N$ of the subgroup $a\Z \cap b\Z$ : it is a common multiple of $a$ and $b$ that divides every common multiple, and for $a, b \in \N^*$ ,

\gcd(a,b) \times \operatorname{lcm}(a,b) = ab \qquad (\text{proof in } \text{Exercise 6.5}).

Examples

Example 6.11 (Alignment problems are lcm problems)

Two meshed gears have $84$ and $36$ teeth. After how many teeth of common motion do they return to their initial position together? The configuration repeats when the number of elapsed teeth is a common multiple of $84$ and $36$ ; the first time is

\operatorname{lcm}(84, 36) = \frac{84 \times 36}{\gcd(84, 36)} = \frac{3024}{12} = 252

teeth — that is, $3$ turns of the large gear and $7$ of the small one ( $252/84$ and $252/36$ ). Note the practical route: compute the gcd first (Euclid: $84 = 2\times36 + 12$ , $36 = 3\times12$ ), then divide — never build the lcm by listing multiples. Every periodic-coincidence question (gears, planetary alignments, repeating decimals meeting) reduces to this one computation.

Read in context →

Examples

Related terms