2023 AIME II Problems/Problem 15
Contents
Problem
For each positive integer let be the least positive integer multiple of such that Find the number of positive integers less than or equal to that satisfy
Solution 1
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 . By Fermat's Theorem, we must have . That is, . We find .
Therefore, for each , we need to find smallest , such that
We have the following results:
If \({\rm Rem} \left( n , 11 \right) = 0\), then \(k_n = 22\) and \(b_n = 1\).
If \({\rm Rem} \left( n , 11 \right) = 1\), then \(k_n = 11\) and \(b_n = 1\).
If \({\rm Rem} \left( n , 11 \right) = 2\), then \(k_n = 17\) and \(b_n = 3\).
If \({\rm Rem} \left( n , 11 \right) = 3\), then \(k_n = 20\) and \(b_n = 7\).
If \({\rm Rem} \left( n , 11 \right) = 4\), then \(k_n = 10\) and \(b_n = 7\).
If \({\rm Rem} \left( n , 11 \right) = 5\), then \(k_n = 5\) and \(b_n = 7\).
If \({\rm Rem} \left( n , 11 \right) = 6\), then \(k_n = 14\) and \(b_n = 39\).
If \({\rm Rem} \left( n , 11 \right) = 7\), then \(k_n = 7\) and \(b_n = 39\).
If \({\rm Rem} \left( n , 11 \right) = 8\), then \(k_n = 15\) and \(b_n = 167\).
If \({\rm Rem} \left( n , 11 \right) = 9\), then \(k_n = 19\) and \(b_n = 423\).
If \({\rm Rem} \left( n , 11 \right) = 10\), then \(k_n = 21\) and \(b_n = 935\).
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)
Solution 2
Observe that if is divisible by , . If not, .
This encourages us to let . Rewriting the above equations, we have The first few values of are and . We notice that , and thus the sequence is periodic with period .
Note that if and only if is even. This occurs when is congruent to or mod , giving four solutions for each period.
From to (which is ), there are values of . We subtract from the total since satisfies the criteria but is greater than to get a final answer of . ~Bxiao31415
(small changes by bobjoebilly and IraeVid13)
Solution 3 (Binary Interpretation, Computer Scientists' Playground)
We first check that hence we are always seeking a unique modular inverse of , , such that .
Now that we know that is unique, we proceed to recast this problem in binary. This is convenient because is simply the last -bits of in binary, and if , it means that of the last bits of , only the rightmost bit (henceforth th bit) is .
Also, multiplication in binary can be thought of as adding shifted copies of the multiplicand. For example:
Now note , and recall that our objective is to progressively zero out the leftmost bits of except for the th bit.
Write , we note that uniquely defines the th bit of , and once we determine , uniquely determines the st bit of , so on and so forth.
For example, satisfies Next, we note that the second bit of is , so we must also have in order to zero it out, giving
happens precisely when . In fact we can see this in action by working out . Note that has 1 on the nd bit, so we must choose . This gives
Note that since the rd and th bit are , , and this gives .
It may seem that this process will take forever, but note that has bits behind the leading digit, and in the worst case, the leading digits of will have a cycle length of at most . In fact, we find that the cycle length is , and in the process found that , , and .
Since we have complete cycles of length , and the last partial cycle yields and , we have a total of values of such that
~ cocoa @ https://www.corgillogical.com
Video Solution
~MathProblemSolvingSkills.com
See also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.