一道⁺ / edao.plus

#10184

同余问题·中国剩余定理

六年级·数论·同余

题目

有一筐苹果，3个3个数余2个，5个5个数余3个，7个7个数余4个。这筐苹果最少有多少个？

解法

分析：设苹果数为 N，则 N ≡ 2 (mod 3)，N ≡ 3 (mod 5)，N ≡ 4 (mod 7)。从 N ≡ 4 (mod 7) 开始逐步求解：N = 7k + 4，代入得 k ≡ 2 (mod 5)，即 k = 5m + 2；N = 35m + 18，代入得 m ≡ 1 (mod 3)，即 m = 3n + 1；故 N = 105n + 53，最小解 n = 0 时 N = 53。
N ≡ 4 (mod 7)
=N = 7k + 4
N ≡ 3 (mod 5)
=7k + 4 ≡ 3 ⇒ k ≡ 2 (mod 5)
k = 5m + 2
=N = 35m + 18
N ≡ 2 (mod 3)
=35m + 18 ≡ 2 ⇒ m ≡ 1 (mod 3)
m = 3n + 1
=N = 105n + 53
最小解
=n = 0, N = 53

方法

同余两个数除以 m 余数相同，记作 a ≡ b (mod m)。余数守加、守减、守乘——整除问题的万能语言。

练一练

有一箱橘子，4个4个数余3个，6个6个数余5个，9个9个数余2个。这箱橘子最少有多少个？

相关题目

#10025 韩信点兵·余同问题

同余 / 枚举法

数论六年级

#10178 同余问题·物不知数

数论六年级