StudySmarter - The all-in-one study app.

4.8 • +11k Ratings

More than 3 Million Downloads

Free

Highest Common Factor

- Calculus
- Absolute Maxima and Minima
- Accumulation Function
- Accumulation Problems
- Algebraic Functions
- Alternating Series
- Application of Derivatives
- Approximating Areas
- Arc Length of a Curve
- Arithmetic Series
- Average Value of a Function
- Calculus of Parametric Curves
- Candidate Test
- Combining Differentiation Rules
- Continuity
- Continuity Over an Interval
- Convergence Tests
- Cost and Revenue
- Derivative Functions
- Derivative of Exponential Function
- Derivative of Inverse Function
- Derivative of Logarithmic Functions
- Derivative of Trigonometric Functions
- Derivatives
- Derivatives and Continuity
- Derivatives and the Shape of a Graph
- Derivatives of Inverse Trigonometric Functions
- Derivatives of Polar Functions
- Derivatives of Sin, Cos and Tan
- Determining Volumes by Slicing
- Disk Method
- Divergence Test
- Euler's Method
- Evaluating a Definite Integral
- Evaluation Theorem
- Exponential Functions
- Finding Limits
- Finding Limits of Specific Functions
- First Derivative Test
- Function Transformations
- Geometric Series
- Growth Rate of Functions
- Higher-Order Derivatives
- Hyperbolic Functions
- Implicit Differentiation Tangent Line
- Improper Integrals
- Initial Value Problem Differential Equations
- Integral Test
- Integrals of Exponential Functions
- Integrals of Motion
- Integrating Even and Odd Functions
- Integration Tables
- Integration Using Long Division
- Integration of Logarithmic Functions
- Integration using Inverse Trigonometric Functions
- Intermediate Value Theorem
- Inverse Trigonometric Functions
- Jump Discontinuity
- Limit Laws
- Limit of Vector Valued Function
- Limit of a Sequence
- Limits
- Limits at Infinity
- Limits of a Function
- Linear Differential Equation
- Logarithmic Differentiation
- Logarithmic Functions
- Logistic Differential Equation
- Maclaurin Series
- Maxima and Minima
- Maxima and Minima Problems
- Mean Value Theorem for Integrals
- Models for Population Growth
- Motion Along a Line
- Natural Logarithmic Function
- Net Change Theorem
- Newton's Method
- One-Sided Limits
- Optimization Problems
- P Series
- Particular Solutions to Differential Equations
- Polar Coordinates Functions
- Polar Curves
- Population Change
- Power Series
- Ratio Test
- Removable Discontinuity
- Riemann Sum
- Rolle's Theorem
- Root Test
- Second Derivative Test
- Separable Equations
- Simpson's Rule
- Solid of Revolution
- Solutions to Differential Equations
- Surface Area of Revolution
- Tangent Lines
- Taylor Series
- Techniques of Integration
- The Fundamental Theorem of Calculus
- The Mean Value Theorem
- The Power Rule
- The Squeeze Theorem
- The Trapezoidal Rule
- Theorems of Continuity
- Trigonometric Substitution
- Vector Valued Function
- Vectors in Calculus
- Washer Method
- Decision Maths
- Geometry
- 2 Dimensional Figures
- 3 Dimensional Vectors
- 3-Dimensional Figures
- Altitude
- Angles in Circles
- Arc Measures
- Area and Volume
- Area of Circles
- Area of Circular Sector
- Area of Parallelograms
- Area of Plane Figures
- Area of Rectangles
- Area of Regular Polygons
- Area of Rhombus
- Area of Trapezoid
- Area of a Kite
- Composition
- Congruence Transformations
- Congruent Triangles
- Convexity in Polygons
- Coordinate Systems
- Dilations
- Distance and Midpoints
- Equation of Circles
- Equilateral Triangles
- Figures
- Fundamentals of Geometry
- Geometric Inequalities
- Geometric Mean
- Geometric Probability
- Glide Reflections
- HL ASA and AAS
- Identity Map
- Inscribed Angles
- Isometry
- Isosceles Triangles
- Law of Cosines
- Law of Sines
- Linear Measure and Precision
- Median
- Parallel Lines Theorem
- Parallelograms
- Perpendicular Bisector
- Plane Geometry
- Polygons
- Projections
- Properties of Chords
- Proportionality Theorems
- Pythagoras Theorem
- Rectangle
- Reflection in Geometry
- Regular Polygon
- Rhombuses
- Right Triangles
- Rotations
- SSS and SAS
- Segment Length
- Similarity
- Similarity Transformations
- Special quadrilaterals
- Squares
- Surface Area of Cone
- Surface Area of Cylinder
- Surface Area of Prism
- Surface Area of Sphere
- Surface Area of a Solid
- Surface of Pyramids
- Symmetry
- Translations
- Trapezoids
- Triangle Inequalities
- Triangles
- Using Similar Polygons
- Vector Addition
- Vector Product
- Volume of Cone
- Volume of Cylinder
- Volume of Pyramid
- Volume of Solid
- Volume of Sphere
- Volume of prisms
- Mechanics Maths
- Acceleration and Time
- Acceleration and Velocity
- Assumptions
- Calculus Kinematics
- Coefficient of Friction
- Connected Particles
- Constant Acceleration
- Constant Acceleration Equations
- Converting Units
- Force as a Vector
- Kinematics
- Newton's First Law
- Newton's Second Law
- Newton's Third Law
- Projectiles
- Pulleys
- Resolving Forces
- Statics and Dynamics
- Tension in Strings
- Variable Acceleration
- Probability and Statistics
- Bar Graphs
- Basic Probability
- Charts and Diagrams
- Conditional Probabilities
- Continuous and Discrete Data
- Frequency, Frequency Tables and Levels of Measurement
- Independent Events Probability
- Line Graphs
- Mean Median and Mode
- Mutually Exclusive Probabilities
- Probability Rules
- Probability of Combined Events
- Quartiles and Interquartile Range
- Systematic Listing
- Pure Maths
- ASA Theorem
- Absolute Value Equations and Inequalities
- Addition and Subtraction of Rational Expressions
- Addition, Subtraction, Multiplication and Division
- Algebra
- Algebraic Fractions
- Algebraic Notation
- Algebraic Representation
- Analyzing Graphs of Polynomials
- Angle Measure
- Angles
- Angles in Polygons
- Approximation and Estimation
- Area and Circumference of a Circle
- Area and Perimeter of Quadrilaterals
- Area of Triangles
- Arithmetic Sequences
- Average Rate of Change
- Bijective Functions
- Binomial Expansion
- Binomial Theorem
- Chain Rule
- Circle Theorems
- Circles
- Circles Maths
- Combination of Functions
- Common Factors
- Common Multiples
- Completing the Square
- Completing the Squares
- Complex Numbers
- Composite Functions
- Composition of Functions
- Compound Interest
- Compound Units
- Construction and Loci
- Converting Metrics
- Convexity and Concavity
- Coordinate Geometry
- Coordinates in Four Quadrants
- Cubic Function Graph
- Cubic Polynomial Graphs
- Data transformations
- Deductive Reasoning
- Definite Integrals
- Deriving Equations
- Determinant of Inverse Matrix
- Determinants
- Differential Equations
- Differentiation
- Differentiation Rules
- Differentiation from First Principles
- Differentiation of Hyperbolic Functions
- Direct and Inverse proportions
- Disjoint and Overlapping Events
- Disproof by Counterexample
- Distance from a Point to a Line
- Divisibility Tests
- Double Angle and Half Angle Formulas
- Drawing Conclusions from Examples
- Ellipse
- Equation of Line in 3D
- Equation of a Perpendicular Bisector
- Equation of a circle
- Equations
- Equations and Identities
- Equations and Inequalities
- Estimation in Real Life
- Euclidean Algorithm
- Evaluating and Graphing Polynomials
- Even Functions
- Exponential Form of Complex Numbers
- Exponential Rules
- Exponentials and Logarithms
- Expression Math
- Expressions and Formulas
- Faces Edges and Vertices
- Factorials
- Factoring Polynomials
- Factoring Quadratic Equations
- Factorising expressions
- Factors
- Finding Maxima and Minima Using Derivatives
- Finding Rational Zeros
- Finding the Area
- Forms of Quadratic Functions
- Fractional Powers
- Fractional Ratio
- Fractions
- Fractions and Decimals
- Fractions and Factors
- Fractions in Expressions and Equations
- Fractions, Decimals and Percentages
- Function Basics
- Functional Analysis
- Functions
- Fundamental Counting Principle
- Fundamental Theorem of Algebra
- Generating Terms of a Sequence
- Geometric Sequence
- Gradient and Intercept
- Graphical Representation
- Graphing Rational Functions
- Graphing Trigonometric Functions
- Graphs
- Graphs and Differentiation
- Graphs of Common Functions
- Graphs of Exponents and Logarithms
- Graphs of Trigonometric Functions
- Greatest Common Divisor
- Growth and Decay
- Growth of Functions
- Highest Common Factor
- Hyperbolas
- Imaginary Unit and Polar Bijection
- Implicit differentiation
- Inductive Reasoning
- Inequalities Maths
- Infinite geometric series
- Injective functions
- Instantaneous Rate of Change
- Integers
- Integrating Polynomials
- Integrating Trig Functions
- Integrating e^x and 1/x
- Integration
- Integration Using Partial Fractions
- Integration by Parts
- Integration by Substitution
- Integration of Hyperbolic Functions
- Interest
- Inverse Hyperbolic Functions
- Inverse and Joint Variation
- Inverse functions
- Iterative Methods
- Law of Cosines in Algebra
- Law of Sines in Algebra
- Laws of Logs
- Limits of Accuracy
- Linear Expressions
- Linear Systems
- Linear Transformations of Matrices
- Location of Roots
- Logarithm Base
- Logic
- Lower and Upper Bounds
- Lowest Common Denominator
- Lowest Common Multiple
- Math formula
- Matrices
- Matrix Addition and Subtraction
- Matrix Determinant
- Matrix Multiplication
- Metric and Imperial Units
- Misleading Graphs
- Mixed Expressions
- Modulus Functions
- Modulus and Phase
- Multiples of Pi
- Multiplication and Division of Fractions
- Multiplicative Relationship
- Multiplying and Dividing Rational Expressions
- Natural Logarithm
- Natural Numbers
- Notation
- Number
- Number Line
- Number Systems
- Numerical Methods
- Odd functions
- Open Sentences and Identities
- Operation with Complex Numbers
- Operations with Decimals
- Operations with Matrices
- Operations with Polynomials
- Order of Operations
- Parabola
- Parallel Lines
- Parametric Differentiation
- Parametric Equations
- Parametric Integration
- Partial Fractions
- Pascal´s Triangle
- Percentage
- Percentage Increase and Decrease
- Percentage as fraction or decimals
- Perimeter of a Triangle
- Permutations and Combinations
- Perpendicular Lines
- Points Lines and Planes
- Polynomial Graphs
- Polynomials
- Powers Roots And Radicals
- Powers and Exponents
- Powers and Roots
- Prime Factorization
- Prime Numbers
- Problem-solving Models and Strategies
- Product Rule
- Proof
- Proof and Mathematical Induction
- Proof by Contradiction
- Proof by Deduction
- Proof by Exhaustion
- Proof by Induction
- Properties of Exponents
- Proportion
- Proving an Identity
- Pythagorean Identities
- Quadratic Equations
- Quadratic Function Graphs
- Quadratic Graphs
- Quadratic functions
- Quadrilaterals
- Quotient Rule
- Radians
- Radical Functions
- Rates of Change
- Ratio
- Ratio Fractions
- Rational Exponents
- Rational Expressions
- Rational Functions
- Rational Numbers and Fractions
- Ratios as Fractions
- Real Numbers
- Reciprocal Graphs
- Recurrence Relation
- Recursion and Special Sequences
- Remainder and Factor Theorems
- Representation of Complex Numbers
- Rewriting Formulas and Equations
- Roots of Complex Numbers
- Roots of Polynomials
- Rounding
- SAS Theorem
- SSS Theorem
- Scale Drawings and Maps
- Scale Factors
- Scientific Notation
- Sector of a Circle
- Segment of a Circle
- Sequences
- Sequences and Series
- Series Maths
- Sets Math
- Similar Triangles
- Similar and Congruent Shapes
- Simple Interest
- Simplifying Fractions
- Simplifying Radicals
- Simultaneous Equations
- Sine and Cosine Rules
- Small Angle Approximation
- Solving Linear Equations
- Solving Linear Systems
- Solving Quadratic Equations
- Solving Radical Inequalities
- Solving Rational Equations
- Solving Simultaneous Equations Using Matrices
- Solving Systems of Inequalities
- Solving Trigonometric Equations
- Solving and Graphing Quadratic Equations
- Solving and Graphing Quadratic Inequalities
- Special Products
- Standard Form
- Standard Integrals
- Standard Unit
- Straight Line Graphs
- Substraction and addition of fractions
- Sum and Difference of Angles Formulas
- Surds
- Surjective functions
- Tables and Graphs
- Tangent of a Circle
- The Quadratic Formula and the Discriminant
- Transformations
- Transformations of Graphs
- Translations of Trigonometric Functions
- Triangle Rules
- Triangle trigonometry
- Trigonometric Functions
- Trigonometric Functions of General Angles
- Trigonometric Identities
- Trigonometric Ratios
- Trigonometry
- Turning Points
- Types of Functions
- Types of Numbers
- Types of Triangles
- Unit Circle
- Units
- Variables in Algebra
- Vectors
- Verifying Trigonometric Identities
- Writing Equations
- Writing Linear Equations
- Statistics
- Binomial Distribution
- Binomial Hypothesis Test
- Bivariate Data
- Box Plots
- Categorical Data
- Categorical Variables
- Central Limit Theorem
- Comparing Data
- Conditional Probability
- Correlation Math
- Cumulative Frequency
- Data Interpretation
- Discrete Random Variable
- Distributions
- Events (Probability)
- Frequency Polygons
- Geometric Distribution
- Histograms
- Hypothesis Test for Correlation
- Hypothesis Testing
- Large Data Set
- Linear Interpolation
- Measures of Central Tendency
- Methods of Data Collection
- Normal Distribution
- Normal Distribution Hypothesis Test
- Probability
- Probability Calculations
- Probability Distribution
- Probability Generating Function
- Quantitative Variables
- Random Variables
- Sampling
- Scatter Graphs
- Single Variable Data
- Standard Deviation
- Standard Normal Distribution
- Statistical Measures
- Tree Diagram
- Type I Error
- Type II Error
- Types of Data in Statistics
- Venn Diagrams

