The research paper published by IJSER journal is about Relation between N numbers and their LCMs and GCDs 1

ISSN 2229-5518

Relation between N numbers and their LCMs and

GCDs

C.S.Abhishek

Abstract— This paper explains the relation among product of ‘n’ natural numbers and the LCMs and GCDs of all combinations of these numb ers. It is known that the product of two numbers is equal to the product of their LCM and GCD. There is also a relation for three numbers. In this paper I am going to introduce two generalized relations for ‘n’ natural numbers.

Index Terms — N numbers , Product , LCM (Least Common Multiple) , GCD (Greatest Common Multiple) , Relation-1, Relation-2 , Odd , Even

——————————  ——————————

1 Introduction

We know that if a, b are two numbers then their product is equal to product of their LCM and GCD
i.e. axb =LCM (a,b) × GCD (a,b)
and also we know that if a,b,c are 3 numbers then
LCM (a,b,c) = [a × b × c × GCD (a,b,c)] /[GCD (a,b) × GCD (b,c) × GCD(c,a)]
GCD (a,b,c) = [a × b × c × LCM (a,b,c)] /[LCM (a,b) × LCM (b,c) × LCM(c,a)]
In this paper I am going to introduce two generalized formu- lae and their proof for ‘n’ natural numbers. The product of ‘n’ numbers can be expressed in terms of LCMs and GCDs of dif- ferent combinations in two different ways as Relation 1 and Relation 2.

C.S.Abhishek is studying 9th Class (during 2011-12) in St.Claire

High School,Ramagundam, Dist:Karimnagar,A.P.,India. E-mail: nathcvr@yahoo.co.in

2 Relations

The Product of ‘n’ numbers can be expressed in two forms i.e,
Relation 1 and Relation 2 as below:
Let a1,a2,a3……….an−1 , an be ‘n’ natural numbers

Relation - 1

a1×a2×a3……….an−1×an =

The product of GCDs of all sets containing even no. of Elements × LCM(of all numbers.)

The product of GCDs of all sets containing odd no. of elements (except 1)

Relation - 2 a1×a2×a3……….an−1×an =

The product of LCMs of all sets containing even no. of Elements × GCD(of all numbers.)

The product of LCMs of all sets containing odd no. of elements (except 1)

3 Proof of Relation 1 1st Relation

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about Relation between N numbers and their LCMs and GCDs 2

ISSN 2229-5518

Now let us prove the 1st Relation i.e. a1×a2×a3……….an−1×an =
The product of GCDs of all sets containing even no. of Elements × LCM(of all numbers.)

The product of GCDs of all sets containing odd no. of elements (except 1)
Let a1,a2,a3……….an−1,an be ‘n’ natural numbers
The above equation can be rearranged as
a1×a2×a3……….an-1 x an × The product of GCDs of all sets containing odd no. of elements(except 1)

1=
The product of GCDs of all sets containing even no. of Elements × LCM(of all numbers)
Let
a1 =2^(x1)×3^(y2)×5^(z3)…………….
a2= 2^(x3)×3^(y4)×5^(z1)…………….
:
:
:
an=2^(xn)×3(y1)×5^(zn-1)×……………..
(all numbers are taken in random)
(all exponents are whole numbers only) Let us assume
x1≤ x2 ≤ x3…………………….xn−1 ≤ xn
y1 ≤ y2 ≤ y3……………………….yn−1 ≤ yn
and so on.
Similarly with all other exponents of prime factors. Let us take Numerator
a1×a2×a3……….an−1×an × The product of GCDs of all sets
containing odd no. of elements(except 1) = 2q×3r×5s….pt
For some {q, r, s……………………… t} ∈ N
LCM (or GCD) of n numbers = Product of LCM (or GCD) of
each of its prime factors with same base.
So for 2 powers we apply the above relation
We take elements as A= {2^(x1),2^(x2)…….2^(xn-1),2^(xn)} ( x1 ≤ x2 ≤ x3…………………….xn−1 ≤ xn )
Let solution is =2q
To know the value of q it is necessary to find the number of sets
No. of sets containing odd no. of elements with 2^(x1) as GCD
are :
With 3no`s {2^(x1), a, b} a and b are any two numbers of
set A. There can be n−1C2 such sets possible.
With 5no`s {2^(x1), a, b, c, d} a, b, c and d are any 4
numbers of set A. There can be n−1C4 such sets possible
………… and so on.
No of sets containing odd no. of elements with 2^(x2) as GCD
are :
With 3no`s {2^(x2), a, b} a and b are any two numbers of
set A. There can be n−2C2 such sets possible
With 5no`s {2^(x2), a, b, c, d} a, b, c and d are any 4
numbers set A. There can be n−2C4 such sets possible
………………..and so on
Solution =2q
If we multiply GCD s (odd) and product of the numbers, we get
q = x1{n−1C2 + n−1C4 + n−1C6 ………………………} + x2{n−2C2 +

n−2C4 + n−2C6 ………………............} +x3{n−3C2

+n−3C4+n−3C6………….} +…………...xn−2{2C2}+x1+x2 ……………
xn−1 +xn
the above relation can be simplified as
q = x1{1+n−1C2+n−1C4+n−1C6……………………} +
x2{1+n−2C2+n−2C4+n−2C6………………....} + x3 {1+ n−3C2+ n−3C4
+n−3C6 ………….} ………….. + xn−2 {1+2C2} + xn−1 +xn
the above relation can be further rewritten as
q = x1{n−1C0+n−1C2+n−1C4+n−1C6 ………………………} + x2{n−2C0+n−2C2+ n−2C4 +n−2C6…………............}+x3 {n−3C0 + n−3C2+ n−3C4 +n−3C6………….} +…………..xn−2{2C0+2C2} + xn−1 +xn
Now let us take Denominator i .e
The product of GCDs of all sets containing even no. of Ele- ments × LCM(of all numbers)
Let

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about Relation between N numbers and their LCMs and GCDs 3

