**DECOMPOSITION OF THE DIVISORS OF A
NATURAL NUMBER**

**INTO PAIRWISE CO-PRIME SETS**

(Amarnath Murthy, S.E. (E&T),Well Logging Services, Oil and Natural Gas corporation Ltd.,Sabarmati, Ahmedabad, 380 005 , INDIA.)

Given n a natural number . Let d_{1}, d_{2 }, d_{3},
d_{4}, d_{5}, . . . be the divisors of N. A querry coms to my
mind, as to, in how many ways , we could choose a divisor pair which are
co-prime to each other? Similarly in how many ways one could choose a triplet,
or a set of four divisors etc. such that, in each chosen set, the divisors are
pairwise co-prime.?

We start with an example Let N= 48 = 2^{4 }x 3 . The ten divisors
are

1 , 2 , 3, 4, 6, 8, 12, 16, 24, 48

We denote set of co-prime pairs by D_{2 }(48) , co-prime triplets by
D_{3 }(48) etc.

We get D_{2 }(48) = { (1,2) , (1, 3) , (1 , 4 ), (1 , 6 ), (1,8 ),
(1, 12 ), ( 1,16) , (1 , 24 ), (1 , 48 ),

(2, 3), ( 4,3), (8, 3) , (16, 3) }

**Order of D _{2 }(48) = 13.**

D_{3 }(48) = { (1,2, 3 ) , (1, 3, 4 ) , (1 , 3 , 8 ), (1 ,3, 16 ) }
,** Order of D _{3 }(48) = 4.**

D_{4} (48) = { } = D_{5} (48) = . . . .= D_{9} (48)
= D_{10} (48) .

Another example N = 30 = 2x3x5 ( a square free number). The 8 divisors are

1 , 2 , 3 , 5 , 6 , 10, 15, 30

D_{2 }(30) = { ( 1,2) , ( 1, 3), ( 1, 5), ( 1, 6), (1, 10) , ( 1, 15
) , ( 1, 30 ) ,( 2, 3) , ( 2, 5) , (2, 15) ,

( 3, 5) , ( 3, 10 ) , ( 5, 6) }.

**Order of D _{2 }(30) = 13. = O[D_{2}( p_{1}p_{2}p_{3})]
----------- (A)**

D_{3 }(30) = { (1,2, 3 ) ,(1 , 2 , 5) , (1, 3 , 5 ) , ( 2 , 3, 5) ,
( 1, 3, 10 ) , (1 , 5, 6) , ( 1,2, 15) }

**Order of D _{3 }(30) = 7.**

D_{4} (30) = { (1,2, 3, 5 )}, **Order of D _{4 }(30) = 1.**

**OPEN PROBLEM: To determine the order of D _{r} (N) .**

In this note we consider the simple case of n being a **square-free number**
for r = 2 , 3 etc.

**(A) r = 2**

We rather derive a reduction formula for r = 2. And finally a direct formula.

Let N = p_{1}p_{2}p_{3}. . .p_{n} where p_{k}
is a prime for k = 1 to n

