Number of divisors for a very large number?

general
, , , ,
1

We all know a number can be expressed as product of primes.

N=(p^x)(q^y)…(r^z) where p,q,…r are prime numbers and x,y…z are positive numbers.

Number of divisors for a number is = (x+1)(y+1)…*(z+1). I understood this is giving correct answer. I need the proof or basic concept underlying this. Explain it clearly…

2

Just think like this,

Let N=(p^x)(q^y)…(r^z)

Now look at first term. Its p^x. Now, any power of p <=x will divide N. So we can choose any power of p from 0 to x , i.e. a total of x+1 choices for power of p which can divide N. Similarly we have y+1 choices for powers of q and so on.

Now-

1.Any combination of them will divide N. (i.e. p^a x q^b ... will divide N provided a<=x,b<=y...)
2.All terms here are independent (the power of p in divisor we take doesnt depend on power of q)

So it is a simple multiplication of choices available available, which is (x+1)(y+1)(z+1)…

2 Likes
3

PS: I have assumed that you are quite well familiar with combinatorics. If thats not the case, please comment/ask doubts. :slight_smile:

4

“Any combination of them will divide N” => can you quote me an example for this. (Remaining I understood)

5

Yeah I understood! Thanks a lot!

1 Like
6

Taking simplest example.

225 = 3^2 x 5^2. (hope i got it right :p)

So, the possible combination of powers are -

(3^0 x 5^0 , 3^1 x 5^0, 3^2 x 5^0,…total 9 combinations). You can see that ALL of these divide N.

Lets take 3^2 x 5^1=45-

225/45 = (3^2 x 5^2)/(3^2 x 5^1) = 5. As you can see, this condition holds-

p^a x q^b ... will divide N provided a<=x,b<=y.
7

Say N = p^a then number of divisors are 1,p^1,p^2,p^3,p^4…p^a so they are a+1 in numbers.

d(p^a) = a+1

Example - 2^8 = 1, 2^1 , 2^2 , 2^3 ,… 2^8.

d(2^8) = (8+1)

now, take a bit more complex one. Let’s say you have N = (p^a)*(q^b).

1 p p2 … pa

q pq p2q … paq

q2 pq2 p2q2 … paq2

… … … … …

qb pqb p2qb … paqb

so in total they form a matrix of (a+1) rows and (b+1) columns. Hence N has (a+1)*(b+1) number of divisors. We can expand this logic to any number.

Instead there can be a more formal proof also, since N = p^a * q^b * rc … then any combination of p raised to power lesser than a will be a divisors of N, similarly for other prime factors too. So applying the basic multiplication rule of product in combinatorics we can get the number of divisors of N will be (a+1)(b+1)*(c+1)…

Note - Number of Proper divisors will be (a+1)(b+1)(c+1)… -1 as proper divisors doesn’t include the number itself.

Hope this helps !