ISSN 2229-5518

The product of GCDs of all sets containing even no. of Ele- ments × LCM(of all numbers) = 2u
= [x {n−1C + n−1C
+ n−1C + n−1C
………………} − { n−1C + n−1C

1 0 2 4 6 1 3

So we take elements as A= {2^(x1),2^(x2)…2^(xn-1),2^(xn)} ( x1≤x2≤x3…………………….xn−1≤xn )
Let solution is =2u
So no. of sets containing even no. of elements with 2^(x1) as
GCD are :
With 2no`s {2^(x1), a } a is any other number from set A.
There can be n−1C1 such sets possible
With 4no`s {2^(x1), a, b, c,} a, b and c are any 3 numbers from set A. There can be n−1C3 such sets
possible
…………….and so on.
So no of sets containing even no. of elements with 2^(x2) as
GCD are:
With 2no`s {2^(x2), a, } a is any number from set A.
There can be n−2C1 such sets possible
With 4no`s {2^(x2), a, b, c,} a, b and c are any 3 numbers
from seta. There can be n−2C3 such sets possible
……………….and so on
Solution =2^u
If we multiply GCD s(even) and LCM of the numbers, we get
u = x1{n−1C1 + n−1C3 + n−1C5 + n−1C7 ………………………}
+x2{n−2C1 + n−2C3 + n−2C5 + n−2C7………………............}+ x3{n−3C1 + n−3C3 + n−3C5 + n−3C7………………….……….} + …………. xn−1{1C1} + xn (xn is LCM of all numbers )
If this relation is correct,then
Numerator/Denominator = 1
Substituting values, we get
2^q / 2^u = 1
2^(q–u) = 1 q–u = 0
So if q–u = 0 is proved,the above relation is true for n numbers
Let us check this
Substituting values of q and u
We get
[x1{n−1C0+n−1C2+n−1C4+n−1C6………………………}+
+ n−1C5 + n−1C7 ………………………} ] + [x2{n−2C0 + n−2C2 + n−2C4
+ n−2C6……..} − {n−2C1+n−2C3+n−2C5+n−2C7………………............}]
…..+xn–xn+xn−1–xn−1

since we know the relation

“(nC0+nC2+nC4+nC6……)= (nC1+nC3+nC5+nC7…………)”

(nC0+nC2+nC4+nC6………)−(nC1+nC3+nC5+nC7………) =0
using above relation
[x1{n−1C0 + n−1C2 +n−1C4 + n−1C6 ………………………} − { n−1C1 + n−1C3 + n−1C5 + n−1C7 ………………………} ] + [x2{n−2C0+n−2C2+ n−2C4 + n−2C6……..} − {n−2C1 + n−2C3 + n−2C5 + n−2C7………...}]
…………… + xn − xn + xn−1 − xn−1
i.e.,
(x1×0)+(x2×0)…………………+0 =0
So q-u =0 ,
Similarly for all other primes(3,5,7….etc) and their powers it
holds true.
Similarly for all numbers because every number is product of primes and their powers.
a1×a2×a3……….an−1×an × The product of GCDs of all sets containing odd no. of elements(except 1)

1=
The product of GCDs of all sets containing even no. of Elements × LCM(all numbers)
i.e., a1×a2×a3……….an−1×an =
The product of GCDs of all sets containing even no. of
Elements × LCM(all numbers.)
The product of GCDs of all sets containing odd no. of

elements (except 1)

Hence Relation 1 is proved

4 Proof of Relation 2

2nd Relation

Now let us prove the 2nd relation i.e.
x2{n−2C0+n−2C2+n−2C4+n−2C6 .....} + x3{n−3C0+n−3C2+n−3C4+n−3C6
………….………….} + …………..xn−2{2C0+2C2} + xn−1 + xn] –
a1×a2×a3……….a

