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 d1, d2 , d3, d4, d5, . . . 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 = 24 x 3 . The ten divisors are

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

We denote set of co-prime pairs by D2 (48) , co-prime triplets by D3 (48) etc.

We get D2 (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 D2 (48) = 13.

D3 (48) = { (1,2, 3 ) , (1, 3, 4 ) , (1 , 3 , 8 ), (1 ,3, 16 ) } , Order of D3 (48) = 4.

D4 (48) = { } = D5 (48) = . . . .= D9 (48) = D10 (48) .

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

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

D2 (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 D2 (30) = 13. = O[D2( p1p2p3)] ----------- (A)

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

Order of D3 (30) = 7.

D4 (30) = { (1,2, 3, 5 )}, Order of D4 (30) = 1.

 

OPEN PROBLEM: To determine the order of Dr (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 = p1p2p3. . .pn where pk is a prime for k = 1 to n

We denote D2 (N) = D2 ( 1#n) for convnience. We shall derive a reductio formula for

D2( 1 # (n+1)).

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

Then D2(Nq) = D2( 1#(n+1))

  1. We have by definition D2( 1#n) Ì D2( 1#(n+1))

This provides us with O [D2( 1#n) ] elements of D2( 1#(n+1)).

(2) Consider an arbitrarily chosen element ( dk , ds ) of D2( 1#n). This element when combined with q yields exactly two elements of D2( 1#(n+1)). i.e. ( qdk , ds ) and ( dk , qds ).

Hence the set D2( 1#n). contributes two times the order of itself.

  1. The element ( 1, q) has ot been considered in the above mentioned cases hence the the total number of elements of D2( 1#(n+1)) are 3 times the order of D2( 1#n) + 1.

O[D2( 1#(n+1))] = 3 x O[ D2( 1#n)] + 1. ---------( B)

Applying Reduction Formula (B) for evaluating O[D2( 1#4)]

From (A) we have O[D2( p1p2p3)] = O[D2( 1#3)] = 13 hence

O[D2( 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,

D2(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 [D2(210)] = 40.

 

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

O[ D2( 1#n)] = (3n - 1) /2 -----------(C)

 

(B) r = 3.

For r = 3 we derive a reduction formula.

(1) We have D3(1#n) Ì D3 ( 1#(n+1)) hence this contributes O[D3(1#n)] elements to D3 ( 1#(n+1)).

(2) Let us Choose an arbitrary element of D3(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[D3(1#n)] elements.

  1. Let the product of the n primes = N . Let ( d1 , d2, d3 , . . . dd(N) ) be all the divisors of N . Consider D2 (1#n) which contains d(N) - 1 elements in which one member is unity = d1. i.e. , ( 1, d2 ) , ( 1, d3 ) , . . ., ( 1, dd(N) ) .

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

Considering the exhaustive contributions from all the three above we get

O[D3 ( 1#(n+1))] = 4 * O[D3(1#n)] + d(N) - 1

O[D3 ( 1#(n+1))] = 4 * O[D3(1#n)] + 2n - 1 -------------(D)

O[D3(210) ] = 4 * O [ D3 (30) ] 8 -1

O[D3(210) ] = 4 * 7 + 8 -1 = 35

To verify the elements are listed below.

D3(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 [Dr ( 1#n) ] we derive an inequality.

Let ( d1 , d2, d3 , . . . dr ) be an element of O [Dr ( 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 Dr ( 1#(n+1)) i.e. ( qd1 , d2, d3 , . . . dr ), ( d1 , qd2, d3 , . . . dr ), . . .

( d1 , d2, d3 , . . . qdr ) .also Dr ( 1#n) Ì Dr ( 1#(n+1)). Hence we get

O[Dr ( 1#(n+1))] > (r+1). O[Dr ( 1#n)]

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

 Considering the general case is a further challenging job.