※ 引述《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 這種長相的也算是比較單純的多項式了，
不知道有沒有資料庫在分類？
看了 L 大寫的之後，雖然在要求 x 項係數只能是 1 或 -1 的情況下 B 很有限，
但如果換其他數字應該也可以弄出類似的結果？
d 之於 x^2 + ax + b 就像 13 之於 x^2 - x + 2，這種。
畢竟 quadratic interger 的冪次一定都可以寫成一次式。
或許可以針對 x 項係數，可以得到一組不同的整數 d，只是不知道有什麼用XD
: 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，在製造 h 的時候，跳過這種 c 就好。
因為 x-c | f,g，這代表我們其實可以把 x-c 各提出一個，這時候 deg--;
最多就跳過 n 個 c，而一旦真的跳過 n 個 c，其實 g|f 就很直觀了。
舉個例子的話，就是 f(x) = x^13-2731x-2730 和 g(x) = x^2-x-2 這種，
c 要是都有挑到 2 和 -1 的話就等於做完了。
就算跳過的 c 有 n-1 個那麼多，也還有 m-n+2 個 c，
對於這個方法的需求（over-determining h）來說也已經足夠了。
雖然真到了這個地步的時候，肯定是把 g 的最後一根代入 f 最快吧。
至於要求 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 掉。
第一個條件可以用只看 pp(f) 和 pp(g) 來實現，而第二個條件可以寫成
Σ_{g(c)≠0} f(c)/g(c) * c^k/p'(c) = 0, for k < n
Σ_{g(c)≠0}f(c)/g(c) * c^n/p'(c) ≠ 0
其中 p(x) = Π_{g(c)≠0} (x-c)
第二式應該是多餘的，因為多項式全等定理會保證 deg(h) = m-n，所以就不上色了。
此時 N = m+1，
還有 h(x) = p(x) * Σ_{g(c)≠0} f(c)/[g(c)p'(c)(x-c)]。
h 的長相出乎我意料之外，還可以寫得蠻美的。
--
好像有些人誤會成我沒有去看 f 和 g 的係數，其實我算是有在看的？
都代 m+1 個 c 了，這跟把係數看完也沒差別了吧。
我好奇找一個很大的數去代的方法，如果加上 primitive 會不會比較能壓低 N？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 163.13.112.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1638467613.A.4C5.html
※ 編輯: Vulpix (163.13.112.58 臺灣), 12/03/2021 04:02:31
※ 編輯: Vulpix (163.13.112.58 臺灣), 12/06/2021 04:19:47