辗转相除法算得上是非常古老的算法了,第一次出现在公元前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数量:现在我想把这些ps4和手办平均白送给别人,我最多能送给几个人啊?“
老王算了起来,一七得七,二七十四,三八妇女节,五一劳动节….很显然,老王没有任何头绪。不过老王不服气,苹果香蕉也不要了,立马跑图书馆找书看去了。
你洋洋得意,又抓起老王一个苹果咬了下去。不过等等,老王不会,你就真的会吗?为了避免出洋相,还是悄悄过来,让我告诉你吧:
其实多项式的辗转相除法和正整数的辗转相除法是一样的。
于是乎,你发现(2x + 6)也就是(x + 3)能被多项式f(x)或多项式g(x)整除,这玩意,就叫最大公因数。记作:
嗯,到了第x天,你就可以把你的这些ps4和手办白送给(x+3)个人,如果你有的话。
你正乐呵着,老王又回来,手上还拿着本翻开《高等代数》,告诉你答案是(x+3),还说:“我还能找到两个多项式u(x),v(x),使得
你大概不会吧?那我来教给你!“
你虽然敬佩老王的好学之心,但也不愿意发现自己不会后嘲笑自己,于是一边说着:“我其实知道”,一边偷瞄了一眼那边神秘的《高等代数》,那翻开的一页正写着:
于是你把这些记了下来,假装思考了一会儿,然后告诉了老王答案。老王很是敬佩你,说你是个数学天才什么的,表示要把那12个苹果和15个香蕉都送给你,虽然它们早已被你吃的差不多了。
老王表示自己也要好好钻研数学,正所谓“学好数理化,走遍天下都不怕”。你一面在一片宁静祥和的氛围中目送老王揣着那本《高等代数》回家,一面想着:
“卧槽,我就知道老王翻到原题了。”