Now that we are well acquainted with the concept of Factors, it is time to move on. If you haven't read that explanation, take a look! Previously, we learned how to find the Common Factors between two (or more) numbers. At the end of the topic, we stated that recognising these common factors can help us determine the **highest common factor** shared between these given numbers.

The highest common factor is a helpful tool that can be used to reduce fractions and ratios. It is also used to simplify expressions and equations so that it is easier for us to solve. Throughout this topic, we shall abbreviate the highest common factor by **HCF**.

We can think of the HCF as the greatest number that is divisible by a set of given numbers. In other words, let \(x\) and \(y\) be two whole numbers. The HCF of \(x\) and \(y\) is the largest possible number that divides both \(x\) and \(y\) completely without leaving a remainder. With this in mind, we can describe the HCF with the following definition.

Recall that a common factor is a number that divides a pair of whole numbers precisely resulting in a remainder equal to zero.

The **highest common factor** (HCF) is the largest common factor of two (or more) whole numbers.

Let us denote the HCF by the letter \(a\). We can write the HCF of \(x\) and \(y\) by the following notation,

\[ \mbox{HCF}(x,y) = a.\]

In some textbooks, the HCF can also be referred to as the **greatest common factor** (GCF) or the **greatest common divisor** (GCD). Let us demonstrate this with an example.

