[puzzle] another little problem

[pier4r]

lcd: least common multiple.

[Thomas Okken]

(10-06-2017 09:03 PM)pier4r Wrote:  

lcd: least common multiple.

The prime factorization of 50! contains all the primes up to 50, of which there are 15; the prime factorization of 5! contains the primes up to 5, of which there are 3.

Since GCD(x, y) * LCM(x, y) = x * y, we're looking for pairs of divisors a, b of 5! * 50! such that a * b = 50! * 5! and GCD(a, b) = 5!.

One factor must contain 2^3 * 3 * 5 and the other all the other powers of 2, 3, and 5, because that's the only way for GCD(a, b) to be 5!. All the other 12 prime factors can go with either a or b, but all the occurrences of any prime factor must either all go with a or all with b, since otherwise they'd contribute to the GCD. So, 12 primes to be placed with 2 different factors, that's 2^12 = 4096 possibilities.

EDIT:

No, that's wrong, the 2^3, 3^1, and 5^1 do not have to all be with the same factor; what's important is that one factor has 2^3 and the other has 2^47; one factor has 3^1 while the other has 3^22, and one factor has 5^1 while the other has 5^12. So, four times as many possibilities as I first figured, for a total of 16384.

[AlexFekken]

Looks correct me to me.

And in general, if n1 is the number of distinct prime factors that the gcd and lcm have in common with the same exponent, n2 the number that they have in common with a different exponent, and n3 the number in the lcm but not the gcd, then the answer would be:

2^(n2+n3-1) if (n2+n3) > 0
1 if n2=n3=0, i.e. gcd = lcm = x = y

That the gcd and lcm are factorials is irrelevant, but makes it easy to count the prime factors.