Question

如果正整数 $n$ 除以 $2$ 、 $3$ 、 $4$ 、 $5$ 、 $6$ 所得的余数互不相同，则称 $n$ 为 超互异。求小于 $1000$ 的超互异正整数的个数。

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.$

答案

答案：49

知识点：模运算中国剩余定理分类讨论

难度评级：2560

解答：

设 $r_k$ 为 $n$ 模 $k$ 的余数，并注意到 $r_2 \equiv r_4 \pmod 2$ 、 $r_2 \equiv r_6 \pmod 2$ ，且 $r_3 \equiv r_6 \pmod 3$ 。若 $r_2 = 0$ ：则 $r_4$ 是偶数且不能等于 $r_2$ ，所以 $r_4 = 2$ ；接着 $r_6$ 是偶数且避开 $\{0, 2\}$ ，所以 $r_6 = 4$ ，这给出 $r_3 = 1$ ；最后 $r_5$ 避开 $\{0, 1, 2, 4\}$ ，所以 $r_5 = 3$ 。这些条件说明 $n \equiv -2$ 对 $2, 3, 4, 5, 6$ 分别成立，即 $n \equiv 58 \pmod{60}$ 。

若 $r_2 = 1$ ：类似地 $r_4 = 3$ ，然后 $r_6 = 5$ ，给出 $r_3 = 2$ ，而 $r_5$ 避开 $\{1, 2, 3, 5\}$ ，所以 $r_5 \in \{0, 4\}$ 。选择 $r_5 = 4$ 时， $n \equiv -1 \pmod{60}$ ，即 $n \equiv 59$ ；选择 $r_5 = 0$ 时， $n \equiv 11 \pmod{12}$ 且 $5 \mid n$ ，即 $n \equiv 35 \pmod{60}$ 。

小于 $1000$ 的正整数中，同余于 $35$ 的有 $17$ 个，同余于 $58$ 的有 $16$ 个，同余于 $59$ 的有 $16$ 个，都是模 $60$ ，意义下，因此总数为 $17 + 16 + 16 = 49$ 。

Write $r_k$ for the remainder of $n$ modulo $k,$ and note $r_2 \equiv r_4 \pmod 2,$ $r_2 \equiv r_6 \pmod 2,$ and $r_3 \equiv r_6 \pmod 3.$ If $r_2 = 0:$ then $r_4$ is even and different from $r_2,$ so $r_4 = 2;$ then $r_6$ is even and avoids $\{0, 2\},$ so $r_6 = 4,$ which gives $r_3 = 1;$ finally $r_5$ avoids $\{0, 1, 2, 4\},$ so $r_5 = 3.$ These say $n \equiv -2$ modulo each of $2, 3, 4, 5, 6,$ i.e. $n \equiv 58 \pmod{60}.$

If $r_2 = 1:$ similarly $r_4 = 3,$ then $r_6 = 5,$ giving $r_3 = 2,$ and $r_5$ avoids $\{1, 2, 3, 5\},$ so $r_5 \in \{0, 4\}.$ The choice $r_5 = 4$ gives $n \equiv -1 \pmod{60},$ i.e. $n \equiv 59;$ the choice $r_5 = 0$ gives $n \equiv 11 \pmod{12}$ with $5 \mid n,$ i.e. $n \equiv 35 \pmod{60}.$

Below $1000$ there are $17$ integers congruent to $35,$ $16$ congruent to $58,$ and $16$ congruent to $59$ modulo $60,$ for a total of $17 + 16 + 16 = 49.$

2023 AIME I 第 7 题

答案：49

难度评级：2560

解答：

其他年份的第 7 题