Skip to main content

2025 AMC 12B Problem 23

Problem 23 of 25HarderNumber Theory

Let SS be the set of all integers z>1z \gt 1 such that for all pairs of nonnegative integers (x,y)(x, y) with x<y<z,x \lt y \lt z, the remainder when 2025x2025x is divided by zz is less than the remainder when 2025y2025y is divided by z.z. What is the sum of the elements of S?S?

Answer choices

Show solution

Solution

The condition requires k↦2025k mod zk \mapsto 2025k \bmod z to be strictly increasing on {0,1,…,z−1}.\{0, 1, \ldots, z-1\}. A strictly increasing list of zz distinct values in [0,z−1][0, z-1] must be 0,1,…,z−1,0, 1, \ldots, z-1, so 2025≡1(modz),2025 \equiv 1 \pmod z, i.e. 20242024 is divisible by z.z. Since 2024=23⋅11⋅23,2024 = 2^3 \cdot 11 \cdot 23, the sum of all its divisors is (1+2+4+8)(1+11)(1+23)(1+2+4+8)(1+11)(1+23) =15⋅12⋅24= 15 \cdot 12 \cdot 24 =4320.= 4320. Excluding z=1z = 1 leaves 4319.4319. Thus, the correct answer is E.
AoPS wiki

Tagged: modular arithmetic · divisibility · sum of factors

More practice