2023 AIME II Problems/Problem 15

For each positive integer $n$ let $a_n$ be the least positive integer multiple of $23$ such that $a_n \equiv 1 \pmod{2^n}.$ Find the number of positive integers $n$ less than or equal to $1000$ that satisfy $a_n = a_{n+1}.$

Solution

Denote $a_n = 23 b_n$ . Thus, for each $n$ , we need to find smallest positive integer $k_n$ , such that $23 b_n = 2^n k_n + 1 .$

Thus, we need to find smallest $k_n$ , such that $2^n k_n \equiv - 1 \pmod{23} .$

Now, we find the smallest $m$ , such that $2^m \equiv 1 \pmod{23}$ . We must have $m | \phi \left( 23 \right)$ . That is, $m | 22$ . We find $m = 11$ .

Therefore, for each $n$ , we need to find smallest $k_n$ , such that $2^{{\rm Rem} \left( n , 11 \right)} k_n \equiv - 1 \pmod{23} .$

We have the following results: \begin{enumerate} \item If ${\rm Rem} \left( n , 11 \right) = 0$ , then $k_n = 22$ and $b_n = 1$ . \item If ${\rm Rem} \left( n , 11 \right) = 1$ , then $k_n = 11$ and $b_n = 1$ . \item If ${\rm Rem} \left( n , 11 \right) = 2$ , then $k_n = 17$ and $b_n = 3$ . \item If ${\rm Rem} \left( n , 11 \right) = 3$ , then $k_n = 20$ and $b_n = 7$ . \item If ${\rm Rem} \left( n , 11 \right) = 4$ , then $k_n = 10$ and $b_n = 7$ . \item If ${\rm Rem} \left( n , 11 \right) = 5$ , then $k_n = 5$ and $b_n = 7$ . \item If ${\rm Rem} \left( n , 11 \right) = 6$ , then $k_n = 14$ and $b_n = 39$ . \item If ${\rm Rem} \left( n , 11 \right) = 7$ , then $k_n = 7$ and $b_n = 39$ . \item If ${\rm Rem} \left( n , 11 \right) = 8$ , then $k_n = 15$ and $b_n = 167$ . \item If ${\rm Rem} \left( n , 11 \right) = 9$ , then $k_n = 19$ and $b_n = 423$ . \item If ${\rm Rem} \left( n , 11 \right) = 10$ , then $k_n = 21$ and $b_n = 935$ . \end{enumerate}

Therefore, in each cycle, $n \in \left\{ 11 l , 11l + 1 , \cdots , 11l + 10 \right\}$ , we have $n = 11l$ , $11l + 3$ , $11l + 4$ , $11l + 6$ , such that $b_n = b_{n+1}$ . That is, $a_n = a_{n+1}$ . At the boundary of two consecutive cycles, $b_{11L + 10} \neq b_{11 \left(l + 1 \right)}$ .

We have $1000 = 90 \cdot 11 + 10$ . Therefore, the number of feasible $n$ is $91 \cdot 4 - 1 = \boxed{\textbf{(363) }}$ .

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Solution 2

Observe that if $a_{n-1}$ is divisible by $2^n$ , $a_n = a_{n-1}$ . If not, $a_n = a_{n-1} + 23 \cdot 2^{n-1}$ .

This encourages us to let $b_n = (a_n - 1)/2^n$ . Rewriting the above equations, we have $b_n = \begin{cases} b_{n-1}/2 & \text{if } 2 | (b_{n-1}+23)/2 \\ 1 &\text{if } 2\not\vert b_{n-1} \end{cases}$ Now, we start listing. We know that $b_1 = 11$ , so $b_2 = 17$ , $b_3 = 20$ , $b_4 = 10$ , $b_5 = 5$ , $b_6 = 14$ , $b_7 = 7$ , $b_8 = 15$ , $b_9 = 19$ , $b_{10} = 21$ , $b_{11} = 22$ , $b_{12} = 1$ . Hence the sequence is periodic with period 11. Note that $a_n = a_{n+1}$ if and only if $b_n = b_{n+1}/2$ , i.e. $b_n$ is even. This occurrs when $n$ is congruent to 0, 3, 4 or 6 mod 11.

