Difference between revisions of "2020 AMC 12A Problems/Problem 21"
(→Solution 2) |
Turtles0120 (talk | contribs) m (→Solution 2) |
||
| Line 33: | Line 33: | ||
Similarly, <math>m</math> is a multiple of <math>5</math>, with a form of <math>5\cdot s</math>. We have | Similarly, <math>m</math> is a multiple of <math>5</math>, with a form of <math>5\cdot s</math>. We have | ||
<cmath>s=\text{gcd}{(6\cdot7\cdot8\cdot9\cdot2, 5\cdot s)}=\text{gcd}{(2^5\cdot3^3\cdot7, s)}</cmath> | <cmath>s=\text{gcd}{(6\cdot7\cdot8\cdot9\cdot2, 5\cdot s)}=\text{gcd}{(2^5\cdot3^3\cdot7, s)}</cmath> | ||
| − | The equation holds, if <math>s</math> is a divisor of <math>2^5\cdot3^3\cdot7</math>, which has <math>(5+1)(3+1)(1+1)=\boxed{(D)48}</math> divisors. | + | The equation holds, if <math>s</math> is a divisor of <math>2^5\cdot3^3\cdot7</math>, which has <math>(5+1)(3+1)(1+1)=\boxed{(\text{D})48}</math> divisors. |
by Linty Huang | by Linty Huang | ||
Revision as of 19:17, 18 December 2020
Problem 21
How many positive integers 
are there such that is a multiple of 
, and the least common multiple of 
and equals times the greatest common divisor of 
and 
Solution
We set up the following equation as the problem states:
![\[\text{lcm}{(5!, n)} = 5\text{gcd}{(10!, n)}.\]](http://latex.artofproblemsolving.com/e/4/1/e4182bee46f971119822c1847de1c6dd5e26a37f.png)
Breaking each number into its prime factorization, we see that the equation becomes
![\[\text{lcm}{(2^3\cdot 3 \cdot 5, n)} = 5\text{gcd}{(2^8\cdot 3^4 \cdot 5^2 \cdot 7, n)}.\]](http://latex.artofproblemsolving.com/3/5/6/356f8d9a66c1cdd0ad995e7193a7bed51528f404.png)
We can now determine the prime factorization of . We know that its prime factors belong to the set 
, as no factor of has 
in its prime factorization, nor anything greater. Next, we must find exactly how many different possibilities exist for each.
There can be anywhere between 
and 
's and 
to 
's. However, since is a multiple of , and we multiply the 
by , there can only be 's in 's prime factorization. Finally, there can either 
or 
's.
Thus, we can multiply the total possibilities of 's factorization to determine the number of integers which satisfy the equation, giving us 
. ~ciceronii
Solution 2
Like the Solution 1, we starts from the equation:
Assume 
, with some integer 
. It follows that 
. It means that has a divisor 
. Since is a multiple of , has a divisor . Thus, 
. The equation can be changed as
![\[k\cdot5!=5\text{gcd}{(10!, k\cdot5!)}\]](http://latex.artofproblemsolving.com/d/3/1/d31c9697395029464e6406de5cf7d6476252298e.png)
![\[k=5\text{gcd}{(6\cdot7\cdot8\cdot9\cdot10, k)}\]](http://latex.artofproblemsolving.com/f/c/3/fc3a8c770bc89280e8eb9162077d861b996025b1.png)
We can see that is also a multiple of , with a form of 
. Substituting it in the above equation, we have
![\[m=5\text{gcd}{(6\cdot7\cdot8\cdot9\cdot2, m)}\]](http://latex.artofproblemsolving.com/f/8/9/f89ecf44bcf7f87a44bc62df275846bd1931d16f.png)
Similarly, 
is a multiple of , with a form of 
. We have
![\[s=\text{gcd}{(6\cdot7\cdot8\cdot9\cdot2, 5\cdot s)}=\text{gcd}{(2^5\cdot3^3\cdot7, s)}\]](http://latex.artofproblemsolving.com/7/d/a/7da21de3c788627db510b0d6e41ecd7f19478dc2.png)
The equation holds, if 
is a divisor of 
, which has 
divisors.
by Linty Huang
| 2020 AMC 12A (Problems • Answer Key • Resources) | |
| Preceded by Problem 20 |
Followed by Problem 22 |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
| All AMC 12 Problems and Solutions | |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
