一道⁺ / edao.plus

#10178

同余问题·物不知数

数论六年级 #同余

题目

有一个数，除以 3 余 2，除以 5 余 3，除以 7 余 2。

求满足条件的最小正整数。

解法

分析：用中国剩余定理逐步求解。

从 N ≡ 2 (mod 7) 开始，N = 7k + 2。

代入 N ≡ 3 (mod 5) 得 k ≡ 3 (mod 5)，N = 35m + 23。

代入 N ≡ 2 (mod 3) 得 m ≡ 0 (mod 3)，N = 105n + 23，

最小正整数解为 n = 0 时 N = 23。
N ≡ 2 (mod 7)
=N = 7k + 2
N ≡ 3 (mod 5)
=7k + 2 ≡ 3 (mod 5)
=2k ≡ 1 (mod 5)
=k ≡ 3 (mod 5)
N = 35m + 23
=
N ≡ 2 (mod 3)
=35m + 23 ≡ 2 (mod 3)
=2m ≡ 0 (mod 3)
=m ≡ 0 (mod 3)
N = 105n + 23
=
最小解
=n = 0, N = 23

方法

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

练一练

有一个数，除以 3 余 1，除以 5 余 2，除以 7 余 3。求满足条件的最小正整数。

相关题目

#10025 韩信点兵·余同问题

同余 / 枚举法

数论六年级

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

数论六年级