Problem:
Call a positive integer n extra-distinct if the remainders when n is divided by 2,3,4,5, and 6 are distinct. Find the number of extra-distinct positive integers less than 1000.
Solution:
n can either be 0 or 1(mod2).
Case 1: n≡0(mod2)
Then, n≡2(mod4), which implies n≡1(mod3) and n≡4(mod6), and therefore n≡3(mod5). Using CRT, we obtain n≡58(mod60), which gives 16 values for n.
Case 2: n≡1(mod2)
n is then 3(mod4). If n≡0(mod3),n≡3(mod6), a contradiction. Thus, n≡2(mod3), which implies n≡5(mod6).n can either be 0(mod5), which implies that n≡35(mod60) by CRT, giving 17 cases; or 4(mod5), which implies that n≡59(mod60) by CRT, giving 16 cases.
The total number of extra-distinct numbers is thus 16+16+17=049.
The problems on this page are the property of the MAA's American Mathematics Competitions