2026 AMC 12B Problem 23

Attempt Problem 23 of the 2026 AMC 12B below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2026 AMC 12B solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

23.

For positive integers aa and b,b, let R(a,b)R(a,b) denote the remainder when aa is divided by b.b. Suppose NN is the least positive integer such that
R(N,2)≥1R(N,4)≥2R(N,8)≥4⋮R(N,2200)≥2199\begin{array}{rcl}R(N,2)&{}\ge{}&1\\R(N,4)&{}\ge{}&2\\R(N,8)&{}\ge{}&4\\&\vdots&\\R(N,2^{200})&{}\ge{}&2^{199}\end{array}
What are the last three digits of N?N?
125125
249249
375375
511511
875875
Answer: C
Concepts:number basemodular exponentiationEuler’s Totient Function
Small hint:
The condition modulo 2k2^k forces the kkth binary digit from the right to be 11
Big hint:
The smallest eligible integer is 2200−12^{200}-1
Solution:
The first condition makes NN odd, so its remainder modulo 22 is 1.1. With divisor 4,4, the remainder must then be 3;3; with divisor 8,8, it must be 7.7. Each time we double the divisor, the new remainder is either the old remainder or the old remainder plus the old divisor. The lower bound forces the latter. Thus the remainder modulo 22002^{200} is 2200−1,2^{200}-1, making the smallest possible value N=2200−1.N=2^{200}-1. To find its last three digits, work modulo 125125 and 8.8.
Let φ(m)\varphi(m) count the integers from 11 through mm that are relatively prime to m.m. Euler’s totient theorem states that, whenever aa and mm are relatively prime, aφ(m)≡1(modm).a^{\varphi(m)}\equiv1\pmod m.
Since 125=53,125=5^3, the numbers not relatively prime to it are exactly the multiples of 5.5. There are 1255=25\frac{125}5=25 of these from 11 through 125.125. Therefore φ(125)=125(1−15)=100.\varphi(125)=125\left(1-\frac15\right)=100.
The numbers 22 and 125125 are relatively prime, so the theorem gives 2100≡1(mod125).2^{100}\equiv1\pmod{125}. Squaring gives 2200≡1(mod125),2^{200}\equiv1\pmod{125}, and subtracting 11 gives N≡0(mod125).N\equiv0\pmod{125}. Also, 22002^{200} is divisible by 8,8, so N≡7(mod8).N\equiv7\pmod8.
Among the multiples of 125125 from 00 through 999,999, only 375375 is 77 modulo 8.8. Therefore the last three digits are 375.375.
Thus, the correct answer is C.
LIVE by Po-Shen Loh
Programs

LIVE Classes

Self-Paced Classes

Stars

Scholarship

About Us

Who Is Po-Shen Loh?

Email Contact

Newsletter

Jobs

Become a Star

For a more Thought Full world.

© 2026 Expii, Inc.Terms of UsePrivacy PolicyCOPPA Privacy Policy