International Journal of Pedagogics
151
https://theusajournals.com/index.php/ijp
VOLUME
Vol.05 Issue06 2025
PAGE NO.
151-153
10.37547/ijp/Volume05Issue06-42
Methods of Finding the LCM and GCD of Numbers
Akbaraliyeva Marjona Khurshid qizi
First year student of FSU, Uzbekistan
Received:
14 April 2025;
Accepted:
15 May 2025;
Published:
18 June 2025
Abstract:
This article examines several methods for determining the Least Common Multiple (LCM) and Greatest
Common Divisor (GCD) among natural numbers. The essence of each method, their application steps, as well as
their advantages and disadvantages, are analyzed. Special attention is given to the Euclidean algorithm, the
method through divisors, and the factorization method. Theoretical knowledge is reinforced through relevant
examples, and recommendations that serve to develop students' mathematical thinking are provided.
Keywords:
LCM, GCD, numbers, mathematical algorithm, divisor, multiple, Euclidean algorithm, arithmetic
method, common divisor, common multiple.
Introduction
Mathematics is one of the main sciences that shapes
consistent, precise, and logical thinking in humans.
Each concept within it is interrelated and has deep
logical meaning. When working with natural numbers,
especially in studying their internal structure and
mutual relations, the concepts of the Greatest
Common Divisor (GCD) and the Least Common Multiple
(LCM) are of particular importance. Through these two
concepts, it becomes possible to determine how
numbers are connected, the degree of their
commonality, and the ratios between them.
The GCD and LCM are closely related and are
widely used in mathematics to simplify complex
problems, correctly determine ratios, and ensure equal
distribution. Their application is especially important in
simplifying fractions, dividing distances or time evenly,
and standardizing measurements.
By deeply understanding this topic, not only is
theoretical knowledge strengthened, but it also creates
an opportunity to find clear solutions to many practical
problems encountered in real life. There are several
methods for finding the GCD and LCM, each based on
different stages and logical approaches. Along with
methods based on divisors and factors, efficient
methods such as the Euclidean algorithm are also
widely used. By learning these methods, students
develop logical thinking and strengthen their
mathematical skills.
Theoretical basis of the concepts of GCD and LCM
The Greatest Common Divisor (GCD) is the largest
positive number that divides each of two or more
natural numbers. The Least Common Multiple (LCM),
on the other hand, is the smallest positive number that
is a multiple of each of the given numbers. These
concepts are fundamental elements of arithmetic and
number theory, through which relationships and ratios
between numbers are determined.
For example, let us take the numbers 12 and 18.
Divisors of 12: 1, 2, 3, 4, 6, 12. Divisors of 18: 1, 2, 3, 6,
9, 18. Their common divisors: 1, 2, 3, 6. Thus, GCD
(12, 18) = 6
For 4 and 6: Multiples of 4: 4, 8, 12, 16, 20, 24. Multiples
of 6: 6, 12, 18, 24, 30
Common multiples: 12, 24, 36...Thus, LCM(4, 6) = 12
Methods of finding GCD and LCM
a) Through determining divisors
In this method, all divisors of each number are
identified. Then, their common divisors are found, and
the largest is selected
—
this is the GCD. To find the
LCM, the multiples of each number are written in
sequence, and the first common multiple is
determined. This method is convenient for small
numbers, but as the numbers grow, the method
becomes inconvenient and time-consuming.
Example 1: Find GCD(20, 30)
Solution:
Divisors of 20: 1, 2, 4, 5, 10, 20
Divisors of 30: 1, 2, 3, 5, 6, 10, 15, 30
Common divisors: 1, 2, 5, 10
GCD = 10
International Journal of Pedagogics
152
https://theusajournals.com/index.php/ijp
International Journal of Pedagogics (ISSN: 2771-2281)
Example 2: Find LCM(8, 12)
Solution:
Multiples of 8: 8, 16, 24, 32, 40, 48...
Multiples of 12: 12, 24, 36, 48, 60...
Common multiples: 24, 48...
LCM = 24
b) Prime factorization method
Each number is factorized into prime factors. For GCD
–
only the smallest powers of the common prime
factors are taken. For LCM
–
the highest power of each
prime factor is taken.
Example:
60 = 2² × 3 × 5
48 = 2⁴ × 3
GCD(60, 48) = 2² × 3 = 12
LCM(60, 48) = 2⁴ × 3 × 5 = 240
This method is useful for reinforcing mathematical logic
and is especially helpful when dealing with many
numbers.
Example 3: Find GCD(72, 120)
Solution:
72 = 2³ × 3²
120 = 2³ × 3 × 5
Common prime factors: 2³, 3 (only the smallest powers
of common prime factors are taken)
GCD = 2³ × 3 = 8 × 3 = 24
Example 4: Find LCM(18, 30)
Solution:
18 = 2 × 3²
30 = 2 × 3 × 5
All prime factors: 2, 3², 5 (the highest powers of each
prime factor are taken)
LCM = 2 × 3² × 5 = 90
c) Euclidean algorithm
What is the significance of this property? This property
allows replacing the given numbers with smaller ones
when finding their GCD, simplifying the calculations.
Such replacement can be performed several times.
1. The larger of the two numbers is divided by the
smaller.
2. The remainder becomes the new number.
3. This process is repeated until the remainder is zero.
4. The remainder just before zero is the GCD.
Example:
Divide 525 by 231 with remainder, getting 63. So,
D(525, 231) = D(231, 63)
Divide 231 by 63: 231 = 63•3 + 42 → D(231, 63) = D(63,
42)
Divide 63 by 42: 63 = 42•1 + 21 → D(63, 42) = D(42, 21)
Divide 42
by 21: remainder is 0 → D(42, 21) = D(21, 0)
The GCD of 21 and 0 is 21
Thus, the GCD of 525 and 231 is 21.
We often write calculations like this:
525 = 231 • 2 + 63
231 = 63 • 3 + 42
63 = 42 • 1 + 21
42 = 21 • 2 + 0
GCD(525, 231) = 21
This method of finding the greatest common
divisor is based on division with remainder. It was first
created by the ancient Greek mathematician Euclid
(3rd century BC), hence it's known as the Euclidean
algorithm. The general form of the Euclidean algorithm
is as follows:
Let a and b be natural numbers and a > b. a is
divided by b with remainder, then b is divided by the
remainder, and then the first remainder is divided by
the second remainder, and so on. In this case, the
remainder different from zero at the last step is the
GCD of a and b.
Example 5: Find GCD(105, 60) using Euclidean
algorithm
Solution:
105 ÷ 60 = remainder 45
60 ÷ 45 = remainder 15
45 ÷ 15 = remainder 0
GCD = 15
This algorithm is also used in modern computer
systems because it is fast, efficient, and easy to code.
d) Finding LCM through GCD
In this method, the product of two numbers is divided
by their GCD:
LCM(a, b) = (a × b) / GCD(a, b)
Example: a = 12, b = 18
GCD(12, 18) = 6
LCM = (12 × 18) / 6 = 216 / 6 = 36
In this approach, it is enough to find the GCD; the LCM
is automatically obtained.
The concepts of Greatest Common Divisor
(GCD) and Least Common Multiple (LCM) are important
foundations used not only in arithmetic, but also widely
in algebra, number theory, algorithms, and
cryptography. When determining these concepts,
various methods
—
in particular, the Euclidean
algorithm, the method of factorization, solving through
linear expressions, and other modern algorithmic
approaches
—
when studied comparatively, each has
its own advantages and disadvantages.
Experience shows that for small numbers, the
factorization method is sufficiently convenient and
understandable, while for large numbers, the Euclidean
algorithm stands out for its efficiency, simplicity, and
speed. Especially from the perspective of computing
technology and algorithmic complexity, the Euclidean
method is used as an optimal solution in many modern
programming languages. At the same time,
understanding the formulas derived using the GCD in
LCM calculation allows for deeper comprehension of
mathematical relationships.
International Journal of Pedagogics
153
https://theusajournals.com/index.php/ijp
International Journal of Pedagogics (ISSN: 2771-2281)
Analysis of theoretical sources and practical
examples shows that studying this topic in depth is
relevant not only at the general education level but also
in academic and practical fields. Through such laws of
commonality and harmony among numbers, students
develop mathematical thinking, shape algorithmic
reasoning, and become ready to use mathematical
approaches in solving real-life problems.
As a result, it can be said that a deep
understanding of methods for finding GCD and LCM
lays a strong foundation for transitioning to other
branches of mathematics. This serves as an essential
basis for mastering even more complex mathematical
concepts in the future.
REFERENCES
1. B.S. Abdullayeva, A.V. Sadikova, N.A. Khamedova,
N.M. Mukhitdinova, M.I. Toshpulatova. Theory of the
Course of Elementary Mathematics. “Tafakkur Bostoni”
Publishing House, Tashkent, 2018
–
496 pages.
2. Qurbonov R., Qosimova G. (2021). Operations on
Numbers and Their Properties.
—
Tashkent: TDPU
Publishing House.
3. To‘xtasinov A. R. (2018). Introduction to
Mathematical Analysis.
—
Tashkent: “Science and
Technologies” Publishing House.
4. Yusupov B. B. (2015). Fundamentals of Discrete
Mathematics.
—
Tashkent: Publishing House of the
National University of Uzbekistan.
5. Ministry of Higher and Secondary Specialized
Education of the Republic of Uzbekistan. (2019).
Mathematics: Textbook (for undergraduate level).
—
Tashkent.
6. Qurbonov R., Qosimova G. Methodology of Teaching
Mathematics in Primary Education.
—
Tashkent: TDPU
Publishing House, 2021.
7. Hardy G. H., Wright E. M. An Introduction to the
Theory of Numbers.
—
Oxford University Press, 2008.
Internet sources:
1. https://uz.wikipedia.org
2. https://arxiv.uz
