Real Numbers: HCF and LCM

Euclid's division algorithm

To find the HCF of two positive integers $a$ and $b$ (with $a > b$), repeatedly apply $a = bq + r$ where $0 \le r < b$, replacing $a$ and $b$ with $b$ and $r$ each time, until the remainder is 0. The divisor at that final step is the HCF.

Worked example: HCF by Euclid's algorithm

Find the HCF of 867 and 255.

Solution: Since $867 > 255$:

As the remainder is now 0, the HCF of 867 and 255 is 51.

Worked example: a proof using the division lemma

Show that any positive odd integer is of the form $6q+1$, $6q+3$, or $6q+5$, for some integer $q$.

Solution: Euclid's division lemma says any positive integer $a$ can be written as $a = 6q+r$ for some $q$, where $0 \le r < 6$, so $a$ is one of $6q, 6q+1, 6q+2, 6q+3, 6q+4, 6q+5$.

Of these six forms, $6q$, $6q+2$, and $6q+4$ are all even, since every term is a multiple of 2. That leaves exactly $6q+1$, $6q+3$, and $6q+5$ as the only forms an odd integer can take.

HCF and LCM by prime factorization

Break both numbers into prime factors. The HCF is the product of the smallest power of each common prime factor; the LCM is the product of the greatest power of every prime factor that appears in either number. For any two positive integers, these always satisfy:

Worked example: HCF, LCM, and verification

Find the HCF and LCM of 336 and 54, and verify the relationship above.

Solution: Prime factorizing both numbers:

The HCF takes the lowest power of each shared prime ($2^1$ and $3^1$), and the LCM takes the highest power of every prime seen:

Verification: $\text{HCF} \times \text{LCM} = 6 \times 3024 = 18144$, and $336 \times 54 = 18144$ too, so the relationship holds.