From 1 to $1001 = 91 \times 11$ , there are $91 \times 4 = 364$ values of $n$ . Since $1001$ satisfies the criteria, we subtract 1 to get $\fbox{363}$ , and we're done!

~Bxiao31415

Solution 3 (Binary Interpretation, Computer Scientists' Playground)

We first check that $\gcd(23, 2^n) = 1$ hence we are always seeking a unique modular inverse of $23$ , $b_n$ , such that $a_n \equiv 23b_n \equiv 1 \mod{2^n}$ .

Now that we know that $b_n$ is unique, we proceed to recast this problem in binary. This is convenient because $x \mod{2^n}$ is simply the last $n$ -bits of $x$ in binary, and if $x \equiv 1 \mod{2^n}$ , it means that of the last $n$ bits of $x$ , only the rightmost bit (henceforth $0$ th bit) is $1$ .

Also, multiplication in binary can be thought of as adding shifted copies of the multiplicand. For example:

$\begin{align} 10111_2 \times 1011_2 &= 10111_2 \times (1000_2 + 10_2 + 1_2) \\ &= 10111000_2 + 101110_2 + 10111_2 \\ &= 11111101_2 \end{align}$

Now note $23 = 10111_2$ , and recall that our objective is to progressively zero out the $n$ leftmost bits of $a_n = 10111_2 \times b_n$ except for the $0$ th bit.

Write $b_n = \underline{c_{n-1}\cdots c_2c_1c_0}_2$ , we note that $c_0$ uniquely defines the $0$ th bit of $a_n$ , and once we determine $c_0$ , $c_1$ uniquely determines the $1$ st bit of $a_n$ , so on and so forth.

For example, $c_0 = 1$ satisfies $a_1 \equiv10111_2 \times 1_2 \equiv 1 \mod{10_2}$ Next, we note that the second bit of $a_1$ is $1$ , so we must also have $c_1 = 1$ in order to zero it out, giving

$a_2 \equiv 10111_2 \times 11_2 \equiv 101110_2 + a_1 \equiv 1000101_2 \equiv 01_2 \mod{100_2}$

$a_{n+1} = a_{n}$ happens precisely when $c_n = 0$ . In fact we can see this in action by working out $a_3$ . Note that $a_2$ has 1 on the $2$ nd bit, so we must choose $c_2 = 1$ . This gives

$a_3 \equiv 10111_2 \times 111_2 \equiv 1011100_2 + a_2 \equiv 10100001_2 \equiv 001_2 \mod{1000_2}$

Note that since the $3$ rd and $4$ th bit are $0$ , $c_3 = c_4 = 0$ , and this gives $a_3 = a_4 = a_5$ .

It may seem that this process will take forever, but note that $23 = 10111_2$ has $4$ bits behind the leading digit, and in the worst case, the leading digits of $a_n$ will have a cycle length of at most $16$ . In fact, we find that the cycle length is $11$ , and in the process found that $a_3 = a_4 = a_5$ , $a_6 = a_7$ , and $a_{11} = a_{12}$ .

Since we have $90$ complete cycles of length $11$ , and the last partial cycle yields $a_{993} = a_{994} = a_{995}$ and $a_{996} = a_{997}$ , we have a total of $90 \times 4 + 3 = \boxed{363}$ values of $n \le 1000$ such that $a_n = a_{n+1}$

~ cocoa @ https://www.corgillogical.com

2023 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 14	Followed by Last Problem
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2023 AIME II Problems/Problem 15

Contents

Solution

Solution 2

Solution 3 (Binary Interpretation, Computer Scientists' Playground)

See also