Let S be the set of all integers z>1 such that for all pairs of nonnegative integers (x,y) with x<y<z, the remainder when 2025x is divided by z is less than the remainder when 2025y is divided by z. What is the sum of the elements of S?
Answer Choices:
A. 3041
B. 3542
C. 3750
D. 4044
E. 4319
π¬ Join the Discussion
Stuck on this problem or want to share your approach?
Continue the conversation and see what others are thinking: View Forum Thread
Define {x}=xββxβ to be the "fractional part" of a number and let Ξ±={z2025β}. Note that the given condition is equivalent to:
{z2025β},{2β
z2025β},β¦,{(zβ1)β
z2025β}
being a strictly increasing sequence.
If Ξ±=0, then the sequence is identically zero, which fails. If Ξ±>z1β, then there exist k and k+1 such that:
{z2025kβ}=kΞ±{z2025(k+1)β}=(k+1)Ξ±β1
Since Ξ±<1, we must have kΞ±>(k+1)Ξ±β1, and so this violates the condition for the pair (k,k+1).
Hence, we must have 0<Ξ±β€z1β, which implies that the condition is equivalent to the fact remainder when 2025 is divided by z is equal to 1. Therefore, z can be any factor of 2024 that is greater than 1. Note that the sum of the factors of 2024=23β
11β
23 is given by 15β
12β
24=4320, and so the desired answer is 4320β1=4319, which corresponds to (E) 4319β.
The problems on this page are the property of the MAA's American Mathematics Competitions