Re: [代數] 問一題模考的多項式
※ 引述《Vulpix (Sebastian)》之銘言：
: ※ 引述《TimcApple (肥鵝)》之銘言：
: : 今年數A的模考題，沒有原題，以下是簡述
: : ==============================================
: : 已知 a 是整數
: : 且 x^13 + x + 90 是 x^2 - x + a 的倍式
: : 試求 a
: : ==============================================
: : 本題是單選，因此刪一刪答案就出來了
: : 但我還是有幾個問題，有點抽象不好意思
: : Q1. 雖然可能的 a 只有一個，其它都不可能
: : 但要怎麼確定這個 a 真的是答案？
: 長除法、沒教的二次式綜合除法、用 x^2≡x-a 降次、代入 g 的根，四個選一個。
: 這應該是高中有超出範圍和沒超出範圍的範圍裡能用的招數了。
: : Q2. 有沒有一個定理類似以下敘述，或是反例
: : 「設整係數多項式 f, g, 會有一個正整數 N = N(f, g) 使得
: : 若有 N 個相異 c 滿足 g(c) | f(c), 則 g(x) | f(x) in Q[x]」
: : 由於有 2 | n(n+1) 的情況，整除只能在有理數多項式內
: 如果要求兩多項式都 primitive 的話，整除就可以限制在 Z[x] 上了吧。
: : Q3. 出題老師是怎麼知道，或是從哪裡知道
: : x^13 + x + 90 是 x^2 - x + a 的倍式的？
: 經驗或者前人的經驗吧？
: x^n+ax+b 這種長相的也算是比較單純的多項式了，
: 不知道有沒有資料庫在分類？
: : g(c) | f(c) 是 in Z, 但 g(x) | f(x) 是 in Q[x]
: : 或者我應該寫 存在正整數 M 使得 g(x) | M f(x) in Z[x]
: : 我目前想一想 方向有兩個
: : (1) 有沒有可能 g(x) 不整除 M f(x)
: : 但是有無限多個 c 滿足 g(c) | f(c)
: : (2) N 能被控制到多小的範圍
: 我是想先從 f,g 都 primitive 下手，m = deg(f) 而且 n = deg(g)，當然 m≧n。
: 如果 g(c) 都不是 0，那 f(c)/g(c) 就都是整數。
: 要是 c 有 m+1 個，可以拿其中 m-n+1 個用拉格朗日插值插出一個 h(x) in Q[x]，
: 其中 h(c) = f(c)/g(c) for all c。
: 在這裡如果能確保 deg(h) = m-n、而且每組 c 都插出同一個 h 的話，
: 那 N 就是 m+1。
: 不過這個條件感覺用起來很麻煩，
: 所以也可以換成直接拿 m+1 個 c 去插，但要能確保插出一個 m-n 次的 h，
: 也就是 m-n+1 次以上的係數都要是 0（而且 m-n 次的係數不能是 0）。
: 這樣 f 和 gh 就在 m+1 個相異數字上等值，所以 f = gh in Q[x]。
: 但如果有某個 g(c) 是 0，那我們可能很難看出 f 和 g 中 x-c 的重數。
: 要是 g 的 x-c 比 f 的還多，那就怎樣都不能整除了。
: 不過這方面不用擔心，因為我們看這個 c 也只看一次（所有 c 都相異）。
: 至於要求 primitive 則是因為我想起了個叫做 numerical polynomial 的東西。
: F in Q[x]，當整數 n 超過某數後 F(n) 都是整數，
: 那 F(x) 就可以寫成 C(x,k) 的線性組合，而且係數都是整數。
: 所以即便上面那個 h 的圖形通過無限多個格子點，
: 那也很難保證 h 是整係數的，反例就是 x(x+1)/2 這種。
: （其實 numerical polynomial 代任何整數都會算出整數。）
: 但是如果要求 f 和 g 都 primitive，
: 那 h 的 primitive part 和 g 的乘積就會是 f，
: 但 f = gh，所以 h = h 的 primitive part，也就是一個整係數多項式。
: 所以就這題來說，隨便挑 14 個相異整數 c 去算 f(c)/g(c) 然後插出 h。
: c │ f(c)/g(c)
: ──┴───────
: -6 -296833953
: -5 -38146970
: -4 -3050399
: -3 -113874
: -2 -1013
: -1 22
: 0 45
: 1 46
: 2 2071
: 3 199302
: 4 4793497
: 5 55486510
: 6 408146691
: 7 2202022966
: 然後插出來的是 x^11+x^10-x^9-3x^8-x^7+5x^6+7x^5-3x^4-17x^3-11x^2+23x+45。
: 的確 h 的 13、12 次係數是 0，而且 11 次係數不是 0。
: 又因為 f、g 都有係數 1 的項 => 都 primitive，
: 那就能知道 f = gh，而且 h 也的確是整係數多項式。
: 總之我覺得須要增加條件：
: f 和 g 都 primitive
: （不加這條的話，會有 g(c)|content(f) 的問題，那這樣我們會對 f 知之甚少。
: 又或者為了要把 g = content(f) 的因數的情況盡數排除，
: 只好在 N 上加上很多個 n，大概有 content(f) 的因數個數那麼多個 n。）
: 和 h 的高次項係數要 0 掉。
: 而第二個條件可以寫成
: Σf(c_i)/g(c_i) * c_i^k/d_i = 0, for k < n
: Σf(c_i)/g(c_i) * c_i^n/d_i ≠ 0 ，其中 d_i = Π_{j≠i} (c_i - c_j)
: 後半句應該是多餘的，因為多項式全等定理會保證 deg(h) = m-n，所以就不上色了。
: 此時 N = m+1。
這應該是個反例
f=x^ 2+100！ g=x
f/g=x+100!/x
所以x 從-100 到100 f/g都是整數
我覺得N 不論如何還是得依賴f 跟g 的係數
但是還是能證明如果gx|fx 那只有有限個正整c 數使得 fc/gc 為整數
就取整數d 使得df＝gh＋r
h,r 為整係數 然後考慮 df/g =h+r/g
因為deg r＜deg g 所以存在M 使得rx/gx ＜1 for all |x|＞M
所以只要N ＞2M 都是整除就可以保證r＝0
我自己算了一些方法估計N 都是係數^ deg指數成長
相較於線性複雜度的長除法可能不會更快
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.184.64.79 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1638567136.A.B42.html
推
12/04 07:38,
2年前
, 1F
12/04 07:38, 1F
→
12/04 07:38,
2年前
, 2F
12/04 07:38, 2F
→
12/04 07:38,
2年前
, 3F
12/04 07:38, 3F
推
12/04 07:43,
2年前
, 4F
12/04 07:43, 4F
→
12/04 07:43,
2年前
, 5F
12/04 07:43, 5F
→
12/04 07:44,
2年前
, 6F
12/04 07:44, 6F
討論串 (同標題文章)