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

辗转相除法算得上是非常古老的算法了,第一次出现在公元前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个香蕉都送给你,虽然它们早已被你吃的差不多了。

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

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

Leave a Reply