All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
GCD and LCM (Posted on 2016-09-16) Difficulty: 3 of 5
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.

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution Comment 1 of 1
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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information