※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1638567136.A.B42.html