大衍求一術(shù)是南宋數(shù)學(xué)家秦九韶在其著作 《數(shù)書(shū)九章》 中提出的用于求解一次同余式方程的方法。
以常見(jiàn)的“物不知數(shù)”問(wèn)題為例，如一個(gè)數(shù)除以 3 余數(shù)是 2，除以 5 余數(shù)是 3，除以 7 余數(shù)是 2，求這個(gè)數(shù)。計(jì)算過(guò)程如下： 1. 先找到 5 和 7 的公倍數(shù)中除以 3 余 1 的最小數(shù)，如 70。 2. 再找到 3 和 7 的公倍數(shù)中除以 5 余 1 的最小數(shù)，如 21。 3. 最后找到 3 和 5 的公倍數(shù)中除以 7 余 1 的最小數(shù)，如 15。 然后用上述三個(gè)數(shù)字分別乘對(duì)應(yīng)的余數(shù)，再相加。具體來(lái)說(shuō)： 1. 70 是除以 3 余 1 的數(shù)，題中除以 3 余 2，所以拿 70 乘 2。 2. 21 是除以 5 余 1 的數(shù)，題中除以 5 余 3，所以拿 21 乘 3。 3. 15 是除以 7 余 1 的數(shù)，題中除以 7 余 2，所以拿 15 乘 2。 70×2 + 21×3 + 15×2 = 233，之后用得到的數(shù)依次減去 3、5、7 的最小公倍數(shù) 105，直至得到合適的最小數(shù)。即 233 - 105 = 128，128 - 105 = 23，23 就是本題的答案。 對(duì)于形如 ax ≡ 1 (mod n)，(a,n) = 1 的同余式，秦九韶的大衍求一術(shù)還有一種解法。首先令 k0 = 0，k1 = 1，r0 = n，r1 = a 。然后讓 r0 和 r1 作帶余除法，即 r0 = q2r1 + r2 ，接著用 r1 和 r2 作帶余除法，即 r1 = q3r2 + r3 ，如此逐步計(jì)算。 此外，對(duì)于某數(shù)用 3 除余 2，用 5 除余 3，用 7 除余 2 的問(wèn)題，解為 3 除的余數(shù)用 70 乘之，5 除的余數(shù)用 21 乘之，7 除的余數(shù)用 15 乘之，把三個(gè)乘積相加，再減去 105 的倍數(shù)。即 2×70 = 140，3×21 = 63，2×15 = 30 ，140 + 63 + 30 = 233 ，233 - 2×105 = 233 - 210 = 23 。