Difference between revisions of "2022 AMC 12A Problems/Problem 23"
(→Solution) |
|||
| Line 13: | Line 13: | ||
We will use the following lemma to solve this problem. | We will use the following lemma to solve this problem. | ||
| − | + | --------------------------- | |
Denote by <math>p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_m^{\alpha_m}</math> the prime factorization of <math>L_n</math>. | Denote by <math>p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_m^{\alpha_m}</math> the prime factorization of <math>L_n</math>. | ||
For any <math>i \in \left\{ 1, 2, \cdots, m \right\}</math>, denote <math>\sum_{j = 1}^{\left\lfloor \frac{n}{p_i^{\alpha_i}} \right\rfloor} \frac{1}{j} = \frac{a_i}{b_i}</math>, where <math>a_i</math> and <math>b_i</math> are relatively prime. | For any <math>i \in \left\{ 1, 2, \cdots, m \right\}</math>, denote <math>\sum_{j = 1}^{\left\lfloor \frac{n}{p_i^{\alpha_i}} \right\rfloor} \frac{1}{j} = \frac{a_i}{b_i}</math>, where <math>a_i</math> and <math>b_i</math> are relatively prime. | ||
Then | Then | ||
<math>k_n = L_n</math> if and only if for any <math>i \in \left\{ 1, 2, \cdots, m \right\}</math>, <math>a_i</math> is not a multiple of <math>p_i</math>. | <math>k_n = L_n</math> if and only if for any <math>i \in \left\{ 1, 2, \cdots, m \right\}</math>, <math>a_i</math> is not a multiple of <math>p_i</math>. | ||
| − | + | --------------------------- | |
Now, we use the result above to solve this problem. | Now, we use the result above to solve this problem. | ||
Revision as of 21:21, 11 November 2022
Problem
Let 
and 
be the unique relatively prime positive integers such that
\[ \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \frac{h_n}{k_n} . \]
Let 
denote the least common multiple of the numbers 
. For how many integers 
with 
is 
?
Solution
We will use the following lemma to solve this problem.
Denote by 
the prime factorization of .
For any 
, denote 
, where 
and 
are relatively prime.
Then
if and only if for any , is not a multiple of 
.
Now, we use the result above to solve this problem.
Following from this lemma, the list of with and is
\[
6, 7, 8, 18, 19, 20, 21, 22 .
\]
Therefore, the answer is \boxed{\textbf{(D) 8}}.
