《孙子算经》的「物不知数」题：某数除以3余2、除以5余3、除以7余2，求此数——古人的口诀解法暗含什么现代定理？
The Sunzi Suanjing poses this: a number leaves remainder 2 when divided by 3, remainder 3 by 5, and remainder 2 by 7 — find it, and what modern theorem hides inside the ancient verse solution?
最小答案是23。口诀「三人同行七十稀」给出系统解法：取70（除以3余1）、21（除以5余1）、15（除以7余1），分别乘以目标余数2、3、2，相加得233，再减去两个105即得23。原理是中国剩余定理：当各模数两两互质时，同余方程组在模105意义下恰有一个解。该定理今天被用来加速RSA解密、构造秘密分享方案，是连接古代算术与现代密码学的桥梁。
The smallest answer is 23. The classical verse uses auxiliary numbers: take 70, which is 1 modulo 3; 21, which is 1 modulo 5; and 15, which is 1 modulo 7; multiply them by the target remainders 2, 3 and 2, sum to get 233, then subtract two copies of 105 to reach 23. The principle is the Chinese remainder theorem: when the moduli are pairwise coprime, a system of simultaneous congruences has exactly one solution modulo their product, here 105. Today the theorem accelerates RSA decryption and supports secret-sharing schemes, bridging ancient reckoning and modern cryptography.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录仅给书名，无版次与年份；同一书名常对应多个版次，不臆测具体版本。
程大位,《算法统宗》,1592年刻本
Cheng Dawei, Suanfa Tongzong (Systematic Treatise on Arithmetic), 1592
#中国剩余定理 #同余方程组 #孙子算经
不分解大数也能初步筛掉许多合数，靠的是三百多年前的一条同余定理——费马小定理的内容是什么？为何通过了它的检验，这个数仍可能是合数？
Without factoring a large number you can still screen out many composites, thanks to a congruence theorem from over three centuries ago — what does Fermat's little theorem state, and why can a number pass its test yet still be composite?
定理说：若p是素数且a不被p整除，则a^(p−1)≡1（mod p），等价于a^p≡a（mod p）。于是无需分解就能筛合数：任取底数a，用快速幂算a^(n−1)模n，余数不是1即可断定n为合数。但逆命题不成立，341=11×31这样的伪素数照样通过检验，卡迈克尔数561更是对一切互素底数集体放行，故它只能充当概率性初筛，实战还需Miller-Rabin之类的多轮强化。
It states that if p is prime and a is not divisible by p, then a^(p−1) ≡ 1 (mod p), equivalently a^p ≡ a (mod p). This sieves composites without factoring: pick any base a, compute a^(n−1) modulo n by fast exponentiation, and any remainder other than 1 certifies n composite. The converse fails — pseudoprimes such as 341 = 11 × 31 sail through, and Carmichael numbers like 561 fool every coprime base at once — so the theorem serves only as a probabilistic first screen, hardened in practice by rounds of Miller-Rabin.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：此条未指向带版次的可引用著作（通识性内容、机构文件或未展开的英文书名），本库不提供独立书目出处；如需精确引用，需由编辑补全具体篇目与版次。
费马,致弗雷尼克勒·德·贝西的信函,1640年10月18日
P. de Fermat, letter to Bernard Frenicle de Bessy, October 18, 1640
#费马小定理 #同余 #伪素数
判断一个很大的整数能否被9整除，为什么只要把各位数字加起来看就行了？
To tell whether a huge integer is divisible by nine, why is it enough to add up its digits?
因为10除以9余1，所以10的任何次幂除以9都余1。把整数写成各位数字乘10的幂之和，取模9时每个幂都退化为1，剩下的恰好是数字之和——例如347与3+4+7=14模9同余。由此得到古老的「弃九法」：若一次运算的两边模9结果不同，则计算必有错误。它是同余算术最经典的日常应用之一。
Because ten leaves remainder one when divided by nine, and so does every power of ten. Write an integer as digits times powers of ten; modulo nine each power collapses to one, leaving exactly the digit sum — 347, for instance, agrees with 14, the total of its digits. Hence the old check called casting out nines: if the two sides of a computation disagree modulo nine, an error certainly occurred. It remains a most classic everyday application of modular arithmetic.
难度 入门 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
Hardy与Wright,《An Introduction to the Theory of Numbers》,Oxford University Press,1938
G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938
独立核验依据 · Independent verification: 核验依据 1 ISBN 9783540643326 (1938) · 核验依据 2 ISBN 9783540643326 (2008)
#弃九法 #整除判别 #模9同余