一道⁺ / edao.plus

#10025

韩信点兵·余同问题

数论六年级 #同余 #枚举法

题目

一筐鸡蛋，1个1个拿正好拿完；

2个2个拿剩1个；

3个3个拿剩1个；

4个4个拿剩1个；

5个5个拿剩1个；

6个6个拿剩1个；

7个7个拿正好拿完。

问这筐鸡蛋最少有多少个？

解法

N-1 是 [2,3,4,5,6]=60 的倍数，故 N=60k+1。验 k=5：N=301=7×43 ✓。最少 301 个。
余数=1
公倍数=60
N−1 的取值 (60的倍数)
k N = 60k+1 是7的倍数？结论
1 “61” ✗
2 “121” ✗
3 “181” ✗
4 “241” ✗
5 “301” ✓

方法

同余两个数除以 m 余数相同，记作 a ≡ b (mod m)。余数守加、守减、守乘——整除问题的万能语言。枚举法按某个顺序把所有可能性“走一遍”，保证不重不漏。

练一练

一叠卡片，3张3张数余2张，5张5张数余2张，7张7张数余2张。

最少有多少张？

相关题目

#10178 同余问题·物不知数

数论六年级

#10184 同余问题·中国剩余定理

数论六年级