Interesting Aspects of Factorization

Factorization:
It is the procedure of expressing an integer as a product of 2 or more numbers.If we express it as the product of powers of distinct primes ,it is called prime factorization.Now we shall look at some interesting aspects of this factorization.

Number of factors or divisors of a given number:

Given a number N,one might have a number of ways of expressing it as the product of 2 numbers A,B. i.e N=A*B.
So How many in number are the divisors of a number?

The answer to it lies in simple prime factorization!!

Let the prime factorization of N yields N=2^a1 * 3^a2 * 5^a3 *......Pk^ak
where Pk is the biggest prime factor of N and ak is its power.

Now it shouldn't take one much time to understand that any factor of N can be obtained by depriving one or more of the above primes,a share of their exponents.

ie any factor M of N is =2^b1 * 3^b2 *...................* Pk^bk
where b1 <= a1 , b2 <= a2 ,...........,bk <= ak.

Hence if N=P1^a1 * P2^a2 * .........*Pk^ak then
the no of divisors of N=(a1+1)*(a2+1)*.......*(ak+1).



Sum of divisors of a number

Now getting along with the above explanation , we can also calculate the sum of all the divisors of a number.

N=P1^a1 * P2^a2 * .........*Pk^ak

Now let F(N)=(1+P1 + P1^2 + ...+P1^ak)*(1+P2+P2^2+...+P2^a2)* ......... *(1+Pk+Pk^2+...+Pk^ak).

Expanding this as a polynomial ,we get (a1+1)*(a2+1)...*(ak+1) terms!!
which is nothing but the no of factors we deduced above.And each of the terms is themselves a factor.Hence the sum of divisors of N is given F(N).

F(N)=(1+P1 + P1^2 + ...+P1^ak)*(1+P2+P2^2+...+P2^a2)* ......... (1+Pk+Pk^2+...+Pk^ak)

Now we shall see another interesting aspect of this factorization.

Is the number of divisors of a number N even or odd?

Please ponder over this question for a little while... before seeing the answer.
Because you might regret missing out such a little,yet interesting feature which one could have seen as early as in 6th standard.

Folks!! you don't actually need primes to answer this question.

Any number N can be expressed as N=A*B where A <=sqrt(N) and B >=sqrt(N).
Now start with A=1 and B=N and start increasing A and decreasing B with A*B=N as the constraint.Now one can clearly see that both A and B approach sqrt(N) in this procedure.

In each iteration as we had A < B we can say that the no of factors are even .

But a peculiar thing yet not rare , can happen.
A=B=sqrt(N).Then we have only 1 factor as A=B.
This can arise only if N is a perfect square!!

Hence driving the point home, we conclude that no of divisors is odd if N is a perfect square, even otherwise.
So one needn't enumerate all the prime factors of a number!!



Some interesting questions

1.All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example 9 can be expressed in three such ways, 2+3+4, 4+5 or 9. Given an integer ,you will have to determine in how many ways that number can be expressed as summation of consecutive numbers.

Click here for solution


2.Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large.So given 5<=N<=100 5<=M<=100 and M<=N.Compute the EXACT value of: N!/(M!*(N-M)!)
The final value of C will fit in a 32-bit Pascal LongInt or a C long.
So deduce an approach based on this assumption given.

Click here for Solution