Difference between revisions of "2020 AMC 12A Problems/Problem 21"
m (→Solution) |
(→Solution 2) |
||
(15 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
How many positive integers <math>n</math> are there such that <math>n</math> is a multiple of <math>5</math>, and the least common multiple of <math>5!</math> and <math>n</math> equals <math>5</math> times the greatest common divisor of <math>10!</math> and <math>n?</math> | How many positive integers <math>n</math> are there such that <math>n</math> is a multiple of <math>5</math>, and the least common multiple of <math>5!</math> and <math>n</math> equals <math>5</math> times the greatest common divisor of <math>10!</math> and <math>n?</math> | ||
Line 5: | Line 5: | ||
<math>\textbf{(A) } 12 \qquad \textbf{(B) } 24 \qquad \textbf{(C) } 36 \qquad \textbf{(D) } 48 \qquad \textbf{(E) } 72</math> | <math>\textbf{(A) } 12 \qquad \textbf{(B) } 24 \qquad \textbf{(C) } 36 \qquad \textbf{(D) } 48 \qquad \textbf{(E) } 72</math> | ||
− | == Solution == | + | == Solution 1== |
We set up the following equation as the problem states: | We set up the following equation as the problem states: | ||
Line 19: | Line 19: | ||
There can be anywhere between <math>3</math> and <math>8</math> <math>2</math>'s and <math>1</math> to <math>4</math> <math>3</math>'s. However, since <math>n</math> is a multiple of <math>5</math>, and we multiply the <math>\text{gcd}</math> by <math>5</math>, there can only be <math>3</math> <math>5</math>'s in <math>n</math>'s prime factorization. Finally, there can either <math>0</math> or <math>1</math> <math>7</math>'s. | There can be anywhere between <math>3</math> and <math>8</math> <math>2</math>'s and <math>1</math> to <math>4</math> <math>3</math>'s. However, since <math>n</math> is a multiple of <math>5</math>, and we multiply the <math>\text{gcd}</math> by <math>5</math>, there can only be <math>3</math> <math>5</math>'s in <math>n</math>'s prime factorization. Finally, there can either <math>0</math> or <math>1</math> <math>7</math>'s. | ||
− | Thus, we can multiply the total possibilities of <math>n</math>'s factorization to determine the number of integers <math>n</math> which satisfy the equation, giving us <math>6 \times 4 \times 1 \times 2 = \boxed{\textbf{(D) } 48}</math>. ~ciceronii | + | Thus, we can multiply the total possibilities of <math>n</math>'s factorization to determine the number of integers <math>n</math> which satisfy the equation, giving us <math>6 \times 4 \times 1 \times 2 = \boxed{\textbf{(D) } 48}</math>. ~ciceronii |
+ | == Solution 2== | ||
+ | Like the Solution 1, we start from the equation: | ||
+ | |||
+ | <cmath>\text{lcm}{(5!, n)} = 5\text{gcd}{(10!, n)}.</cmath> | ||
+ | Assume <math>\text{lcm}{(5!, n)}=k\cdot5!</math>, with some integer <math>k</math>. It follows that <math>k\cdot 4!=\text{gcd}{(10!, n)}</math>. It means that <math>n</math> has a divisor <math>4!</math>. Since <math>n</math> is a multiple of <math>5</math>, <math>n</math> has a divisor <math>5!</math>. Thus, <math>\text{lcm}{(5!, n)}=n=k\cdot5!</math>. The equation can be changed as | ||
+ | <cmath>k\cdot5!=5\text{gcd}{(10!, k\cdot5!)}</cmath> | ||
+ | <cmath>k=5\text{gcd}{(6\cdot7\cdot8\cdot9\cdot10, k)}</cmath> | ||
+ | We can see that <math>k</math> is also a multiple of <math>5</math>, with a form of <math>5\cdot m</math>. Substituting it in the above equation, we have | ||
+ | <cmath>m=5\text{gcd}{(6\cdot7\cdot8\cdot9\cdot2, m)}</cmath> | ||
+ | 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> | ||
+ | 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{(\textbf{D})48}</math> divisors. ~Linty Huang.shen k.kai | ||
+ | |||
+ | == Solution 3 == | ||
+ | |||
+ | As in the previous solutions, we start with | ||
+ | |||
+ | <cmath>\text{lcm}(5!,n) = 5\text{gcd}(10!,n)</cmath> | ||
+ | |||
+ | From this we have that <math>\text{lcm}(5!,n) \,|\, 5\text{gcd}(10!,n)</math> , and in particular, <math>n \,|\, 5\text{gcd}(10!,n)</math>. However, <math>\text{gcd}(10!,n)\, |\, n</math>, so we must have <math>\text{gcd}(10!,n) = n</math> or <math>\text{gcd}(10!,n) = n/5</math>. If <math>\text{gcd}(10!,n) = n</math>, then we have <math>\text{lcm}(5!,n) = 5n</math>; because <math>5\, |\, 5!</math>, this implies that 5 does not divide <math>n</math>, so we must have <math>\text{gcd}(10!,n) = n/5</math>. | ||
+ | |||
+ | Now we have <math>\text{lcm}(5!,n) = n</math>, implying that <math>5!\, |\, n</math>, and <math>n/5\, |\, 10!</math>. Writing out prime factorizations, this gives us | ||
+ | |||
+ | <cmath>2^3 \cdot 3 \cdot 5 \,|\, n</cmath> | ||
+ | <cmath>n \,|\, 2^8 \cdot 3^4 \cdot 5^2 \cdot 7</cmath> | ||
+ | |||
+ | So <math>n</math> can have 3, 4, 5, 6, 7, or 8 factors of 2; 1, 2, 3, or 4 factors of two; and 0 or 1 factors of 7. Note that <math>\text{gcd}(2^8 \cdot 3^4 \cdot 5^2 \cdot 7,n) = n/5</math> implies that <math>n</math> has 2 factors of 5. Thus, there are <math>6 \cdot 4 \cdot 2 = 48</math> possible choices for <math>n</math>, and our answer is <math>\boxed{\textbf{(D) 48}}</math>. | ||
+ | |||
+ | -gumbymoo | ||
+ | |||
+ | ==Video Solution by Richard Rusczyk== | ||
+ | https://www.youtube.com/watch?v=8S85536jpYw&list=PLyhPcpM8aMvJvwA2kypmfdtlxH90ShZCc&index=1&t=25s | ||
+ | - AMBRIGGS | ||
+ | |||
+ | == Video Solution by OmegaLearn == | ||
+ | https://youtu.be/CWZkTCNu42o?t=846 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
+ | |||
+ | ==See Also== | ||
{{AMC12 box|year=2020|ab=A|num-b=20|num-a=22}} | {{AMC12 box|year=2020|ab=A|num-b=20|num-a=22}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 01:31, 21 August 2024
Contents
Problem
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 1
We set up the following equation as the problem states:
Breaking each number into its prime factorization, we see that the equation becomes
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 start 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
We can see that
is also a multiple of
, with a form of
. Substituting it in the above equation, we have
Similarly,
is a multiple of
, with a form of
. We have
The equation holds, if
is a divisor of
, which has
divisors. ~Linty Huang.shen k.kai
Solution 3
As in the previous solutions, we start with
From this we have that , and in particular,
. However,
, so we must have
or
. If
, then we have
; because
, this implies that 5 does not divide
, so we must have
.
Now we have , implying that
, and
. Writing out prime factorizations, this gives us
So can have 3, 4, 5, 6, 7, or 8 factors of 2; 1, 2, 3, or 4 factors of two; and 0 or 1 factors of 7. Note that
implies that
has 2 factors of 5. Thus, there are
possible choices for
, and our answer is
.
-gumbymoo
Video Solution by Richard Rusczyk
https://www.youtube.com/watch?v=8S85536jpYw&list=PLyhPcpM8aMvJvwA2kypmfdtlxH90ShZCc&index=1&t=25s - AMBRIGGS
Video Solution by OmegaLearn
https://youtu.be/CWZkTCNu42o?t=846
~ pi_is_3.14
See Also
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.