用辗转相除法求多项式的最大公因式

辗转相除法算得上是非常古老的算法了，第一次出现在公元前300年，欧几里得的《原本》上。这玩意本来是求两个正整数的最大公约数的。

比如隔壁老王今天出来散步，碰上了你，可能会问你一道low爆的数学题：我这儿有12个苹果，15个香蕉，不能切开，最多能平均分给几个小朋友啊？

太简单了啊，你心里默念着古老的辗转相除法：

15 = 12 + 3
12 = 3 x 4 + 0

你转眼间说出了答案：3，并拿了老王一个苹果吃了起来。边吃边想：为什么不考考隔壁老王呢？

于是你对老王说：”假如我现在有6台ps4，每天还要再买2台，所以第x天ps4的数量是2x+6；我还有一些手办，经常交易所以数量时多时少，但第x天的数量可以计算出来，是x^3 + 6x^2 +11x + 3。也就是说假设现在是第x天，那么

我的ps4数量： $f(x) = 2x + 6$ 我的手办数量： $g(x) = x^3 + 6x^2 + 11x + 6$

现在我想把这些ps4和手办平均白送给别人，我最多能送给几个人啊？“

老王算了起来，一七得七，二七十四，三八妇女节，五一劳动节….很显然，老王没有任何头绪。不过老王不服气，苹果香蕉也不要了，立马跑图书馆找书看去了。

你洋洋得意，又抓起老王一个苹果咬了下去。不过等等，老王不会，你就真的会吗？为了避免出洋相，还是悄悄过来，让我告诉你吧：

其实多项式的辗转相除法和正整数的辗转相除法是一样的。

$g(x) = \frac{x^2}{2}f(x) + (3x^2 + 11x + 6)$

$(3x^2 + 11x + 6) = \frac{3x}{2}f(x) + (2x + 6)$

$f(x) = 2x + 6$

于是乎，你发现(2x + 6)也就是(x + 3)能被多项式f(x)或多项式g(x)整除，这玩意，就叫最大公因数。记作：

$(f(x),g(x)) = x + 3$

嗯，到了第x天，你就可以把你的这些ps4和手办白送给(x+3)个人，如果你有的话。

你正乐呵着，老王又回来，手上还拿着本翻开《高等代数》，告诉你答案是(x+3)，还说：“我还能找到两个多项式u(x),v(x)，使得

$(f(x),g(x)) = u(x)f(x) + v(x)g(x)$

你大概不会吧？那我来教给你！“

你虽然敬佩老王的好学之心，但也不愿意发现自己不会后嘲笑自己，于是一边说着：“我其实知道”，一边偷瞄了一眼那边神秘的《高等代数》，那翻开的一页正写着：

$2x + 6 = (3x^2 + 11x + 6) - \frac{3x}{2}f(x)$

$=(g(x) - \frac{x^2}{2}f(x)) - \frac{3x}{2}f(x)$

$= -\frac{x^2+3x}{2}f(x) + g(x)$

因此

$u(x) = -\frac{x^2+3x}{2} , v(x) = 1$

$(f(x),g(x)) = -\frac{x^2+3x}{2}f(x) + g(x)$

于是你把这些记了下来，假装思考了一会儿，然后告诉了老王答案。老王很是敬佩你，说你是个数学天才什么的，表示要把那12个苹果和15个香蕉都送给你，虽然它们早已被你吃的差不多了。

老王表示自己也要好好钻研数学，正所谓“学好数理化，走遍天下都不怕”。你一面在一片宁静祥和的氛围中目送老王揣着那本《高等代数》回家，一面想着:

“卧槽，我就知道老王翻到原题了。”

Posts