前几天在一个程序员闲聊群里看到一道题题目就一句话“简单修改一个n让它变成7的倍数”。说实话第一眼看到这题我是有点懵的——修改一个nn是个变量还是某个具体数字怎么个改法后来大家七嘴八舌一讨论问题才逐渐变得清晰任给你一个正整数n能不能通过改动它的某一位数字让新得到的数能被7整除而最漂亮的结论是——只改个位永远够用。无论n长什么样你都能只调整个位数字把它变成7的倍数。这个结论并不复杂但背后的同余思想特别耐嚼今天就从这道题出发把证明过程、适用范围和实际用处一次聊透。1. 一个没头没尾的题先把它翻译成人话1.1 “修改一个n”到底允许动哪里这类一句话题目在数学趣题和算法群里特别常见最坑人的地方不是解法而是定义不清。第一次读完题目后我先把“修改一个n”补全成自己认为最合理的版本任给一个正整数 n允许把它的十进制表示中某一位数字改成 0 到 9 中的另一个数字改动后最高位不能为 0问是否总能得到一个 7 的倍数如果 n 本身已经是 7 的倍数那题目已经完成所以真正要回答的是“n 不是 7 的倍数时改一位能不能成功”。讨论中大家还发现了一个更强的版本不只改一位能成功甚至把所有其他位都锁死、只允许改个位也一定能成功。先看两个具体例子。n123个位是3把3改成6得到1267×18。n2024个位是4把4改成3得到20237×289。两个例子都只动了最后一位。一位数的情况比较特殊比如 n1把个位1改成7得到7是7的倍数n5 也一样改成7就行。所以绝大多数一位数都能通过改个位完成。但 n7 本身已经是7的倍数如果题目强制要求“必须改一位且结果还是正整数”那就没有解了这个边界细节后面专门讨论。1.2 7为什么是这道题的“主角”选7不是随机的。小学阶段我们学过很多整除判定2和5看末位3和9看各位数字和4看末两位8看末三位11看奇数位与偶数位的差。但7一直没有课本级的简便口诀。原因在于7在十进制底下“藏得很深”10 对 7 取余是 310² 对7取余是210³ 对7取余是610 的幂模7的周期长达6位不像2和5那样只看最后一位就完事。正是因为7没有一望即知的口诀它成了各种趣味数学题和算法题最爱的“硬骨头”判断一个大数能不能被7整除真的需要做除法或者走截尾法循环。反过来“凑一个7的倍数”这个问题也因此变得有意思——如果题目换成“凑2的倍数”答案太显然改个位为偶数就行根本不需要证明换成“凑3的倍数”可以调各位数字和但复杂得多。7恰好卡在一个“直接改个位就能成、但大多数人一时想不到”的位置上。1.3 直觉上的第一反应改十位行不行很多人第一反应是改最高位比如把2024改成1424或3424这种比较大的变化但验算下来都不靠谱。实际上改十位不一定总能成功原因是十位数字变化等价于整体加上一个 k×10而 10 在模7下的变化只覆盖一部分余数不够灵活。真正能保证成功的是直接改个位。为什么是它因为个位的变化可以等间隔地覆盖0到9十个数字而模7一共只需要7类余数十有八九能命中。这个直觉在下一节会变成严格的证明。现在先记住一个方向末位才是“万能拧手”。2. 只改个位为什么永远都能凑出7的倍数2.1 把“改个位”翻译成一条同余式设原数为 n去掉个位后是 q个位数字为 d于是n 10q d我们的操作是把 d 换成某个 x ∈ {0,1,...,9}得到新数 n′ 10q x。目标n′ 能被7整除也就是10q x ≡ 0 (mod 7)又因为 n ≡ 10q d (mod 7)移项得到 10q ≡ n - d (mod 7)代入目标式x ≡ d - n (mod 7)到这里问题已经从“找一个数”变成了“找一个余数”。需要的 x 不是一个天外飞仙它只是一个同余类的代表元。接下来就看这个代表元能不能落在0到9之间。2.2 需要的余数恰好落在0到6之间设 r (d - n) mod 7按惯例取 0 ≤ r 7。关键点来了r 的取值范围正好就是 {0,1,2,3,4,5,6}而这七个数字每一个都是合法的个位数字。所以直接令 x r就一定能落在0-9范围内。这就是证明的全部秘密。至于0到9多出来的7、8、9三个数字它们会制造“第二个解”。下表列出 x 从0到9时与7的模关系新个位 x0123456789x mod 70123456012如果算出来的 r0那么 x0 或 x7 都能用r1则 x1 或 8r2则 x2 或 9。剩下的 r3,4,5,6 时r7 已经超过9就只有一个解。这里有个值得注意的细节0算不算7的倍数按数学定义00×7当然是7的倍数。所以在允许结果为0的场合x0是一个合法选择如果题目要求最终必须是一个正整数那就得避开0。2.3 完整证明任意n都能只靠改个位完成把上面的推理整理成三段式分解 n10qd改个位为 x得到 n′10qx。根据同余的加减性n′≡0 (mod 7) 等价于 x≡d-n (mod 7)。令 r 是 d-n 除以7的余数0≤r7那么 r 本身就是0到6之间的数字新数个位取 xr即可保证被7整除。证明到这里已经完整。它没有用到 n 的任何额外性质因此是“任意 n 都成立”的结论。更妙的是它甚至不需要真的算出 n′ 有多大——只要知道了 n 除以7的余数和它的个位数字r 就确定了。做一个实例验证n31415926。先算 31415926 mod 7。用纸笔逐步取模4487989×731415923所以 31415926314159233余数是3。个位 d6于是 r(6-3)≡3 (mod 7)把个位6改成3得到31415923。验证31415923÷74487989确实整除。如果 n7 这种边界按这个公式走d7n mod 70r(7-0)≡0候选解是 x0得到0或 x7等于没改。如果把“0是7的倍数”也放进来那么把7改成0也算一种答案只是通常讨论正整数时不算。这个约定问题做算法题时一定要在开头问清楚。3. 从7到任意模数成立的边界在哪里3.1 模数不超过10时个位修改法必可行把“7”换成任意 m≤10 的正整数证明几乎不用变需要的 x 满足 x≡d-n (mod m)令 r(d-n) mod m则 0≤rm≤10而 r 一定在0-9内所以直接取 xr 即可。举例说明改成2的倍数只需要把个位调成偶数。比如17个位7改成0、2、4、6、8中的任一个得到10、12、14、16、18全是2的倍数。改成5的倍数个位调成0或5。改成3的倍数个位也能永远调成功。比如4040 mod 31d0r(0-40) mod 3 1? 实际算一下40 mod 310-1-1≡2所以 r2把个位0改成2得到423×14。改成10的倍数个位改成0即可当然要考虑原数首位不为0的限制。这里要特别说明m≤10这个条件重点在于“余数集合大小不超过个位可选数字的个数”和 m 与 10 是否互质没关系。改成4的倍数也一样r 在0-3取 xr 即可。3.2 模数超过10之后反例开始出现当 m10情况就变了。需要的余数 r 可能落在10到m-1之间而个位只能提供0-9于是找不到对应的 x。最直接的反例是 m11n11。n本身是11的倍数如果允许不改题目已完成。但如果强制必须修改个位把个位1改成0,2,3,...,9得到的10,12,13,...,19对11取余分别是10,1,2,...,8没有一个是0。所以“必须改个位且必须改掉原数字”时11这个数永远凑不成11的倍数。m12也是一样n12强制改个位无解。更深一层的原因是模数有12种余数个位只有10种变化可选的数字少两个遇到缺的那两个余数就必然失败。3.3 加个“只能变大/只能变小”的约束结论就崩了原题没说不准变大还是变小所以 x 既可以比 d 小也可以比 d 大。但现实中经常有人把题目记错成“只能改大一位”或者“只能改小一位”这时候定理就不成立了。只允许把个位改大n7个位7只能改成8或98和9都不是7的倍数失败。只允许把个位改小n7个位7改成0到6。如果要求正整数结果0不能用1到6也都不是7的倍数失败。不限制方向但强制“结果不能等于原数”n7依然是问题元凶因为唯一候选x7恰好等于没改x0又会被某些人排除。这些边界再一次说明一道好的趣题往往不是难在中间的证明而是难在开头那句约定没写清楚。实际做这类问题我会先把“修改”的定义钉死改几位限制方向吗结果允不允许0然后再往下推。4. 手算和代码最快找到那个应改的数字4.1 手算套路先取模再倒推个位如果不想写代码标准流程是写出 n 的个位 d其余部分记为 q。计算 r(d-n) mod 7也就是对 n 取模后拿个位减掉它再取余数。新个位优先取 xr如果 r 恰好等于原个位 d且题目要求必须改动就考虑 xr7前提是不超过9。验证 n′10qx 是不是7的倍数。两个手算例子。n20242024 mod 71d4r3个位改成3得2023。验证20237×289。n987654先算它对7的余数7×141093987651987654比它大3所以余数是3。个位 d4r(4-3)≡1新个位可以取1或8所以候选是987651和987658。前者是7×141093后者是7×141094。这个例子展示了“r1时有两个解”的情况一个改小3一个改大4看业务上更喜欢哪个方向。4.2 Python实现只改个位与穷举任意位直接给代码。第一个函数只改个位把得到的候选全部列出来def fix_last_digit(n: int, m: int 7) - list[int]: q, d divmod(n, 10) r (d - n) % m ans [] for k in range(10): x r k * m if x 9: ans.append(q * 10 x) return ans跑几个用例print(fix_last_digit(2024)) # [2023] print(fix_last_digit(987654)) # [987651, 987658] print(fix_last_digit(31415926)) # [31415923] print(fix_last_digit(123)) # [126]如果允许修改任意一位想找“改动后离原数最近”的7的倍数可以用一段暴力枚举把每一位都试着改成0-9计算差值绝对值保留最小。def nearest_multiple_any_digit(n: int) - int: if n % 7 0: return n s list(str(n)) best None best_diff None for i in range(len(s)): for ch in 0123456789: if ch s[i]: continue t int(.join(s[:i] [ch] s[i1:])) if t % 7 0: diff abs(t - n) if best is None or diff best_diff: best, best_diff t, diff return best这段代码能生成“允许改任意一位的最优解”满足一些把题理解为“改一位让它离原数最近”的需求。注意它默认不允许改最高位为0并且要求至少改动一位如果 n 本身就是7的倍数它直接返回 n。4.3 如果题目要求“改动尽量小”怎么处理刚才的暴力枚举能解决“任意位、改动最小”的版本。但如果只允许改个位“改动最小”就是在两个候选r 和 r7若 r7≤9之间挑一个使 |x-d| 最小的。举例n987654 时候选是 x1 和 x8原个位 d4差值分别是3和4所以选 x1改后是987651只差3。更一般地改个位造成的偏差最多不会超过9但实际因为 r 在0-6之间x 又只能等于 r 或 r7所以候选值相对原个位通常偏离很小。这也是为什么“只改个位”在工程里特别好用它把搜索空间压到了常数级一个同余式子就出答案。5. 这题背后的同余思想其实到处都是5.1 校验码ISBN和身份证里的“7的倍数”“补一个数让整体能被 k 整除”这个动作在现实世界中叫校验码。ISBN-10 的校验位设计就是前9位数字加权求和补上第10位让加权和对11取模为0。身份证号码的最后一位校验码也是加权求和、模11取余算出来的。它们使用的都是同一套工具模运算 反推缺失位。回到我们的题目给一个数 n改个位让它成为7的倍数本质上就是“让个位这个自由变量去补足 10q 对7的缺口”。这种“留一个自由位、其他位固定、按模运算反推自由位”的思路是很多编码和校验系统的底层逻辑。5.2 7的整除速判口诀是怎么来的很多人见过这个口诀去掉个位剩下数减去个位的两倍反复进行最后能判断原数是不是7的倍数。它为什么对设原数 N10qd口诀算的是 q-2d。我们有10qd 10(q-2d)21d而 21d 显然是7的倍数所以 N≡0 (mod 7) 当且仅当 10(q-2d)≡0 (mod 7)。又因为10与7互质可以安全地把10从同余式里消掉于是等价于 q-2d≡0 (mod 7)。这个推导和本文“改个位”的推导用的是同一条同余桥10qd≡0 (mod 7)。可以说“7的倍数”这个看似没什么规律的主题在同余视角下其实是很有规律的。5.3 对写代码的人生成“对齐数”的通用思路日常写测试用例、造数据时经常要“把某个随机数对齐到某个步长”。比如时间戳对齐到15分钟、文件大小对齐到4KB、股票数量对齐到100股等等。最常用的写法是向上取整def align_up(n: int, m: int) - int: return ((n m - 1) // m) * m而本文的“改个位凑倍数”适合另一种约束只允许动最末一位。比如某个协议里最后一位是校验位前面若干位是业务数据那么计算校验位时就会用到公式 r(d-n) mod m。这本质上和“随机数对齐”是同一套心法只不过约束条件更苛刻。回头看这题真正难的地方不在证明而在把“修改一个n”这句话想清楚。我第一次拿到题时先是懵了一会儿为什么非得是7然后列了一堆枚举方案。当发现只改个位就永远够的时候我的第一反应是那还枚举什么一道题先找自由变量再算余数最后反推答案——这个三步走比任何暴力搜索都快得多也更优雅。以后我再遇到“把一个数变成X的倍数”的需求我的默认检查顺序会是允许动哪一位有没有方向限制容不容忍0这三个条件一旦定下来同余式往纸上一摆答案自己就漏出来了。