结果恒为整数的多项式
By 苏剑林 | 2014-12-04 | 22467位读者 |昨晚上初等数论的时候,有这么一道题
求证
$$\frac{1}{3}x^3+\frac{1}{5}x^5+\frac{7}{15}x$$
恒为整数,其中$x$是一个整数。
更一般地,可以得到
$$\sum_{p\in\mathbb{P}}\frac{1}{p}x^p + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)x$$
恒为整数,其中$\mathbb{P}$是有限个素数的集合,还有更多整数值函数问题。要证明这些函数的值恒为整数,可以通过同余分析,证明分子总能被分母整除。但是,更妙的、同时往往会更简单的方法是,将结果赋予必然为整数的意义——可以是计算上的,也可以是操作上的。
比如证明${n\choose k}=\frac{n !}{(n-k)! k!}$恒为整数(假设目前的情况是只知道等号右边的表达式,不知道它的意义),只要表明它等于从$n$个东西中选择$k$个的组合数就行了,因为组合数必然是整数了。这是赋予函数操作上的意义。另外一个例子是证明$\frac{n(n+1)}{2}$恒为整数,既可以简单证明$n,n+1$之一必为偶数,从而恒为整数;又可以证明$\frac{n(n+1)}{2}=1+2+\dots+n$,右端是一个整数列的前$n$项和,所以其和自然为整数。也就是说,证明多项式值恒为整数的方法之一,就是将它表示为一个整数列的前$n$项和。
现在的问题是,如何求出这个整数列呢?作差分即可!比如$f(x)=\frac{1}{3}x^3+\frac{1}{5}x^5+\frac{7}{15}x$,$f(0)=0$,而
$$f(x)-f(x-1)=x^4-2 x^3+3 x^2-2 x+1$$
等号右端是一个整系数多项式,其值自然是整数,而因为
$$f(x)=\sum_{t=1}^{x}\left(t^4-2 t^3+3 t^2-2 t+1\right)$$
所以$f(x)$恒为整数。当然,该问题使用同余分析也不算复杂,当时,对于下面的题目,如果使用同余分析,就会相当复杂了。
记
$$f(x)=\sum_{p\in\mathbb{P}}\frac{1}{p}x^p + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)x$$
只需要注意到
$$\begin{aligned}f(x)-f(x-1)=&\sum_{p\in\mathbb{P}}\frac{1}{p}x^p + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)x\\
&-\sum_{p\in\mathbb{P}}\frac{1}{p}(x-1)^p - \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)(x-1)\\
=&\sum_{p\in\mathbb{P}}\frac{1}{p}\left[ x^p -(x-1)^p \right] + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)\\
=&\sum_{p\in\mathbb{P}}\frac{1}{p}\left[\sum_{k=1}^{p-1} {p\choose k} (-1)^{p-k+1} x^k \right] +\sum_{p\in\mathbb{P}}\frac{1}{p}+ \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)\\
=&\sum_{p\in\mathbb{P}}\left[\sum_{k=1}^{p-1} \frac{1}{p}{p\choose k} (-1)^{p-k+1} x^k \right] +1
\end{aligned}$$
注意,$p$是素数,因此$p\left|{p\choose k}\right.$,所以最后的式子是一个整系数多项式,因此$f(n)$是一个整数列的前$n$项之和,从而$f(x)$恒为整数。
转载到请包括本文地址:https://kexue.fm/archives/3103
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Dec. 04, 2014). 《结果恒为整数的多项式 》[Blog post]. Retrieved from https://kexue.fm/archives/3103
@online{kexuefm-3103,
title={结果恒为整数的多项式},
author={苏剑林},
year={2014},
month={Dec},
url={\url{https://kexue.fm/archives/3103}},
}
October 5th, 2015
机智