What is the HCF of 14 and 21?

**Solution**

Let us first list down the factors of 14. The number 14 can be written as the product of the following pairs of numbers.

\[ \begin{align} 1 \cdot 14 &= 14 \\ 2 \cdot 7 &= 14. \end{align} \]

Thus, the factors of 14 are 1, 2, 7, and 14. Next, let us list down the factors of 21. Applying the same method as before, we have

\[ \begin{align} 1 \cdot 21 &= 21 \\ 3 \cdot 7 &= 21. \end{align} \]

Thus, the factors of 21 are 1, 3, 7, and 21. Listing these two lists of factors and comparing them, we find that the common factors of 14 and 21 are 1 and 7. Between these two common factors, observe that 1 is less than 7.

Therefore, 7 is the highest common factor between 14 and 21. Indeed, 7 divides both 14 and 21.

Prime Numbers are numbers that are only divisible by 1 and themselves. This means that a prime number has only two factors, that is, 1 and itself. So, what if we had to find the HCF of two prime numbers? Here's an example.

Find the HCF of 23 and 31.

**Solution**

The numbers 23 and 31 are indeed prime as they are not divisible by any other number apart from 1 and itself. Thus, their factors are simply listed below.

Factors of 23: 1 and 23

Factors of 31: 1 and 31

