ગુરુત્તમ સામાન્ય અવયવ અને લઘુત્તમ સામાન્ય અવયવી કેલ્ક્યુલેટર

Greatest common divisor (GCD, GCF or HCF) and least common multiple (LCM) of two or more whole numbers, with Euclid's algorithm step by step.

અપડેટ કરેલું 28 સપ્ટેમ્બર, 2026તપાસેલાં ઉદાહરણો: 6

Greatest common divisor

પૂર્ણ સંખ્યા; સૌથી નજીક; સરખા અંતરે શૂન્યથી દૂર

Least common multiple: 180

The largest number dividing 12, 18 and 30 exactly is 6; the smallest positive number they all divide into is 180.

Euclid's algorithm as squares: 12 × 18 rectangle

Euclid's algorithm, a = q·b + r પંક્તિઓ: 3

Pair	a	b	Quotient q	Remainder r
gcd(12, 18)	18	12	1	6
gcd(12, 18)	12	6	2	0
gcd(6, 30)	30	6	5	0

ગણતરી કેવી રીતે થાય છે S

Euclid's algorithm for gcd(12, 18)
$\begin{aligned}18 &= 1 \times 12 + 6 \\ 12 &= 2 \times 6 + 0\end{aligned} \qquad \Rightarrow \gcd = 6$
Divide, keep the remainder, repeat with the divisor; the last non-zero remainder is the gcd.
Least common multiple with 18
$\operatorname{lcm}(12, 18) = \frac{12 \times 18}{\gcd(12, 18)} = \frac{216}{6} = 36$
Euclid's algorithm for gcd(6, 30)
$\begin{aligned}30 &= 5 \times 6 + 0\end{aligned} \qquad \Rightarrow \gcd = 6$
Divide, keep the remainder, repeat with the divisor; the last non-zero remainder is the gcd.
Least common multiple with 30
$\operatorname{lcm}(36, 30) = \frac{36 \times 30}{\gcd(36, 30)} = \frac{1{,}080}{6} = 180$

ગુરુત્તમ સામાન્ય અવયવ અને લઘુત્તમ સામાન્ય અવયવી કેલ્ક્યુલેટર વિશે

The greatest common divisor (GCD, also called the greatest common factor or highest common factor) is the largest whole number that divides every input; the least common multiple (LCM) is the smallest positive number that every input divides. Euclid's algorithm finds the GCD by repeatedly replacing the larger number with its remainder after division by the smaller: gcd(1071, 462) = gcd(462, 147) = gcd(147, 21) = 21. The LCM follows from lcm(a, b) = |a × b| ÷ gcd(a, b), applied a pair at a time.

Reducing fractions uses the GCD; adding fractions and lining up repeating schedules use the LCM. For the default 12, 18 and 30 the GCD is 6 and the LCM is 180, so events every 12, 18 and 30 days next coincide after 180 days.

For two numbers the calculator also gives the Bézout identity from the extended Euclidean algorithm: 21 = 1071 × (−3) + 462 × 7. Negative inputs count by their absolute value, gcd(0, n) = n, and a list containing 0 has an LCM of 0.

ઉકેલેલાં ઉદાહરણો

12, 18 and 30

Whole numbers: 12, 18, 30

Greatest common divisor: 6
Least common multiple: 180

ચકાસણીનો સ્ત્રોત: Python 3.8 math.gcd and a·b // gcd folded over the list

Euclid's 1071 and 462

Whole numbers: 1071, 462

Greatest common divisor: 21
Least common multiple: 23,562
Bézout identity: 21 = 1071·(−3) + 462·7

ચકાસણીનો સ્ત્રોત: Wikipedia — Euclidean algorithm worked example (gcd 21); lcm and Bézout coefficients by hand back-substitution, checked in Python

Extended Euclid on 240 and 46

Whole numbers: 240 46

Greatest common divisor: 2
Least common multiple: 5,520
Bézout identity: 2 = 240·(−9) + 46·47

ચકાસણીનો સ્ત્રોત: Wikipedia — Extended Euclidean algorithm example table (s = −9, t = 47)

Coprime 17 and 31

Whole numbers: 17, 31

Greatest common divisor: 1
Least common multiple: 527

ચકાસણીનો સ્ત્રોત: Both prime, so gcd 1 and lcm 17 × 31 = 527

પ્રશ્નો

How do you find the GCD of two numbers?

