返回题库

余数问题

Remainders

专题
Brainteaser / 脑筋急转弯
难度
L5

题目详情

求满足下列条件的最小正整数:它除以 2 余 1,除以 3 余 2,……,除以 10 余 9。

What is the smallest positive integer that has a remainder of 1 when divided by 2, a remainder of 2 when divided by 3, ..., and a remainder of 9 when divided by 10?

解析

设所求最小正整数为 XX。题意等价于

X=2X2+1X=3X3+2X=10X10+9X = 2X_2 + 1 \\ X = 3X_3 + 2 \\ \vdots \\ X = 10X_{10} + 9

Xi=Xi+1X'_i = X_i + 1,则两边同时加 1 得到

X+1=2X2X+1=3X3X+1=10X10X+1 = 2X'_2 \\ X+1 = 3X'_3 \\ \vdots \\ X+1 = 10X'_{10}

也就是说,X+1X+1 必须能被 2,3,4,5,6,7,8,9,102,3,4,5,6,7,8,9,10 同时整除。这些数的最小公倍数是 2520,因此

X+1=2520X=2519X+1=2520 \quad\Rightarrow\quad X=\boxed{2519}

Original Explanation

Let XX denote the smallest positive integer we are solving for. We can further define X2,X3,...,X10X_2, X_3, ..., X_{10} as positive integers such that:

X=2×X2+1X=3×X3+2X=10×X10+10X = 2 \times X_2 + 1 \\ X = 3 \times X_3 + 2 \\ \vdots \\ X = 10 \times X_{10} + 10

Let Xi=Xi+1i{2,3,...,10}X'_i = X_i + 1 \forall i \in \{2, 3, ..., 10\}.

Then, adding 11 to both sides of each equations:

X+1=2×X2X+1=3×X3X+1=10×X10X + 1 = 2 \times X'_2 \\ X + 1 = 3 \times X'_3 \\ \vdots \\ X + 1 = 10 \times X'_{10}

In other words, we are now looking for XX such that X+1X+1 is perfectly divisible by 2, 3, 4, 5, 6, 7, 8, 9, and 10. The least common multiple of these numbers is 2520, and thus XX is 2519\boxed{2519}