Observe that the only common factor between these two numbers is 1. As there are no other common factors to compare this to, we conclude that the HCF of 23 and 31 is 1.

This example leads us to the following result: the HCF of two (or more) prime numbers is always equal to 1. This statement is true for all given sets of prime numbers.

Why not give it a go? Try finding the HCF between the prime numbers 3, 17, and 29. You'll see that the result is also 1!

The HCFs of two (or more) numbers have several notable properties we should familiarise ourselves with. These are listed below.

In the next section, we shall move on to the different techniques for finding the HCF of two (or more) numbers.

There are three ways to find the HCF of two (or more) numbers.

**Listing factors method.****Prime factorisation.****Division method.**

Here, we hope to learn how to apply each method and introduce several worked examples showing each approach.

The listing factors method is the **most straightforward technique** when finding the HCF. The example seen in the previous section uses this method. There are three steps to this method.

List the factors of each given number.

Find the common factors between these numbers.

Determine the highest common factor among this list of common factors. This number is the HCF.

Let us look at some worked examples.

Find the HCF of 27 and 36.

**Solution**

**Step 1:** Let us list the factors of 27 and 36.

Factors of 27: 1, 3, 9, 27

Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36

**Step 2: **From these two lists, let us determine the common factors shared between 27 and 36.

Common factors of 27 and 36: 1, 3, 9.

**Step 3:** Finally, we shall identify the largest common factor in this list.

Here, 9 is the largest common factor. Thus, \( \mbox{HCF}(27,36) = 9\).

Find the HCF of 7, 35, and 42.

**Solution**

**Step 1:** Let us list the factors of 7, 35, and 42.

Factors of 7: 1, 7

Factors of 35: 1, 5, 7, 35

Factors of 42: 1, 2, 3, 6, 7, 14, 21, 42

**Step 2: **From these three lists, let us determine the common factors shared between 7, 35, and 42.

Common factors of 7, 35, and 42: 1 and 7.

**Step 3:** Finally, we shall identify the largest common factor in this list.

Here, 7 is the largest common factor. Thus, \(\mbox{HCF}(7, 35, 42) = 7.\)

