Number Theory

GCD-LCM

GCD (Greatest Common Divisor) or HCF (Highest Common Factor)

gcd(n1,n2) – gcd of two natural numbers is the greatest natural number which divides them both. e.g

$n_1 = g \times x$
$n_2 =g \times y$
x and y have to be co-prime. Therefore gcd if x & y should be 1 i. e gcd(x,y) =1
g is the smaller power of each common prime factor.

$18 = 2^1 \times 3^2$
$24 = 2^3 \times 3^1$
Take the lowest power of 2 and 3 from both i.e $2^1 and 3^1$ Therefore gcd us 6
GCD is one of the factors of those two numbers

LCM (Least Common Multiple)

$18 = 2^1 \times 3^2$
$24 = 2^3 \times 3^1$
Take the highest power of 2 and 3 from both i.e $2^3 and 3^2$ Therefore LCM is 72
The two numbers are one of the factors of LCM. We can also say LCM is the multiple of two numbers.
LCM of two co-prime numbers is the multiplication of those two numbers. LCM(a,b) = a x b when a & b are co-prime

Relation among H.C.F, L.C.M and Numbers

Two positive integers a & b

(1) $\begin{equation*} a \times b= H.C.F_{(ab)} \times L.C.M_{(ab)}\end{equation*}$

Note: Applicable for only 2 numbers.

(2) $\begin{equation*} H.C.F_{(ab)} = H.C.F_{(a,b+an)} \end{equation*}$

The above equation is very useful while finding the GCD. Say n=-1 & b>a
b+an will reduce b. e.g
GCD(20,68) = GCD (20,68-3*20)=GCD(20,8)
GCD(8,20) = GCD(8,20-2*8)=GCD(8,4) = 4

Using the above principle we can say

Any two consecutive numbers are co-prime. Therefore gcd(n,n+1) = 1 e.g gcd(55,56) = gcd(78,79) = 1
Any two consecutive odd numbers are co-prime. Therefore gcd(2n+1, 2n+3) = 1 e.g gcd(15,17) = gcd(53,55) = 1
Any two consecutive even numbers have gcd 2. Therefore gcd(2n, 2n+2) = 2 e.g gcd(14,16) = gcd(14,2) = 2

Three positive integers a b & c

(3) $\begin{equation*} L.C.M_{(abc)}=\frac{abc \times H.C.F_{(abc)}}{H.C.F_{(ab)} \times H.C.F_{(bc)} \times H.C.F_{(ac)}}\end{equation*}$

(4) $\begin{equation*} H.C.F_{(abc)}=\frac{abc \times L.C.M_{(abc)}}{L.C.M_{(ab)}\times L.C.M_{(bc)}\times L.C.M_{(ac)}}\end{equation*}$

From the above two equations:

(5) $\begin{equation*} a^2 \times b^2 \times c^2=H.C.F_{(ab)} \times L.C.M_{(ab)} \times H.C.F_{(bc)} \times L.C.M_{(bc)} \times H.C.F_{(ac)}} \times L.C.M_{(ac)}}\end{equation*}$

Questions

Q. GCD of $2^7 \times 3^2 \times 5^b$ and $2^a \times 7^2 \times 5^3$ is $2^a \times 5^3$ find the minimum value of a+b. [Ans – 3]

Q. Find the smallest and largest three-digit numbers which are divisible by 4,6 and 15 [Ans – 120,960]

Q. Find the greatest number which divides 196, 154 & 84 [Ans – 14]

Q. For two positive integers, LCM is 240 and HCF is 10. There
i. is exactly one such pair
ii. are exactly two such pairs
iii. are exactly three such pairs
[Ans – ii. are exactly two such pairs]
Two numbers 10x and 10y. Where x and y are co-prime
$LCM=240=10xy$ two pairs are (10,240) and (30,80)

Q. The product of two positive integers is 9984 and the greatest common factor of those integers equals that difference between them. What are the two integers?
A. lets two numbers are a = gx and b = gy
$\because g = a - b = gx -gy$
$\therefore x-y = 1$ , which means one of them will be odd and other one will be even
$\because ab= g^2xy=9984$
$\therefore g^2xy=2^8 \times 3 \times 13$ , x and y are co-prime i.e g(x,y)=1
From the above equation, the possible value of g could be { $2^0,2^1,2^2,2^3,2^4$ }

Case-1: $2^0$ i.e g = 1. In this case, the multiplication of two co-prime should be 9984. As one of them has to be even and the other odd, so
option-1: $2^8 \times 3$ and 13, but the difference between co-prime will not be 1
option-2: $2^8 \times 13$ and 3, but the difference between co-prime will not be 1
option-3: $2^8 \times 3 \times 13$ and 1, but the difference between co-prime will not be 1
So this case is not possible.

Case-2: $2^1$ i.e g = 2. In this case, the multiplication of two co-prime should be $2^6 \times 3 \times 13$ . As one of them has to be even and the other odd, so
option-1: $2^6 \times 3$ and 13, but the difference between co-prime will not be 1
option-2: $2^6 \times 13$ and 3, but the difference between co-prime will not be 1
option-3: $2^6 \times 3 \times 13$ and 1, but the difference between co-prime will not be 1
So this case is not possible.

Case-3: $2^2$ i.e g = 4. In this case, the multiplication of two co-prime should be $2^4 \times 3 \times 13$ . As one of them has to be even and the other odd, so
option-1: $2^4 \times 3$ and 13, but the difference between co-prime will not be 1
option-2: $2^4 \times 13$ and 3, but the difference between co-prime will not be 1
option-3: $2^4 \times 3 \times 13$ and 1, but the difference between co-prime will not be 1
So this case is not possible.

Case-4: $2^3$ i.e g = 8. In this case, the multiplication of two co-prime should be $2^2 \times 3 \times 13$ . As one of them has to be even and the other odd, so
option-1: $2^2 \times 3$ and 13, but the difference between co-prime will be 1
option-2: $2^2 \times 13$ and 3, but the difference between co-prime will not be 1
option-3: $2^2 \times 3 \times 13$ and 1, but the difference between co-prime will not be 1.
Therefore, two co-prime numbers are 12 & 13. The GCD is 8.
And the two numbers are 96 and 104

Q. Three numbers which are coprime to each other are such that the product of the first two is 551 and that of the last two is 1073. What is the sum of three numbers?
A. Method 1:
xy = 551, As the product is odd. So both number has to be odd. i.e x & y both are odd
zy=1073, Similarly z & y both are odd.
zy-xy=1073-551
y(z-x)=522=18*29, as y is odd so z-x has to be even to make the product even.
Therefore y = 29
From xy = 551 abd yz=1073, x=19 & z = 37
19+29+37 = 85

Method 2:
All are coprime to each other. Therefore,
n1 = xy = 551
n2 = yz = 1073
y is the gcd (n1,n2) i.e gcd(551,1073) = gcd(551,1073-551) = gcd(551, 522)=gcd(522,551-522)=gcd(522,29)=29
As y is the common factor between xy and yz. And y can be 1 or 29.
if y =1 then x = 551 and z = 1073
As per questions x y z all are coprime. But 551 and 1073 have common factor 29. So y=1 not possible.
Therefore y =29, x=19 & z = 37

GCD-LCM

GCD (Greatest Common Divisor) or HCF (Highest Common Factor)

LCM (Least Common Multiple)

Relation among H.C.F, L.C.M and Numbers

Two positive integers a & b

Three positive integers a b & c

Questions

Table of Contents

You may also like to read

Cyclicity of Number

Popular content

contact us