Maths Olympiad Prep

Library / /2 of 16

Number theory Difficulty 6.1 National olympiad Prove it Japan

Determine how many integers between 11 and 10001000 (inclusive) have the property that the remainders upon division by 22, 33, 44, 55, and 66 are all distinct.

Solution

Let nn be an integer with 1n10001 \le n \le 1000, and for each integer ii with 2i62 \le i \le 6, let rir_i denote the remainder when nn is divided by ii. We require that r2,r3,r4,r5,r6r_2, r_3, r_4, r_5, r_6 be pairwise distinct. Since 0rii10 \le r_i \le i - 1, in particular r2r_2 can only be 00 or 11.

Case 1: Assume r2=0r_2 = 0. Then nn is even, so r4{0,2}r_4 \in \{0, 2\}, and r2r4r_2 \neq r_4 forces r4=2r_4 = 2. Similarly r6{0,2,4}r_6 \in \{0, 2, 4\} and r6r2,r4r_6 \neq r_2, r_4 force r6=4r_6 = 4, which in turn gives r3=1r_3 = 1. Finally r5{0,1,2,4}r_5 \notin \{0, 1, 2, 4\} forces r5=3r_5 = 3. Hence the only possible tuple is
(r2,r3,r4,r5,r6)=(0,1,2,3,4), (r_2, r_3, r_4, r_5, r_6) = (0, 1, 2, 3, 4),
which, by the Chinese remainder theorem, holds precisely when n58(mod60)n \equiv 58 \pmod{60}.

Case 2: Assume r2=1r_2 = 1. Then nn is odd, so r4{1,3}r_4 \in \{1, 3\}, and r2r4r_2 \neq r_4 forces r4=3r_4 = 3. Similarly r6{1,3,5}r_6 \in \{1, 3, 5\} and r6r2,r4r_6 \neq r_2, r_4 force r6=5r_6 = 5, which in turn gives r3=2r_3 = 2. Finally r5{1,2,3,5}r_5 \notin \{1, 2, 3, 5\} forces r5{0,4}r_5 \in \{0, 4\}. Hence the only possible tuples are
(r2,r3,r4,r5,r6)=(1,2,3,0,5)and(1,2,3,4,5), (r_2, r_3, r_4, r_5, r_6) = (1, 2, 3, 0, 5) \quad \text{and} \quad (1, 2, 3, 4, 5),
which, by the Chinese remainder theorem, hold precisely when n35(mod60)n \equiv 35 \pmod{60} or n59(mod60)n \equiv 59 \pmod{60}.

Therefore it suffices to count the integers between 11 and 10001000 whose remainder modulo 6060 is 3535, 5858, or 5959. There are 1717, 1616, and 1616 such integers, respectively. Hence the total number is 4949.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.