Find the HCF of 12, 15, 21, and 24.

**Solution**

**Step 1:** Let us list the factors of 12, 15, 21, and 24.

Factors of 12: 1, 2, 3, 4, 6, 12

Factors of 15: 1, 3, 5, 15

Factors of 21: 1, 3, 7, 21

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

**Step 2: **From these three lists, let us determine the common factors shared between 12, 15, 21, and 24.

Common factors of 12, 15, 21, and 24: 1 and 3.

**Step 3:** Finally, we shall identify the largest common factor in this list.

Here, 3 is the largest common factor. Thus, \(\mbox{HCF}(12, 15, 21, 24) = 3.\)

Although this method is very straightforward and can be used to find the HCF of two or numbers, it can be rather tricky especially when dealing with bigger numbers. This is where the other two ways of finding the HCF come in!

Prime factorisation is a process used to represent a number as a product of its prime factors. A more detailed discussion of this topic can be found in the article: Prime Factorisation. There are three steps to finding the HCF of two (or more) numbers using this method.

Express the given numbers in their prime factored form.

Find the common prime factors of the given numbers.

Multiply the common prime factors. This product is the HCF of the given numbers.

To view this clearly, let us demonstrate this with the following examples.

Find the HCF of 24 and 32.

**Solution **

**Step 1: **We shall write each number as a product of primes.

Prime factorization of 24:

