EKUB, the greatest common divisor, and EKUK, the least common multiple: rules, the Euclidean algorithm, and examples

EKUB (greatest common divisor) is used to reduce fractions, while EKUK (least common multiple) is used to find a common denominator or the next time recurring events occur together. For positive natural numbers, EKUB is formed from the lowest powers of the common prime factors, while EKUK is formed from the highest powers of all the prime factors.

Below are definitions, prime factorization, the Euclidean algorithm, worked examples, and a method for checking your answer independently.

What are EKUB, the greatest common divisor, and EKUK, the least common multiple?

The definitions are simple:

• $\text{EKUB}(a;\,b)$ is the greatest natural number that divides both positive natural numbers $a$ and $b$ without remainder.
• $\text{EKUK}(a;\,b)$ is the least positive natural number that is divisible by both positive natural numbers $a$ and $b$ without remainder.

For example, $\text{EKUB}(8;\,12) = 4$: the common divisors of 8 and 12 are $1$, $2$, and $4$, and the greatest is 4. $\text{EKUK}(8;\,12) = 24$: 24 is divisible by both 8 and 12 and is the smallest such number.

For positive natural numbers $a$ and $b$, there is a very useful relationship:

$\text{EKUB}(a;\,b) \cdot \text{EKUK}(a;\,b) = a \cdot b$

This formula is an excellent way to check your answer: if the product of the calculated EKUB and EKUK does not equal $a \cdot b$, there is an error somewhere.

The basic rule: prime factorization

The most general method is to express each number as a product of prime factors. To do this, divide the number successively, starting with the smallest prime number. Then apply two simple rules:

1. For EKUB, take only the prime factors present in both factorizations (the common factors) and use the lowest power of each.
2. For EKUK, take all the prime factors appearing in the factorizations and use the highest power of each.

A convenient way to remember this: EKUB means "intersection", that is, only the shared part; EKUK means "union", that is, everything, but without unnecessary repetition. For positive natural numbers, EKUB cannot exceed the smaller number, while EKUK cannot be less than the larger one.

Worked examples and solutions

Example 1 - Find $\text{EKUB}(48;\,36)$ and $\text{EKUK}(48;\,36)$.

Solution. Find the prime factorization of each number: $48 = 2^4 \cdot 3$ and $36 = 2^2 \cdot 3^2$.

The common prime factors are 2 and 3. Their lowest powers are $2^2$ and $3^1$. Therefore, $\text{EKUB}(48;\,36) = 2^2 \cdot 3 = 12$.

For EKUK, take the highest powers: $2^4$ and $3^2$. Therefore, $\text{EKUK}(48;\,36) = 2^4 \cdot 3^2 = 16 \cdot 9 = 144$.

Check: $12 \cdot 144 = 1728$ and $48 \cdot 36 = 1728$. The results match, so the answer is correct.

Example 2 - (practical problem). A bus on the first route leaves the stop every 45 minutes, and a bus on the second route leaves every 60 minutes. They left together at 9:00. When will they next leave at the same time?

Solution. We need the shortest time interval that is a multiple of both 45 and 60, namely $\text{EKUK}(45;\,60)$. Find the prime factorizations: $45 = 3^2 \cdot 5$ and $60 = 2^2 \cdot 3 \cdot 5$. The highest powers are $2^2$, $3^2$, and $5$. Therefore, $\text{EKUK}(45;\,60) = 4 \cdot 9 \cdot 5 = 180$ minutes, or 3 hours. Answer: at 12:00.

Example 3 - (the Euclidean algorithm). Find $\text{EKUB}(1071;\,462)$.

Solution. Finding the prime factorizations of large numbers takes a long time. In this case, the Euclidean algorithm is convenient: divide the larger number by the smaller one with remainder, then divide the divisor by that remainder and continue until the remainder is zero.

$1071 = 462 \cdot 2 + 147$

$462 = 147 \cdot 3 + 21$

$147 = 21 \cdot 7 + 0$

The last nonzero remainder is 21. Therefore, $\text{EKUB}(1071;\,462) = 21$. Indeed: $1071 = 21 \cdot 51$ and $462 = 21 \cdot 22$.

Example 4 - (with fractions). Express the fractions $\dfrac{5}{12}$ and $\dfrac{7}{18}$ with the least common denominator.

Solution. The least common denominator is $\text{EKUK}(12;\,18)$. Find the prime factorizations: $12 = 2^2 \cdot 3$ and $18 = 2 \cdot 3^2$. Therefore, $\text{EKUK}(12;\,18) = 2^2 \cdot 3^2 = 36$. Now multiply the numerator and denominator of each fraction by the appropriate factor: $\dfrac{5}{12} = \dfrac{15}{36}$ and $\dfrac{7}{18} = \dfrac{14}{36}$.

Independent practice

Find $\text{EKUB}(84;\,126)$ and $\text{EKUK}(84;\,126)$. Short answer: EKUB $42$, EKUK $252$. Check: $42\cdot252=84\cdot126=10\,584$.

Common mistakes

Confusing EKUB, the greatest common divisor, with the least common multiple. The words "greatest" and "least" in the names refer to the result's position among the common divisors or common multiples, not its size relative to $a$ or $b$. First determine whether the problem asks for a divisor or the time when recurring events happen together.

Assuming that "EKUK, the least common multiple, is the product of the two numbers". Writing $\text{EKUK}(8;\,12)$ as $96$ is incorrect: the correct answer is 24. The product equals the least common multiple only when the numbers are coprime, that is, when $\text{EKUB}(a;\,b) = 1$.

Choosing the powers the wrong way round. Taking the highest powers when calculating EKUB and the lowest powers when calculating the least common multiple is a common mechanical error. Remember the rule using the idea of "intersection and union".

Treating 1 as a prime number. 1 is not prime, so it does not appear in the prime factorization. The smallest prime number is 2.

Not checking the answer. Checking with the formula $\text{EKUB} \cdot \text{EKUK} = a \cdot b$ takes only a few seconds but can prevent an error in an exam.

Summary and next step

• For the greatest common divisor, take the lowest powers of the common prime factors.
• For the least common multiple, take the highest powers of all the prime factors that appear.
• For large numbers, the Euclidean algorithm may be faster than prime factorization.
• Check your answer using $\text{EKUB}\cdot\text{EKUK}=a\cdot b$.
• Continue learning how EKUB and EKUK are used with common fractions or take a test on the topic.