Use Euclid's algorithm: divide the larger number by the smaller, keep the remainder, and repeat with the divisor and the remainder until the remainder is 0; the last non-zero remainder is the GCD. For 1071 and 462: 1071 = 2 × 462 + 147, 462 = 3 × 147 + 21, 147 = 7 × 21 + 0, so the GCD is 21. By Lamé's theorem it never needs more than five steps per digit of the smaller number.

How do you find the LCM of two numbers?

Divide their product by their GCD: lcm(a, b) = a × b ÷ gcd(a, b). For 12 and 18, gcd = 6, so lcm = 216 ÷ 6 = 36. For more numbers, go one pair at a time: lcm(36, 30) = 1,080 ÷ 6 = 180, so the LCM of 12, 18 and 30 is 180. Listing multiples (12, 24, 36 …) reaches the same answer, but slowly for large numbers.

What is the difference between GCD, GCF and HCF?

There is none: greatest common divisor (GCD), greatest common factor (GCF) and highest common factor (HCF) are three names for the same number. GCF and HCF are the usual school terms, GCF mostly in the US and HCF in the UK and India, while GCD is the name in number theory and programming, as in Python's math.gcd. Under every name, gcd(12, 18) = 6.

How are the GCD and LCM related?

For two positive whole numbers, gcd(a, b) × lcm(a, b) = a × b; with 12 and 18, 6 × 36 = 216 = 12 × 18. In prime factors, the GCD takes the lower power of each shared prime and the LCM the higher power of every prime: 12 = 2² × 3 and 18 = 2 × 3², so the GCD is 2 × 3 = 6 and the LCM is 2² × 3² = 36. The product rule does not extend to three or more numbers.

What does it mean when two numbers are coprime?

Their GCD is 1, so they share no prime factor, and their LCM is simply their product. 17 and 31 are coprime, with an LCM of 17 × 31 = 527, and so are 8 and 15 although neither is prime. A fraction is in lowest terms exactly when its numerator and denominator are coprime.

“ગુરુત્તમ સામાન્ય અવયવ અને લઘુત્તમ સામાન્ય અવયવી કેલ્ક્યુલેટર” કેટલું ચોક્કસ છે?

ચોકસાઈ તમારા ઇનપુટ અને પદ્ધતિની ધારણાઓ પર આધારિત છે. દશાંશ ગણતરી 50 સાર્થક અંકો વાપરે છે, પરંતુ અંદાજ, સંખ્યાત્મક પદ્ધતિઓ અને મૂળ ડેટા ઓછા ચોક્કસ હોઈ શકે છે; દર્શાવેલા મૂલ્યોને રાઉન્ડ કરવાથી આ મર્યાદાઓ દૂર થતી નથી. સ્વતંત્ર સ્ત્રોતોના ઉકેલેલા ઉદાહરણો સાથે ચકાસણી: 6. ઉદાહરણ તરીકે, “12, 18 and 30”ને Python 3.8 math.gcd and a·b // gcd folded over the list સાથે ચકાસવામાં આવે છે.

આ પદ્ધતિનો સ્ત્રોત શું છે?

Euclid, Elements, Book VII, Propositions 1–2; Knuth, The Art of Computer Programming Vol. 2, §4.5.2 (Euclid's algorithm); Wikipedia — Extended Euclidean algorithm (worked example 240, 46).

આ કેલ્ક્યુલેટર વિશે

\begin{gathered} \gcd(a, b) = \gcd(b,\ a \bmod b) \\[6pt] \gcd(a, 0) = |a| \\[10pt] \operatorname{lcm}(a, b) = \frac{|a\,b|}{\gcd(a, b)} \end{gathered}

સ્રોતો

Euclid, Elements, Book VII, Propositions 1–2
Knuth, The Art of Computer Programming Vol. 2, §4.5.2 (Euclid's algorithm)
Wikipedia — Extended Euclidean algorithm (worked example 240, 46)

સંદર્ભો સાથે ચકાસેલાં

આ કેલ્ક્યુલેટરમાં સ્વતંત્ર સ્રોતોના જવાબો ધરાવતા 6 ઉકેલેલાં ઉદાહરણો છે. તે પરીક્ષણ સમૂહમાં ચાલે છે અને તમે અહીં પણ ચલાવી શકો છો.

Euclid's algorithm as squares: 12 × 18 rectangle

Euclid's algorithm for gcd(12, 18)

Least common multiple with 18

Euclid's algorithm for gcd(6, 30)

Least common multiple with 30