n−1×an =

[x1{n−1C1 +n−1C3 + n−1C5 + n−1C7 + ………………………} +
x2{n−2C1+n−2C3+n−2C5+n−2C7 ….....} + x3{n−3C1+n−3C3+n−3C5+n−3C7
……..………….}+ …………. xn−1{1C1} + xn ]
The product of LCMs of all sets containing even no. of Elements × GCD(all numbers.)

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about Relation between N numbers and their LCMs and GCDs 4

ISSN 2229-5518

The product of LCMs of all sets containing odd no. of elements (except 1)
Let a1,a2,a3……….an−1,an be ‘n’ natural numbers
The above equation can be rearranged as
a1×a2×a3……….an-1 x an × The product of LCMs of all sets containing odd no. of elements(except 1)

1=
The product of LCMs of all sets containing even no. of Elements × GCD(of all numbers)
Let
a1 =2^(x1)×3^(y2)×5^(z3)…………….
a2= 2^(x3)×3^(y4)×5^(z1)…………….
:
:
:
an=2^(xn)×3(y1)×5^(zn-1)×……………..
(all numbers are taken in random)
(all exponents are whole numbers only) Let us assume
x1≥ x2 ≥ x3…………………….xn−1 ≥ xn
y1 ≥ y2 ≥ y3……………………….yn−1 ≥ yn
and so on.
Similarly with all other exponents of prime factors. Let us take Numerator
a1×a2×a3……….an−1×an × The product of GCDs of all sets
containing odd no. of elements(except 1) = 2q×3r×5s….pt
For some {q, r, s……………………… t} ∈ N
LCM (or GCD) of n numbers = Product of LCM (or GCD) of
each of its prime factors with same base.
So for 2 powers we apply the above relation
We take elements as A= {2^(x1),2^(x2)…….2^(xn-1),2^(xn)} ( x1 ≥ x2 ≥ x3…………………….xn−1 ≥ xn )
Let solution is =2q
To know the value of q it is necessary to find the number of sets
No. of sets containing odd no. of elements with 2^(x1) as LCM
are :
With 3no`s {2^(x1), a, b} a and b are any two numbers of
set A. There can be n−1C2 such sets possible
With 5no`s {2^(x1), a, b, c, d} a, b, c and d are any 4
numbers of set A. There can be n−1C4 such sets possible
………… and so on.
No of sets containing odd no. of elements with 2^(x2) as LCM
are:
With 3no`s {2^(x2), a, b} a and b are any two numbers of
set A. There can be n−2C2 such sets possible
With 5no`s {2^(x2), a, b, c, d} a, b, c and d are any 4
numbers set A. There can be n−2C4 such sets possible
………………..and so on
Solution =2q
If we multiply LCMs (odd) and product of the numbers, we get
q = x1{n−1C2 + n−1C4 + n−1C6 ………………} + x2{n−2C2 + n−2C4 +

n−2C6 ………………............} + x3 {n−3C2 +n−3C4+n−3C6………….}

+…………...xn−2{2C2}+x1+x2 …………… xn−1 +xn
the above relation can be simplified as
q = x1{1 + n−1C2 + n−1C4 + n−1C6 ……………………} + x2{1 + n−2C2
+ n−2C4 + n−2C6………………....} + x3 {1+ n−3C2+ n−3C4 +n−3C6
………….} ………….. + xn−2 {1+2C2} + xn−1 +xn
the above relation can be further rewritten as
q = x1{n−1C0 + n−1C2 + n−1C4 + n−1C6 ………………………} + x2{n−2C0 + n−2C2+ n−2C4 +n−2C6…………............} + x3 {n−3C0 + n−3C2+ n−3C4 +n−3C6………….} +…………..xn−2{2C0+2C2} + xn−1
+xn
Now let us discuss about Denominator i .e
The product of LCMs of all sets containing even no. of Ele- ments × GCD (of all numbers)
Let
The product of LCMs of all sets containing even no. of Ele- ments × GCD(of all numbers) = 2u
So we take elements as A= {2^(x1),2^(x2)…2^(xn-1),2^(xn)}
( x1≥x2≥x3…………………….xn−1≥xn ) Let solution is =2u

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about Relation between N numbers and their LCMs and GCDs 5

ISSN 2229-5518

