CRT AIME Difficult
2012


Problem - 236

For a positive integer $p$, define the positive integer $n$ to be $p$-safe if $n$ differs in absolute value by more than $2$ from all multiples of $p$. For example, the set of $10$-safe numbers is $\{ 3, 4, 5, 6, 7, 13, 14, 15, 16, 17, 23, \ldots\}$. Find the number of positive integers less than or equal to $10,000$ which are simultaneously $7$-safe, $11$-safe, and $13$-safe.


Answer     958

For any integer n, let $r = n \pmod{p}$ where $0 \le r < p$. Then $n$ is $p$-safe if and only if $p - 2 > r > 2$. Therefore, there are $p-5$ qualified $r$.

Therefore a number $n$ that meets the requirement of this problem can have $2$ different residues $\pmod{7}$, $6$ different residues $\pmod{11}$, and $8$ different residues $\pmod{13}$. Because $7$, $11$, and $13$ are pairwise co-prime, we assert these exist one unique solution to a combination of one each of these congruent relations by the Chinese remainder theorem within the range of $1$ to $7\times 11\times 13 = 1001$.Therefore, there are totally $2\times 6\times 8=96$ solutions not exceeding $1001$. This means $960$ solutions not exceeding $10010$.

Meanwhile, it is easy to check manually and find $10006$ and $10007$ are two solutions greater than $10000$. Excluding these two, we find the final answer to this question is $\boxed{958}$.

report an error