\[ \begin{array}{c|c} 2 & 24 \\ \hline 2 & 12 \\ \hline 2 & 6 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[24 = 2\cdot 2\cdot 2\cdot 3 = 2^3 \cdot 3\]

Prime factorization of 32:

\[ \begin{array}{c|c} 2 & 32 \\ \hline 2 & 16 \\ \hline 2 & 8 \\ \hline 2 & 4 \\ \hline 2& 2 \\ \hline & 1 \end{array} \]

\[32 = 2\cdot 2\cdot 2\cdot 2 \cdot 2 = 2^5\]

**Step 2: **List the common primes of 24 and 32.

\[\begin{align} 24 &= 2\cdot 2\cdot 2\cdot 3 \\ 32 &= 2\cdot 2\cdot 2\cdot 2 \cdot 2 .\end{align} \]

Here, the common primes of 24 and 32 are the three instances of the number 2.

**Step 3: **Multiply the common factors.

\[ 2\cdot 2\cdot 2=8.\]

Thus, \(\mbox{HCF}(24, 32) = 8.\)

Find the HCF of 8, 12, and 20.

**Solution **

**Step 1: **We shall write each number as a product of primes.

Prime factorization of 8:

\[ \begin{array}{c|c} 2 & 8 \\ \hline 2 & 4 \\ \hline 2 & 2 \\ \hline & 1 \end{array} \]

\[8 = 2\cdot 2\cdot 2\cdot = 2^3 \]

Prime factorization of 12:

\[ \begin{array}{c|c} 2 & 12 \\ \hline 2 & 6 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[12 = 2\cdot 2\cdot 3 = 2^2 \cdot 3\]

Prime factorization of 20:

\[ \begin{array}{c|c} 2 & 20 \\ \hline 2 & 10 \\ \hline 5 & 5 \\ \hline & 1 \end{array} \]

\[20 = 2\cdot 2\cdot 5 = 2^2 \cdot 5\]

**Step 2: **List the common primes of 8, 12 and 20.

\[\begin{align} 8 &= 2\cdot 2\cdot 2\cdot \\ 12 &= 2\cdot 2\cdot 3 \\ 20 &= 2\cdot 2\cdot 5 .\end{align} \]

Here, the common primes of 8, 12, and 20 are the two instances of the number 2.

**Step 3: **Multiply the common factors.

\[2 \cdot 2 = 4.\]

Thus, \( \mbox{HCF}(8, 12, 20) = 4.\)

Find the HCF of 9, 27, 36, and 45.

**Solution **

**Step 1: **We shall write each number as a product of primes.

Prime factorization of 9:

\[ \begin{array}{c|c} 3 & 9 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[9 = 3\cdot 3 = 3^2\]

Prime factorization of 27:

\[ \begin{array}{c|c} 3 & 27 \\ \hline 3 & 9 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[27 = 3\cdot 3\cdot 3 = 3^3\]

Prime factorization of 36:

\[ \begin{array}{c|c} 2 & 36 \\ \hline 2 & 18 \\ \hline 3 & 9 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[36 = 2\cdot 2\cdot 3\cdot 3 = 2^2 \cdot 3^2\]

Prime factorization of 45

\[ \begin{array}{c|c} 3 & 45 \\ \hline 3 & 15 \\ \hline 5 & 5 \\ \hline & 1 \end{array} \]

\[45 = 3\cdot 3\cdot 5 = 3^2 \cdot 5\]

**Step 2: **List the common primes of 9, 27, 36, and 45.

\[\begin{align} 9 &= 3\cdot 3 \\ 27 &= 3\cdot 3\cdot 3 \\ 36 &= 2\cdot 2\cdot 3\cdot 3 \\ 45 &= 3\cdot 3\cdot 5 .\end{align} \]

Here, the common primes of 9, 27, 36, and 45 are the two instances of the number 3.

**Step 3: **Multiply the common factors.

\[ 3 \cdot 3 = 9\]

Thus, \( \mbox{HCF}( 9, 27, 36, 45) = 9.\)

For this approach, we shall make use of **long division**. Below are the steps to this method.

Using long division, divide the larger number by the smaller number.

If the remainder is equal to 0, then the divisor is the HCF.

If the remainder is not equal to 0, then we shall make the remainder of Step 1 the divisor and the divisor from Step 1 the dividend. In doing so, conduct long division again.

If the remainder is equal to 0, then the divisor of the last division is the HCF.

If the remainder is not equal to 0, then repeat Step 3 until the remainder equals 0.

**Division method for multiple numbers**

We need to tweak the division method when it comes to finding the HCF of more than two numbers. Here, we need to group the numbers into equal groups (of two) and perform long division as before. In doing so, we are essentially breaking down the division involved into a string of steps that are less complicated.

Determine the HCF of the first two of the given numbers via the division method above.

Find the HCF of the third number and the HCF found from the first two numbers in Step 1.

This gives the HCF of the three numbers.

Repeat Step 2 to find the HCF of the fourth number and the HCF found from the first three numbers in Step 3.

This gives the HCF of the four numbers.

Let us now look at some worked examples.

Find the HCF of 40 and 50.

**Solution **

**Step 1: **Divide 50 by 40.

\[ \begin{array}{rl} 1 & \\40\; \enclose{longdiv}{\;50} \kern-.2ex\\ \underline{40} \, & \\ 10 \, & \end{array}\]

**Step 2:** Since the remainder is not 0, make the remainder (= 10) the divisor and the divisor (= 40) the dividend.

\[ \begin{array}{rl} 4 & \\10\; \enclose{longdiv}{\;40} \kern-.2ex\\ \underline{40} \, & \\ 0 \, & \end{array}\]

**Step 3:** As the remainder in Step 2 is equal to 0, the divisor = 10 is the HCF.

Thus, \( \mbox{HCF}(40, 50) = 10.\)

Find the HCF of 33, 121, and 154.

**Solution**

**Step 1(a):** Find the HCF of 33 and 121 using long division.

\[ \begin{array}{rl} 3 & \\33\; \enclose{longdiv}{\;121} \kern-.2ex\\ \underline{99} \, & \\ 22 \, & \end{array}\]

**Step 1(b):** Since the remainder is not 0, make the remainder (= 22) the divisor and the divisor (= 33) the dividend.

\[ \begin{array}{rl} 1 & \\22\; \enclose{longdiv}{\;33} \kern-.2ex\\ \underline{22} \, & \\ 11 \, & \end{array}\]

**Step 1(c):** Since the remainder is not 0, make the remainder (= 11) the divisor and the divisor (= 22) the dividend.

\[ \begin{array}{rl} 1 & \\11\; \enclose{longdiv}{\;22} \kern-.2ex\\ \underline{22} \, & \\ 0\, & \end{array}\]

The remainder is finally equal to 0. Thus, the divisor = 11 is the HCF of 33 and 121.

**Step 2:** Now that we have the HCF of 33 and 121, let us now find the HCF of 33, 121, and 154. To do so, make the HCF (of 33 and 121) found in Step 1(c) the divisor and 154 the divided. Apply long division as usual.

\[ \begin{array}{rl} 14 & \\11\; \enclose{longdiv}{\;154} \kern-.2ex\\ \underline{154} \, & \\ 0 \, & \end{array}\]

As the remainder in Step 2 is equal to 0, the divisor = 11 is the HCF of all three given numbers.Thus, \( \mbox{HCF}(33, 121, 154) = 11.\)

Find the HCF of 24, 48, 63, and 75.

**Solution**

**Step 1:** Find the HCF of 24 and 48 using long division.

\[ \begin{array}{rl} 2 & \\24\; \enclose{longdiv}{\;48} \kern-.2ex\\ \underline{48} \, & \\ 0 \, & \end{array}\]

As the remainder is equal to 0, the divisor = 24 is the HCF of 24 and 48.

**Step 2(a):** Now that we have the HCF of 24 and 48, let us now find the HCF of 24, 48, and 63. To do so, make the HCF (of 24 and 48) found in Step 1 the divisor and 63 the divided. Perform long division as before.

\[ \begin{array}{rl} 2 & \\24\; \enclose{longdiv}{\;63} \kern-.2ex\\ \underline{48} \, & \\ 15 \, & \end{array}\]

**Step 2(b):** Since the remainder is not 0, make the remainder (= 15) the divisor and the divisor (= 24) the dividend.

\[ \begin{array}{rl} 1 & \\15\; \enclose{longdiv}{\;24} \kern-.2ex\\ \underline{15} \, & \\ 9 \, & \end{array}\]

**Step 2(c):** Since the remainder is not 0, make the remainder (= 9) the divisor and the divisor (= 15) the dividend.

\[ \begin{array}{rl} 1 & \\9\; \enclose{longdiv}{\;15} \kern-.2ex\\ \underline{9} \, & \\ 6 \, & \end{array}\]

**Step 2(d):** Since the remainder is not 0, make the remainder (= 6) the divisor and the divisor (= 9) the dividend.

\[ \begin{array}{rl} 1 & \\6\; \enclose{longdiv}{\;9} \kern-.2ex\\ \underline{6} \, & \\ 3 \, & \end{array}\]

**Step 2(e):** Since the remainder is not 0, make the remainder (= 3) the divisor and the divisor (= 6) the dividend.

\[ \begin{array}{rl} 2 & \\3\; \enclose{longdiv}{\;6} \kern-.2ex\\ \underline{6} \, & \\ 0 \, & \end{array}\]

The remainder is finally equal to 0. Thus, the divisor = 3 is the HCF of 24, 48, and 63.

**Step 3:** As we now have the HCF of 24, 48, and 63, we finally need to find the HCF of 24, 48, 63, and 75. We do this by making the HCF (of 24, 48, and 63) found in Step 2(e) the divisor and 75 the divided. Apply long division as usual.

\[ \begin{array}{rl} 25 & \\3\; \enclose{longdiv}{\;75} \kern-.2ex\\ \underline{75} \, & \\ 0 \, & \end{array}\]

Here the remainder is equal to 0. So the divisor = 3 is the HCF of all four given numbers.

Thus, \( \mbox{HCF}(24, 48, 63, 75) = 3.\)

The lowest common multiple (LCM) is the smallest common multiple for a given set of numbers. You can find more information on this topic in the article: Lowest Common Multiple. In this section, we shall make comparisons between the HCF and LCM. This contrast is seen in the table below.

The table below compares the HCF and LCM of two whole numbers, x and y.

Highest Common Factor (HCF) | Lowest Common Multiple (LCM) |

The GCF of two whole numbers \(x\) and \(y\) is the greatest number that divides both\(x\) and \(y\) completely. | The LCM of two whole numbers \(x\) and \(y\) is the smallest number which is a multiple of both \(x\) and \(y\) . |

The intersection between the set of common factors of \(x\) and \(y\) is the greatest value. | The intersection between the set of common multiples of \(x\) and \(y\) is the minimum value. |

Denoted by \(\mbox{GCF}(x, y) = a\), where \(a\) is the GCF of \(x\) and \(y\) | Denoted by \(\mbox{LCM}(x, y) = b\), where \(b\) is the LCM of \(x\) and \(y\) |

Despite their differences, the HCF and LCM of two numbers happen to have a clever link to one another. Let's say we have two whole numbers, \(x\) and \(y\). The HCF and LCM of these two numbers are denoted by \( \mbox{HCF}(x, y) \) and \( \mbox{LCM}(x, y)\). These two concepts are related by the following notion: the product of the HCF and LCM of \(x\) and \(y\) is equal to the product of \(x\) and \(y\). We can write this as the notation below,

\[ \mbox{HCF}(x,y) \cdot \mbox{LCM}(x,y) = xy.\]

Here is an example that demonstrates this.

Verify that the above formula is satisfied for the numbers 9 and 12.

**Solution**

Let us first find the HCF of 9 and 12. Using the listing method, we obtain:

Factors of 9: 1, 3, 9

Factors of 12: 1, 2, 3, 4, 6, 12

Common factors of 9 and 12: 1 and 3

Thus, HCF(9, 12) = 3

Now, let us find the LCM of 9 and 12. To find the LCM, refer to the topic: Lowest Common Multiple.

\[ \begin{array}{c|c} 3 &9 \; 12 \\ \hline 2 & 3, \; 4 \\ \hline 2 & 3,\; 2 \\ \hline 3 & 3,\; 1 \\ \hline & 1,\;1 \end{array} \]

\[36 = 3\cdot 2\cdot 2\cdot 3\]

Thus \( \mbox{LCM}(9, 12) = 36.\)

Referring to the given formula, we first note that the product of 9 and 12 is equal to 108. Now, let us deduce the product of their HCF and LCM.

\[ \mbox{HCF}(9,12) \cdot \mbox{LCM}(9,12) = 3\cdot 36 = 108.\]

As you can see, the product of the HCF and LCM of 9 and 12 is also equal to the product of 9 and 12. Thus, the formula holds for this pair of numbers.

This formula is true for all given sets of numbers. Try it out with the examples given throughout this discussion.

We shall end our discussion with a final example of finding the HCF of a pair of numbers using all three methods studied above.

Determine the HCF of 45 and 72 using the listing method, prime factorisation method, and division method for finding the HCF.

**Listing method **

**Step 1:** Let us list the factors of 45 and 72.

Factors of 45: 1, 3, 5, 9, 15, 45

Factors of 72: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72

**Step 2: **From these two lists, let us determine the common factors shared between 45 and 72.

Common factors of 45 and 72: 1, 3, 9

**Step 3:** Finally, we shall identify the largest common factor in this list.

Here, 9 is the largest common factor. Thus, \( \mbox{HCF}(45, 72) = 9.\)

**Prime factorisation method **

**Step 1: **We shall write each number as a product of primes.

Prime factorization of 45

\[ \begin{array}{c|c} 3 & 45 \\ \hline 3 & 15 \\ \hline 5 & 5 \\ \hline & 1 \end{array} \]

\[45 = 3\cdot 3\cdot 5 = 3^2 \cdot 5\]

Prime factorization of 72

\[ \begin{array}{c|c} 2 & 72 \\ \hline 2 & 36 \\ \hline 2 & 18 \\ \hline 3 & 9 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[72 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3\cdot 3 = 2^3 \cdot 3^2\]

**Step 2: **List the common primes of 45 and 72.

\[\begin{align} 45 &= 3\cdot 3\cdot 5 \\ 72 &= 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3\cdot 3 .\end{align} \]

Here, the common primes of 45 and 72 are the two instances of the number 3.

**Step 3: **Multiply the common factors

\[ 3\cdot 3 = 9 \]

Thus, \( \mbox{HCF}(45, 72) = 9.\)

**Division method**

**Step 1: **Divide 72 by 45

\[ \begin{array}{rl} 1 & \\45\; \enclose{longdiv}{\;72} \kern-.2ex\\ \underline{45} \, & \\ 27 \, & \end{array}\]

**Step 2:** Since the remainder is not 0, make the remainder = 27 the divisor = 45 the dividend.

\[ \begin{array}{rl} 1 & \\27\; \enclose{longdiv}{\;45} \kern-.2ex\\ \underline{27} \, & \\ 18 \, & \end{array}\]

**Step 3: **Since the remainder is not 0, make the remainder = 18 the divisor = 27 the dividend.

\[ \begin{array}{rl} 1 & \\18\; \enclose{longdiv}{\;27} \kern-.2ex\\ \underline{18} \, & \\ 9 \, & \end{array}\]

**Step 4:** Since the remainder is not 0, make the remainder = 9 the divisor = 18 the dividend.

\[ \begin{array}{rl} 2 & \\9\; \enclose{longdiv}{\;18} \kern-.2ex\\ \underline{18} \, & \\ 0 \, & \end{array}\]

**Step 5:** As the remainder in Step 4 is equal to 0, the divisor = 9 is the HCF.

Thus, \( \mbox{HCF}(45, 72) = 9.\)

- The HCF is the largest common factor of two whole numbers and is denoted by HCF(x, y) = a.
- The HCF of two numbers divides each given number without leaving a remainder.
- The HCF of two numbers is a factor of each given number.
- The HCF of two numbers is always less than or equal to each given number.
- The HCF of two (or more) prime numbers is always 1.
- Listing method for finding HCF.
List the factors of each number.

Find the common factors between these numbers.

Determine the highest common factor among this list of common factors.

Prime factorisation method for finding HCF.

Express the numbers in their prime factored form.

Find the common prime factors of these numbers.

Multiply the common prime factors.

Division method for finding HCF.

Divide the larger number by the smaller number via long division.

If the remainder is 0, then the divisor is the HCF.

If the remainder is not 0, then from Step 1, make the remainder the divisor and the divisor the dividend. Perform long division once more.

If the remainder is 0, then the divisor of the last division is the HCF.

If the remainder is not 0, then repeat Step 3 until the remainder equals 0.

Relationship between HCF and LCM:

\[ \mbox{HCF}(x,y) \cdot \mbox{LCM}(x,y) = xy.\]

The highest common factor is the largest common divisor between a pair of numbers

- Listing out common factors
- Prime factorization
- Division method

The HCF of 15 and 25 is 5

- The HCF of two numbers divides each given number without a remainder
- The HCF of two numbers is a factor of each given number
- The HCF of two numbers is always less than or equal to each given number
- The HCF of two prime numbers is always 1

More about Highest Common Factor

Be perfectly prepared on time with an individual plan.

Test your knowledge with gamified quizzes.

Create and find flashcards in record time.

Create beautiful notes faster than ever before.

Have all your study materials in one place.

Upload unlimited documents and save them online.

Identify your study strength and weaknesses.

Set individual study goals and earn points reaching them.

Stop procrastinating with our study reminders.

Earn points, unlock badges and level up while studying.

Create flashcards in notes completely automatically.

Create the most beautiful study materials using our templates.

Sign up to highlight and take notes. It’s 100% free.