2023 AIME I Problem 7

Attempt Problem 7 of the 2023 AIME I 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 2023 AIME I solutions, or check the answer key.

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

7.

Call a positive integer nn extra-distinct if the remainders when nn is divided by 2,2, 3,3, 4,4, 5,5, and 66 are distinct. Find the number of extra-distinct positive integers less than 1000.1000.

Answer: 49
Concepts:modular arithmeticChinese Remainder Theoremcasework
Difficulty rating: 2560
Solution:

Write rkr_k for the remainder of nn modulo k,k, and note r2r4(mod2),r_2 \equiv r_4 \pmod 2, r2r6(mod2),r_2 \equiv r_6 \pmod 2, and r3r6(mod3).r_3 \equiv r_6 \pmod 3. If r2=0:r_2 = 0: then r4r_4 is even and different from r2,r_2, so r4=2;r_4 = 2; then r6r_6 is even and avoids {0,2},\{0, 2\}, so r6=4,r_6 = 4, which gives r3=1;r_3 = 1; finally r5r_5 avoids {0,1,2,4},\{0, 1, 2, 4\}, so r5=3.r_5 = 3. These say n2n \equiv -2 modulo each of 2,3,4,5,6,2, 3, 4, 5, 6, i.e. n58(mod60).n \equiv 58 \pmod{60}.

If r2=1:r_2 = 1: similarly r4=3,r_4 = 3, then r6=5,r_6 = 5, giving r3=2,r_3 = 2, and r5r_5 avoids {1,2,3,5},\{1, 2, 3, 5\}, so r5{0,4}.r_5 \in \{0, 4\}. The choice r5=4r_5 = 4 gives n1(mod60),n \equiv -1 \pmod{60}, i.e. n59;n \equiv 59; the choice r5=0r_5 = 0 gives n11(mod12)n \equiv 11 \pmod{12} with 5n,5 \mid n, i.e. n35(mod60).n \equiv 35 \pmod{60}.

Below 10001000 there are 1717 integers congruent to 35,35, 1616 congruent to 58,58, and 1616 congruent to 5959 modulo 60,60, for a total of 17+16+16=49.17 + 16 + 16 = 49.

← Problem 6#6
Full Exam

Problem 7 in Other Years