AMC 8 2012 Problem 15

AMC8 2012 年第 15 题

余数与同余★★★☆☆

The smallest number greater than 2 that leaves a remainder of 2 when divided by 3, 4, 5, or 6 lies between what numbers?

大于 2 且除以 3,4,5 或 6 所得余数均为 2 的最小整数在下面哪两个数之间？

A. $\hspace{.05in}40\text{ and }50$
B. $\hspace{.05in}51\text{ and }55$
C. $\hspace{.05in}56\text{ and }60$
D. $\hspace{.05in}\text{61 and 65}$
E. $\hspace{.01in}\text{66 and 99}$

正确答案 · Correct Answer

解析 · Solution

Solution 1

To find the answer to this problem, we need to find the least common multiple of 3, 4, 5, 6 and add 2 to the result. To calculate the least common multiple, we need to find the prime factorization for each of them.

3 = 3^{1}

4 = 2^{2}

5 = 5^{1}

, and

6 = 2^{1}*{3^{1}}

. So the least common multiple of the four numbers is

2^{2}*{3^{1}*{5^{1}}} = 60

, and by adding 2, we find that that such number is 62. Now we need to find the only given range that contains 62. The only such range is answer

\textbf{(D)}

, and so our final answer is

61\text{ and65}

. We have to find the smallest number

x

for

x \equiv 2\mod3

x \equiv 2\mod4

, and

x \equiv 2\mod5

. We are excluding six because it won't make our divisors relatively prime. For the first equation,

x \equiv 2\mod3

holds remainder(

r

) of 2. Now we have to find

M

. Our

M

which is all divisors multiplied by each other divided by the divisor we are using. So our

M

\displaystyle \frac{3 \cdot 4 \cdot 5}{3} = 20

. We now need to find the inverse of

a

times

M

and solve

a

. Doing this we can get

20a \equiv 1\mod3

, and the smallest value of

a

where this is true is 2. Now we multiply every value we have which gets us

2 \cdot 20 \cdot 2

. Then we repeat for mod 4 and mod 5. For mod 4 the numbers

r

M

a

are 2, 15, and 3 respectively. For mod 5 we get 2, 12, and 8. Now we have to multiply all our values and we get 80 (mod 3), 90 (mod 4), and 192 (mod 5). Now we do

80+90+192\mod{5 \cdot 4 \cdot 3}

. This is

362\mod60

. This means

x \equiv 2\mod60

, but since it needs to be greater than 2, we get 62, which divided by six also has a remainder of 2. So 62 is in the range of

61\text{ and65}

. If CRT didn't make sense, this video is very good: Chinese Remainder Theorem | Sun Tzu's Theorem Additionally, this page is great: CRT Let

x

the number of problem. By Chinese Remainder Theorem, we know that

$\begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 2 \pmod 4 \\ x \equiv 2 \pmod 5 \end{cases}

$. $

x \equiv 2 \pmod 6

$ is exclude because it won't make our divisors relatively prime. The solution in this problem is: $

x \equiv \sum^{n=3}_{k=1} a_kb_kc_k \pmod {4×3 \times 5} \implies x\equiv \sum^{n=3}_{k=1} a_kb_kc_k \pmod {60}

$ where: $

a_k: \text{The product of all moduli except the k-th modulus.}

$ $

b_k: \text{Inverse modular}

$ $

c_k: \text{remainder of x by k-th modulus}

$ Since the $

c_1=c_2=c_3=2

a_1= \frac{3×4 \times 5}{3} = 20 \implies 20b_1 \equiv 1 \pmod 3 \implies 2b_1 \equiv 1 \pmod 3 \therefore b_1=2

a_2= \frac{3×4 \times 5}{4} = 15 \implies 15b_2 \equiv 1 \pmod 4 \implies 3b_2 \equiv 1 \pmod 4 \therefore b_2=3

a_3= \frac{3×4 \times 5}{5} = 12 \implies 12b_2 \equiv 1 \pmod 5 \implies 2b_2 \equiv 1 \pmod 5 \therefore b_3=3

therefore

x\equiv \sum^{n=3}_{k=1} a_kb_kc_k \pmod {60} \Rightarrow x\equiv 20×2 \times 2 + 15×2 \times 3 + 12×2 \times 3\pmod {60} \Rightarrow x\equiv 242 \pmod {60} \Rightarrow x\equiv 2 \pmod {60}

Thus,

x=60m+2>2 \implies m>0

and for

m=1 \implies x=62

. Correct answer:

D

继续练习

免费刷 2012 整卷 →