So no. of sets containing even no. of elements with 2^(x1) as
LCM are
With 2no`s {2^(x1), a } a is any other number from set A.
There can be n−1C1 such sets possible
With 4no`s {2^(x1), a, b, c,} a, b and c are any 3 numbers

“(nC0+nC2+nC4+nC6……)= (nC1+nC3+nC5+nC7…………)”

(nC0+nC2+nC4+nC6………)−(nC1+nC3+nC5+nC7………) =0
using above relation
[x1{n−1C0 + n−1C2 +n−1C4 + n−1C6 ………………………} − { n−1C1 +
from set A. There can be n−1C3 such sets

n−1C

+ n−1C
+ n−1C
………………………} ] + [x {n−2C +n−2C +
possible

3 5 7

2 0 2

…………….and so on.
So no of sets containing even no. of elements with 2^(x2) as
LCM are
With 2no`s {2^(x2), a, } a is any number from set A.
There can be n−2C1 such sets possible
With 4no`s {2^(x2), a, b, c,} a, b and c are any 3 numbers
from set A. There can be n−2C3 such sets possible
……………….and so on
Solution =2u
If we multiply LCM s(even) and GCD of the numbers, we get
u = x1{n−1C1 + n−1C3 + n−1C5 + n−1C7 ………………………}
+x2{n−2C1 + n−2C3 + n−2C5 + n−2C7………………............}+ x3{n−3C1 + n−3C3 + n−3C5 + n−3C7………………….……….} + …………. xn−1{1C1} + xn (xn is GCD of all numbers )
If this relation is correct,then
Numerator/Denominator = 1
Substituting values, we get
2q / 2u = 1
2(q–u) = 1 q–u = 0
So if q–u = 0 is proved,the above relation is true for n numbers
Let us check this
Substituting values of q and u
We get
[x1{n−1C0+n−1C2+n−1C4+n−1C6………………………}+
x2{n−2C0+n−2C2+n−2C4+n−2C6 .....} + x3{n−3C0+n−3C2+n−3C4+n−3C6
………….………….} + …………..xn−2{2C0+2C2} + xn−1 + xn] –
[x1{n−1C1 +n−1C3 + n−1C5 + n−1C7 + ………………………} +
x2{n−2C1+n−2C3+n−2C5+n−2C7 ….....} + x3{n−3C1+n−3C3+n−3C5+n−3C7
……..………….}+ …………. xn−1{1C1} + xn ]
= [x1{n−1C0 + n−1C2 + n−1C4 + n−1C6 ………………} − { n−1C1 + n−1C3
+ n−1C5 + n−1C7 ………………………} ] + [x2{n−2C0 + n−2C2 + n−2C4
+ n−2C6……..} − {n−2C1+n−2C3+n−2C5+n−2C7………………............}]
…..+xn–xn+xn−1–xn−1

since we know the relation

n−2C4 + n−2C6……..} − {n−2C1 + n−2C3 + n−2C5 + n−2C7………...}]

…………… + xn − xn + xn−1 − xn−1
i.e.,
(x1×0)+(x2×0)…………………+0 =0
So q-u =0 ,
Similarly for all other primes(3,5,7….etc) and their powers it
holds true.
Similarly for all numbers because every number is product of primes and their powers.
a1×a2×a3……….an−1×an × The product of LCMs of all sets containing odd no. of elements(except 1)

1=
The product of LCMs of all sets containing even no. of Elements × GCD(all numbers)
i.e., a1×a2×a3……….an−1×an =
The product of LCMs of all sets containing even no. of
Elements × GCD(of all numbers.)

The product of LCMs of all sets containing odd no. of elements (except 1)
Hence Relation 2 is proved

Example

Let us take one example with Five numbers (n=5) i.e, a1=24 , a2=36 , a3=45 , a4=85 , a5=135

Product of a1 , a2 , a3 , a4 , a5 = 446148000

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about Relation between N numbers and their LCMs and GCDs 6

ISSN 2229-5518

Relation 1 = (9841500 * 3 * 18360) / (1215 * 1 ) = 446148000

Relation 2 = (4.02582E+27 * 2.04533E+19 * 1) / 1.00523E+34 *

18360) = 446148000

Conclusion

Both relations are tested for different values from n = 4 to 10 in MS-Excel sheet and found to be correct.

Acknowledgements

The author wishes to thank Mr. H.Srinivas Reddy,M.Sc,B.Ed (Varadhi Institute of Mathematics & Science, Karimnagar,A.P.) for his guidance and support. The author also wishes to thank Rev.Fr.Casmir D’Souza, Head Master of St.Claire High School, Ramagundam, Dist:Karimnagar, A.P.(India) and Dr. S.R.Santhanam (AMTI, Chennai, India) for their co-operation and encouragement.

IJSER © 2012

http://www.ijser.org