The Highest Common Factor, also called the Greatest Common Divisor,
is the largest positive integer that divides every number in a list exactly.
The Least Common Multiple is the smallest positive integer that is a multiple of every number in the list.
1. Highest Common Factor / Greatest Common Divisor
The HCF or GCD of numbers \(a,b,c,\ldots\) is written as
\[
\begin{aligned}
\gcd(a,b,c,\ldots).
\end{aligned}
\]
It is the largest number that divides all the given numbers with no remainder.
For example, the common factors of \(12\), \(18\), and \(30\) are \(1\), \(2\), \(3\), and \(6\).
Therefore,
\[
\begin{aligned}
\gcd(12,18,30)=6.
\end{aligned}
\]
2. Least Common Multiple
The LCM of numbers \(a,b,c,\ldots\) is written as
\[
\begin{aligned}
\operatorname{lcm}(a,b,c,\ldots).
\end{aligned}
\]
It is the smallest positive number that every original number divides exactly.
For \(12\), \(18\), and \(30\), the least common multiple is
\[
\begin{aligned}
\operatorname{lcm}(12,18,30)=180.
\end{aligned}
\]
3. Prime factorisation method
Every positive integer greater than \(1\) can be written as a product of prime powers:
\[
\begin{aligned}
n &= p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}.
\end{aligned}
\]
The prime factorisation method is the most visual way to understand HCF and LCM.
4. HCF from prime factors
To find the HCF:
- Factor every number into primes.
- Keep only the primes that appear in every number.
- For each common prime, choose the smallest exponent.
- Multiply those prime powers.
For example:
\[
\begin{aligned}
12 &= 2^2\cdot3,\\
18 &= 2\cdot3^2,\\
30 &= 2\cdot3\cdot5.
\end{aligned}
\]
The primes common to all three numbers are \(2\) and \(3\).
The smallest exponent of \(2\) is \(1\), and the smallest exponent of \(3\) is \(1\).
Therefore:
\[
\begin{aligned}
\mathrm{HCF}
&=2^1\cdot3^1\\
&=6.
\end{aligned}
\]
5. LCM from prime factors
To find the LCM:
- Factor every number into primes.
- Use every prime that appears in at least one number.
- For each prime, choose the largest exponent.
- Multiply those prime powers.
Using the same numbers:
\[
\begin{aligned}
12 &= 2^2\cdot3,\\
18 &= 2\cdot3^2,\\
30 &= 2\cdot3\cdot5.
\end{aligned}
\]
The primes that appear are \(2\), \(3\), and \(5\).
The largest exponent of \(2\) is \(2\), the largest exponent of \(3\) is \(2\), and the largest exponent of \(5\) is \(1\).
Therefore:
\[
\begin{aligned}
\mathrm{LCM}
&=2^2\cdot3^2\cdot5\\
&=4\cdot9\cdot5\\
&=180.
\end{aligned}
\]
6. Why minimum exponents give the HCF
A common factor must divide every number.
Therefore, it cannot use more copies of a prime than the number that has the fewest copies of that prime.
That is why the HCF uses the minimum exponent among the common primes.
If one number has \(2^2\), another has \(2^1\), and another has \(2^1\), then the common factor can only use
\[
\begin{aligned}
2^1.
\end{aligned}
\]
7. Why maximum exponents give the LCM
A common multiple must be divisible by every number.
Therefore, it must contain enough copies of each prime to cover the number with the greatest exponent of that prime.
That is why the LCM uses the maximum exponent.
If one number contains \(3^2\), then the LCM must contain at least \(3^2\), or it will not be divisible by that number.
8. Coprime numbers
If the HCF of a set of numbers is \(1\), then the whole set has no common prime factor shared by every number.
Such numbers are often called relatively prime as a set.
\[
\begin{aligned}
\gcd(7,11,13)=1.
\end{aligned}
\]
Since all three are prime and different, their LCM is their product:
\[
\begin{aligned}
\operatorname{lcm}(7,11,13)
&=7\cdot11\cdot13\\
&=1001.
\end{aligned}
\]
9. Relationship for two numbers
For two positive integers \(a\) and \(b\), there is a useful relationship:
\[
\begin{aligned}
\gcd(a,b)\cdot\operatorname{lcm}(a,b)
&=a\cdot b.
\end{aligned}
\]
For example:
\[
\begin{aligned}
\gcd(12,18)&=6,\\
\operatorname{lcm}(12,18)&=36.
\end{aligned}
\]
Then:
\[
\begin{aligned}
6\cdot36
&=216,\\
12\cdot18
&=216.
\end{aligned}
\]
This identity is guaranteed for two numbers, but it does not extend in the same simple product form to three or more numbers.
10. Euclidean algorithm for GCD
The Euclidean algorithm is a fast way to compute the GCD of two numbers.
It uses repeated division:
\[
\begin{aligned}
\gcd(a,b)&=\gcd(b,a\bmod b).
\end{aligned}
\]
Example:
\[
\begin{aligned}
30 &= 18\cdot1+12,\\
18 &= 12\cdot1+6,\\
12 &= 6\cdot2+0.
\end{aligned}
\]
Therefore:
\[
\begin{aligned}
\gcd(30,18)=6.
\end{aligned}
\]
For multiple numbers, apply the GCD step repeatedly:
\[
\begin{aligned}
\gcd(a,b,c)=\gcd(\gcd(a,b),c).
\end{aligned}
\]
11. Full worked example
Find the HCF and LCM of \(12\), \(18\), and \(30\).
First factorise:
\[
\begin{aligned}
12 &= 2^2\cdot3,\\
18 &= 2\cdot3^2,\\
30 &= 2\cdot3\cdot5.
\end{aligned}
\]
HCF uses common primes with minimum exponents:
\[
\begin{aligned}
\mathrm{HCF}
&=2^1\cdot3^1\\
&=6.
\end{aligned}
\]
LCM uses all primes with maximum exponents:
\[
\begin{aligned}
\mathrm{LCM}
&=2^2\cdot3^2\cdot5\\
&=180.
\end{aligned}
\]
Final result:
\[
\begin{aligned}
\boxed{\mathrm{HCF}=6}
\qquad
\boxed{\mathrm{LCM}=180}.
\end{aligned}
\]
12. Formula summary
| Goal |
Rule |
Example with \(12,18,30\) |
| Prime factorisation |
Write each number as a product of prime powers. |
\(12=2^2\cdot3\) |
| HCF / GCD |
Use common primes with smallest exponents. |
\(2^1\cdot3^1=6\) |
| LCM |
Use all primes with largest exponents. |
\(2^2\cdot3^2\cdot5=180\) |
| Two-number identity |
\(\gcd(a,b)\operatorname{lcm}(a,b)=ab\) |
\(6\cdot36=12\cdot18\) |
| Repeated GCD |
\(\gcd(a,b,c)=\gcd(\gcd(a,b),c)\) |
\(\gcd(12,18,30)=6\) |
13. Common mistakes
- Using the largest common exponent for HCF instead of the smallest common exponent.
- Forgetting a prime factor when building the LCM.
- Using only primes common to all numbers for the LCM.
- Confusing HCF with LCM.
- Assuming the two-number product identity works the same way for more than two numbers.
- Forgetting that \(1\) has no prime factors.
Key idea: HCF is about what all numbers share; LCM is about what is needed to cover every number.
