The Student Room Group

Question on factoring a prime

'Suppose that the prime factorisation of N is p1a1p2a2...pnanp_1^{a_1}p_2^{a_2}...p_n^{a_n}, where p1<p2<...<pnp_1 < p_2 < ... < p_n and ai>1a_i >1. Prove that the number of factors of N is (a1+1)(a2+1)...(an+1)(a_1 +1)(a_2 +1)...(a_n +1).'

Can someone please help to explain the solution to this question?
(edited 2 years ago)
Reply 1
Just think of an n-dimensional box with each prime on one dimension.

If necessary, create a simple example with 2 primes, say 2 and 3 and a couple of low exponents. How do you represent each factor on a grid?
(edited 2 years ago)
Can't you just solve it with standard combinatorics? Since the question is just asking how many different combinations of the exponents of the factors there are.
Each factor (p) of N appears a times. What I mean is that p^1, p^2, p^3,..., p^a are all factors of N, as said in the question. We also include p^0 as 1 is obviously a factor of N. This means that in total there are a+1 choices for your power of p, each of which provide a different factor of N. Now we extend this to different factors of N (p_1, p_2, p_3, p_4,..., p_n). Each of which having their own unique a and therefore we can state that the factor p_n will have a_n+1 different powers to choose from. If we wish to find all possible combinations for the factors of N, we just multiply all these different combinations together and hence we end up with our final result, (a_1 +1)(a_2 +1)...(a_n +1).
Sorry if I wasn't very clear, feel free to ask for an explanation for any parts that were poorly put.
(edited 2 years ago)

Quick Reply

Latest