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:
Answer (049):
Suppose n is an extra-distinct integer, and for k∈{2,3,4,5,6}, let rk be the remainder when n is divided by k.
- If n is even, then r2=0, and r4 and r6 must be even. Thus r4=2 and r6=4. Because n≡r6≡4(mod6), it follows that n≡1(mod3), so r3=1. Now the only available value for r5 is 3 . From these congruences, it follows that n+2 is divisible by 2,3,4,5, and 6 . Therefore n=60m−2 for some positive integer m.
- If n is odd, then r2=1, and r4 and r6 must be odd. Thus r4=3 and r6=5. Because n≡r6≡5(mod6), it follows that n≡2(mod3), so r3=2. Hence n+1 is divisible by 2,3,4, and 6 , and thus n=12m−1 for some positive integer m. The only available values for r5 are 0 and 4 . Therefore either n≡−1(mod60) or n≡35(mod60).
It follows that among any 60 consecutive positive integers, exactly 3 are extra-distinct. Thus there are 3⋅16=48 extra-distinct positive integers from 1 to 960 . There is 1 additional extra-distinct integer from 961 to 1000 because there is one extra-distinct integer between 1 and 40 . Hence the requested number of extra-distinct integers is 48+1=49.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions