An interesting equation (Posted on 2007-08-05)

	Submitted by Praneeth
Rating: 3.6667 (3 votes)
Solution:	(Hide)
Consider the equation x*y=A. No. of solutions of (x,y)=d(A).---(1) If LCM(x,y)=L, GCD(x,y)=G, then x*y=A => L*G=A We know that L is a multiple of G, So G² is a factor of A. For every G, L=A/G.----(2) Now we have to find No. of solutions of L(x,y)=L and G(x,y)=G for each (L,G) pair. No. of solutions will be 2^n(L/G) = 2^n(A/G²) (from(2)) Total no. of solutions = Σ2^(A/i²); where (A/i²) is an integer and i>0. From (1), Σ2^(x/i²) = d(A). No. of solutions for x,y whose LCM is L and GCD is G =2^n(L/G) Proof: Consider prime factorization of both L and G. Let exponent of a prime factor of L in L,G,x,y be i,j,k,l respectively. we know that i>=j, i=max(k,l) and j=min(k,l) If i>j, k can take either i or j. So, 2 possibilities. If i=j, only one possibility for k as well as l. In the same way find and multiply for every prime factor of L. So, No. of solutions for (x,y) is simply equal to 2^n(L/G). Other Solution is given in the comments by Eigenray.

	Subject	Author	Date
	Solution	Eigenray	2007-08-06 09:09:20
	Hint	Praneeth	2007-08-06 01:23:53