One basket of eggs.

1粒1粒拿，正好拿完。

Remove 1 by 1, nothing left in basket.

2粒2粒拿，还剩1粒。

Remove 2 by 2, one left in basket.

3粒3粒拿，正好拿完。

Remove 3 by 3, nothing left in basket.

4粒4粒拿，还剩1粒。

Remove 4 by 4, one left in basket.

5粒5粒拿，还差1粒才能拿完。

Remove 5 by 5, short of one to complete.

6粒6粒拿，还剩3粒。

Remove 6 by 6, 3 left in basket.

7粒7粒拿，正好拿完。

Remove 7 by 7, **nothing** left in basket.

8粒8粒拿，还剩1粒。

Remove 8 by 8, one left in basket.

9粒9粒拿，正好拿完。

Remove 9 by 9, nothing left in basket.

请问筐里最少有几粒鸡蛋 ？

At least how many eggs are there in the basket?

[Hint] This is a Chinese Remainder Problem (” 韩信点兵”)

—— [Solution] —–

Let there be minimum X eggs in the basket.

Remove 1 by 1, nothing left in basket:

X = 0 mod (1) …[1]

=> trivial & useless !

Remove 2 by 2, one left in basket:

X = 1 mod (2) … [2]

Remove 3 by 3, nothing left in basket:

X = 0 mod (3) … [3]

Remove 4 by 4, one left in basket:

X = 1 mod (4) … [4]

Remove 5 by 5, short of one to complete:

X = -1 mod (5) … [5]

Remove 6 by 6, 3 left in basket:

X = 3 mod (6) … [6]

Remove 7 by 7, nothing left in basket:

X = 0 mod (7) … [7]

Remove 8 by 8, one left in basket:

X = 1 mod (8) … [8]

Remove 9 by 9, nothing left in basket:

X = 0 mod (9) … [9]

Simplify [6] = [3]

X = 3 mod (6)

X = 3 mod (3×2)

X = 3 mod (3)

X = 0 mod (3) … [3]

Notice [3], [7],[9]: X is multiple of 3, 7, 9

=> X is mulitple of LCM (3,7,9) = 63

**X = 0 mod (63) … [3,7,9]**

Similarly,

X = 1 mod (2)

X = 1 mod (4)

X = 1 mod (8)

=> X = 1 mod (LCM {2, 4, 8}) [**Note @**]

=>** X = 1 mod (8) … [8]**

**[Note @]:**

X = 1 mod (2)

=> X – 1 = 2n

Similarly,

X = 1 mod (4) <=> X – 1 = 4m

X = 1 mod (8) <=> X – 1 = 8t = 4.(2n)t’ = 2.(4m)t”

These 3 equations <=> X = 1 mod (8)

Simplify the 9 equations by considering only the remaining 3 equations:

**X = 0 mod (63) … [3,7,9]**

**X = -1 mod (5) … [5]**

**X = 1 mod (8) … [8]**

Since (8, 5, 63 ) are **co-primes pair-wise –**** ***ie (8, 5), (8, 63), (5, 63) are relative primes to each other in each pair* – we can apply the Chinese Remainder Theorem to the last 3 equations:

…[#]

By sequentially “mod” the equation [#] by 8, 5, 63, we get:

(63×5).u1 = 1 mod (8) **… [8]**

315.u1 = (39×8+3).u1 = 1 mod (8)

3.u1 = 1 mod (8)

=> **u1 = 3 **[as 9 = 1 mod (8)]

(63×8).u2 = -1 mod (5)**… [5]**

504.u2 = (50×11 – 1).u2 = -1 mod (5)

-1.u2= -1 mod (5)

**u2 = 1 **[as -1 = -1 mod (5)]

(5×8).u3 **=** 0 mod (63)**… [3,7,9]**

40.u3 = 0 mod (63)

**u3 = 0** [as 0 = 0 mod (63) ]

[#]:

X = (63×5).u1 + (63×8).u2 +(5×8).u3 mod (8x5x63)

X = (63×5).**3** + (63×8).**1** + (5×8).**0** mod (2520)

X =** 63 x 23** = 1449 mod (2550)