Difference between revisions of "2023 AIME II Problems/Problem 15"
(Created page with "==Solution== Denote <math>a_n = 23 b_n</math>. Thus, for each <math>n</math>, we need to find smallest positive integer <math>k_n</math>, such that \[ 23 b_n = 2^n k_n + 1 ....") |
(→Solution) |
||
Line 3: | Line 3: | ||
Denote <math>a_n = 23 b_n</math>. | Denote <math>a_n = 23 b_n</math>. | ||
Thus, for each <math>n</math>, we need to find smallest positive integer <math>k_n</math>, such that | Thus, for each <math>n</math>, we need to find smallest positive integer <math>k_n</math>, such that | ||
+ | <cmath> | ||
\[ | \[ | ||
23 b_n = 2^n k_n + 1 . | 23 b_n = 2^n k_n + 1 . | ||
\] | \] | ||
− | + | </cmath> | |
Thus, we need to find smallest <math>k_n</math>, such that | Thus, we need to find smallest <math>k_n</math>, such that | ||
+ | <cmath> | ||
\[ | \[ | ||
2^n k_n \equiv - 1 \pmod{23} . | 2^n k_n \equiv - 1 \pmod{23} . | ||
\] | \] | ||
+ | </cmath> | ||
Now, we find the smallest <math>m</math>, such that <math>2^m \equiv 1 \pmod{23}</math>. | Now, we find the smallest <math>m</math>, such that <math>2^m \equiv 1 \pmod{23}</math>. | ||
Line 18: | Line 21: | ||
Therefore, for each <math>n</math>, we need to find smallest <math>k_n</math>, such that | Therefore, for each <math>n</math>, we need to find smallest <math>k_n</math>, such that | ||
+ | <cmath> | ||
\[ | \[ | ||
2^{{\rm Rem} \left( n , 11 \right)} k_n \equiv - 1 \pmod{23} . | 2^{{\rm Rem} \left( n , 11 \right)} k_n \equiv - 1 \pmod{23} . | ||
\] | \] | ||
+ | </cmath> | ||
We have the following results: | We have the following results: |
Revision as of 16:58, 16 February 2023
Solution
Denote .
Thus, for each
, we need to find smallest positive integer
, such that
Thus, we need to find smallest , such that
Now, we find the smallest , such that
.
We must have
. That is,
.
We find
.
Therefore, for each , we need to find smallest
, such that
We have the following results:
\begin{enumerate}
\item If , then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\item If
, then
and
.
\end{enumerate}
Therefore, in each cycle, , we have
,
,
,
, such that
. That is,
.
At the boundary of two consecutive cycles,
.
We have .
Therefore, the number of feasible
is
.
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)