We denote D_{2} (N) = D_{2} ( 1#n) for convnience. We shall
derive a reductio formula for

D_{2}( 1 # (n+1)).

Let q be a prime such that (q, N) = 1 , ( HCF =1)

Then D_{2}(Nq) = D_{2}( 1#(n+1))

- We have by definition D
_{2}( 1#n) Ì D_{2}( 1#(n+1))

This provides us with O [D_{2}( 1#n) ]
elements of D_{2}( 1#(n+1)).

(2) Consider an arbitrarily chosen element ( d_{k
}, d_{s}^{ }) of D_{2}( 1#n). This element when
combined with q yields exactly two elements of D_{2}( 1#(n+1)). i.e. (
qd_{k }, d_{s}^{ }) and ( d_{k }, qd_{s}^{
}).

Hence the set D_{2}( 1#n). contributes two
times the order of itself.

- The element ( 1, q) has ot
been considered in the above mentioned cases hence the the total number of
elements of D
_{2}( 1#(n+1)) are 3 times the order of D_{2}( 1#n) + 1.

**O[D _{2}( 1#(n+1))] = 3 x O[ D_{2}( 1#n)] + 1. ---------(
B)**

**Applying Reduction Formula (B) for evaluating O[D _{2}( 1#4)]**

From (A) we have O[D_{2}( p_{1}p_{2}p_{3})]
= O[D_{2}( 1#3)] = 13 hence

**O[D _{2}( 1#4)] = 3x13+ 1 = 40** .

This can be verified by considering N = 2x3x5x7 = 210. The divisors are

1 , 2 , 3 , 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210,

D_{2}(210) = { (1,2) , ( 1, 3) , ( 1, 5) , ( 1, 6) , (1, 7 ) , (1,
10), ( 1, 14) ,(1 ,15 ), ( 1,21),(1, 30),

( 1, 35), ( 1, 42 ) , ( 1, 70) , ( 1, 105) , ( 1 , 210) , ( 2, 3) , ( 2, 5) , ( 2, 7) , ( 2, 15) , ( 2, 21) ,

(2, 35), (2, 105 ) , ( 3 , 5) , ( 3, 7 ) ,( 3, 10), (3, 14 ) , ( 3, 35 ) , ( 3 , 70 ), ( 5 , 6), ( 5, 7) ,

( 5, 14) , ( 5 , 21) , ( 5, 42) , ( 7, 6) , ( 7, 10 ) , ( 7, 15) ,( 7, 30 ) , ( 6, 35 ) , ( 10, 21) , ( 14, 15) }

O [D_{2}(210)] = 40.

The reduction formula (B) can be reduced to a direct formula by applying simple induction and we get

**O[ D _{2}( 1#n)] = (3^{n} - 1) /2 -----------(C)**

**(B) r = 3.**

For r = 3 we derive a reduction formula.

(1) We have D_{3}(1#n) Ì D_{3}
( 1#(n+1)) hence this contributes O[D_{3}(1#n)] elements to D_{3}
( 1#(n+1)).

(2) Let us Choose an arbitrary element of D_{3}(1#n) say (a , b , c
). The additional prime q yields (qa , b , c ) ,

(a , qb , c ), (a , b , qc ) i.e. three elements. In this way we get 3 x O[D_{3}(1#n)]
elements.

- Let the product of the n
primes = N . Let ( d
_{1 , }d_{2}, d_{3}, . . . d_{d(N)}) be all the divisors of N . Consider D_{2}(1#n) which contains d(N) - 1 elements in which one member is unity = d_{1}. i.e. , ( 1, d_{2}) , ( 1, d_{3}) , . . ., ( 1, d_{d(N)}) .

If q is placed as the third element with these as the third element we get
d(N) - 1 elements of D_{3} ( 1#(n+1)). The remaining eleents of D_{2}
(1#n) yield elements repetitive elements already covered under (2).

Considering the exhaustive contributions from all the three above we get

O[D_{3} ( 1#(n+1))] = 4 * O[D_{3}(1#n)] + d(N) - 1

**O[D _{3} ( 1#(n+1))] = 4 * O[D_{3}(1#n)] + 2^{n} -
1 -------------(D)**

O[D_{3}(210) ] = 4 * O [ D_{3} (30) ] 8 -1

**O[D _{3}(210) ] = 4 * 7 + 8 -1 = 35**

To verify the elements are listed below.

**D _{3}(210) =** { (1,2, 3 ) , ( 1, 2 , 5) , ( 1, 3, 5) , , (1,
2, 7 ) , (1, 3, 7 ), (1 ,5 , 7 ), ( 1, 2 , 15 ),(1, 2, 21 ),

( 1, 2, 35), ( 1,2 , 105 ) , ( 1, 3, 10) , ( 1, 3, 14) , ( 1 , 3, 35) , ( 1, 3, 70 ) , ( 1, 5, 6 ) , (1, 5,14 ) , ( 1, 5 , 21) ,

(1, 5, 42 ), (1,7, 6 ) , ( 1 ,7, 10 ) , ( 1, 7, 15 ) ,( 1, 7, 30), (2 ,3, 5 ) , ( 2, 3, 7 ) , ( 2 , 5, 7 ), ( 2 , 3 , 35), (2, 5, 21) ,

( 2, 7 ,15 ) , (3, 5 , 7) , ( 3, 5, 14) , (3 , 7, 10 ) , ( 5, 7, 6 ) , (1, 6, 35 ) , (1, 10, 21) , (1, 14, 15) }

**Open Problem : To obtain a direct formula from the reduction formula (D).**

Regarding the general case i.e. O [D_{r} ( 1#n) ] we derive an
inequality.

Let ( d_{1 , }d_{2}, d_{3} , . . . d_{r} )
be an element of O [D_{r} ( 1#n) ].

Introducing a new prime q other than the prime factors of N we see that this
element in conjunction with q gives r elements of D_{r} ( 1#(n+1)) i.e.
( **qd _{1}**

( d_{1 , }d_{2}, d_{3} , . . . **qd _{r} **)
.also D

**O[D _{r} ( 1#(n+1))] > (r+1). O[D_{r} ( 1#n)]**

**To find an accurate formula is a tough task ahead for the readers.**

** Considering the general case is a further challenging job.**

** **