2023 AIME I Problem 7

Below is the professionally curated solution for Problem 7 of the 2023 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:modular arithmeticChinese Remainder Theoremcasework

Difficulty rating: 2560

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.

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 6Full ExamProblem 8

Problem 7 in Other Years