[puzzle] another little problem

[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.