Determine the total number of pairs (M,N) of positive integers with M ≤N, such that:
gcd(M,N) = 5!, and
lcm(M,N) = 51!
Prove that no further pair satisfies the given set of simultaneous equations.
5! = 2^3 * 3 * 5, as shown in a breakdown of counts of the prime factors by the definitionally constituent factors of 5 factorial:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
2 1
3 1
4 2
5 1
3 1 1
The same sort of breakdown of counts of prime factors of 51! follows:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
2 1
3 1
4 2
5 1
6 1 1
7 1
8 3
9 2
10 1 1
11 1
12 2 1
13 1
14 1 1
15 1 1
16 4
17 1
18 1 2
19 1
20 2 1
21 1 1
22 1 1
23 1
24 3 1
25 2
26 1 1
27 3
28 2 1
29 1
30 1 1 1
31 1
32 5
33 1 1
34 1 1
35 1 1
36 2 2
37 1
38 1 1
39 1 1
40 3 1
41 1
42 1 1 1
43 1
44 2 1
45 2 1
46 1 1
47 1
48 4 1
49 2
50 1 2
51 1 1
47 23 12 8 4 3 3 2 2 1 1 1 1 1 1
so 51! =
47 23 12 8 4 3 3 2 2 1 1 1 1 1 1
2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47
By the first breakdown, 5! = 2^3 * 3 * 5, we know that each of M and N has at least the 3rd power of 2, and at least one factor 3 and one factor 5. We also know that at least one of M and N has no more than the third power of 2; at least one has no more than the first power of 3 as a factor and one has no more than the first power of 5.
So, by combining this information with the prime factorization of 51!, as far as the prime factors 2, 3 and 5 go, one has 2^3 and the other has 2^44; one has 3^1 and the other has 3^22; one has 5^1 and the other has 5^11. You can mix and match these, so just in this regard we have 2^3 possibilities.
For the other twelve primes, from 7 to 47, the full power as found in 51! must be in one or the other so as for that prime not to appear in the gcd. So for each of the 2^3 possibilities mentioned in the preceding paragraph, there are 2^12 possibilities of assigning these prime powers to one or the other of M and N.
The result, 2^15 = 32,768, is determined just the number of distinct primes in the factorization of 51!, so it looks like we went to a lot of work for nothing, except to show why this is the case--that is, why it's just 2 raised to the power of the number of distinct prime factors in 51!.
Edited on September 16, 2016, 11:10 am
|
|
Posted by Charlie
on 2016-09-16 10:18:50 |
solution
