推 alfadick :g(x) = (x - x_1)^p_1 (x - x_2)^p_2 .. 04/08 15:42
→ alfadick :這在哪本書會講？ 04/08 15:42
※ 引述《ad0960 (停留)》之銘言：
: 第二的算法是我有問題的：
: 定義2多項式：x^11和x^2+x+1
: 然後令x^2+x+1=0, and then (x+1)(x^2+x+1)=x^3-1=0, -> x^3=1
: -> x^11=x^2, ->將3帶到x^2裡，得3^2=9。
: 答案是9。
: 這個解法我有問題，為什麼可以去令x^2+x+1=0呢？
: 請問有版友可以幫法幫給一個嚴格推理的計算過程嗎？
: 感謝！！
: 推 LPH66 :後一法其實是在做多項式除法 04/08 10:54
: → LPH66 :做多項式除法時令除式為 0 代入被除式這招還滿常見的 04/08 10:55
: → ad0960 :您好，我的問題是為什麼可以令為0？ 04/08 10:56
: → LPH66 :不過實際上多項式除法的餘式應是 -x-1 就是 04/08 10:56
: → LPH66 :f(x) = g(x)q(x) + r(x) 代入使 g(x) = 0 的 x 之後 04/08 10:56
: → ad0960 :因式定理中，一次因式時令為0，那是方便的說法。 04/08 10:57
: → LPH66 :就會剩下 r(x) 這是之所以令除式為 0 的理由 04/08 10:57
: ※ 編輯: ad0960 來自: 123.194.124.191 (04/08 10:58)
: → ad0960 :不好意思，不是因式定理，嚴格上來說是餘式定理。 04/08 11:00
: → ad0960 :我剛剛google確認了一下，餘式定理是用在一次因式。 04/08 11:02
: → ad0960 :在餘式定理中，對於ax+b，為了要找出-b/a，令ax+b=0 04/08 11:03
: → ad0960 :是為了方便的作法，但我這題是二次以上，這令為0的 04/08 11:04
: → ad0960 :動作，我找不到理由。 04/08 11:04
其實想法還是一樣的 基本上都是我推的那兩行
f(x) = g(x)q(x) + r(x) 代入使 g(x) = 0 的 x 後就剩下 r(x)
g(x) 是一次式時沒什麼問題
g(x) 是二次式以上時其實有一個比較嚴格一點的做法:
令 g(x) = (x - x_1)^p_1 (x - x_2)^p_2 ... (x - x_n)^p_n
然後分別求除以 (x - x_i)^p_i 的餘式再合併起來
以原題來說 x^2+x+1 = (x - ω)(x - ω^2) 其中ω是 1 的(複數的)立方根
所以其實我們可以直接代入 ω 跟 ω^2
這樣會得到 x^11 除以 x - ω 餘 ω^11 = ω^2 ←┐
├ 注意這裡
x^11 除以 x - ω^2 餘 ω^22 = ω ←┘
那麼我們就能寫下 x^11 = (x - ω)(x - ω^2)q(x) + a(x - ω) + ω^2
於是 a(ω^2 - ω) + ω^2 = ω 解得 a = -1
最後所求餘式就是 -(x-ω) + ω^2 = -x + ω + ω^2 = -x-1 + (1+ω+ω^2) = -x-1
上面寫注意的地方其實就是之所以能夠直接令除式 = 0 的理由
可以看到 直接令 x^2+x+1 = 0 得到的式子 x^2
在 x = ω 跟 x = ω^2 兩個地方的值即為原式直接除以這兩個一次式的餘式
一般說來 若令這樣計算來的式子叫 h(x) 好了
那麼在使 g(x) = 0 的 x 值上會有 f(x) = h(x)
(這是由於計算時使用了等價於 g(x) = 0 的關係式
因此在整個計算過程裡得到的所有式子在這些 x 值上的取值都會相等
特別地, 最一開始的 f(x) 跟最後的 h(x) 也是如此)
而原來的計算步驟裡 最後求 a 的步驟實質上是在找一個次數比 g(x) 小的多項式
它在這些 x 值上取值 f(x) 而已
也就是說 我們其實是跳過了後面那個求 a 的步驟
直接找出了一個多項式 h(x) 它跟 f(x) 對 g(x) 同餘
那當然這個 h(x) 不一定就是 r(x) 還要再除下去到次數小於 g(x) 後才是 r(x)
這就是之所以能夠直接令 g(x) = 0 的理由
--
順帶一提, 如果原題用除到底的 -x-1 來做的話會得餘 -4
不過由於除數是 13 餘 -4 跟餘 9 是一樣的
因此這裡就不除到底 直接用 h(x) = x^2 來計算
--
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.69.49.38