During an elementary number theory class last night, there was a problem:
Prove that \frac{1}{3}x^3+\frac{1}{5}x^5+\frac{7}{15}x is always an integer, where x is an integer.
More generally, one can obtain that \sum_{p\in\mathbb{P}}\frac{1}{p}x^p + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)x is always an integer, where \mathbb{P} is a finite set of prime numbers. There are many more such integer-valued function problems. To prove that the values of these functions are always integers, one can use congruence analysis to show that the numerator is always divisible by the denominator. However, a more elegant and often simpler method is to assign a meaning to the result that is necessarily an integer—this can be either computational or operational.
For example, to prove that \binom{n}{k}=\frac{n!}{(n-k)! k!} is always an integer (assuming for a moment that we only know the expression on the right and not its meaning), we only need to show that it equals the number of ways to choose k items from n items, as a combination count must be an integer. This is assigning an operational meaning to the function. Another example is proving that \frac{n(n+1)}{2} is always an integer; one can either simply prove that one of n or n+1 must be even, or prove that \frac{n(n+1)}{2}=1+2+\dots+n. Since the right side is the sum of the first n terms of an integer sequence, the sum is naturally an integer. In other words, one method to prove a polynomial always yields integers is to express it as the sum of the first n terms of an integer sequence.
The question now is, how do we find this integer sequence? We can use finite differences! For example, let f(x)=\frac{1}{3}x^3+\frac{1}{5}x^5+\frac{7}{15}x. We have f(0)=0, and f(x)-f(x-1)=x^4-2 x^3+3 x^2-2 x+1 The right side is a polynomial with integer coefficients, so its value is naturally an integer. Since f(x)=\sum_{t=1}^{x}\left(t^4-2 t^3+3 t^2-2 t+1\right) it follows that f(x) is always an integer. Of course, using congruence analysis for this problem is not overly complicated either. However, for the following problem, congruence analysis would become quite complex.
Let f(x)=\sum_{p\in\mathbb{P}}\frac{1}{p}x^p + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)x We only need to observe that \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 \\ &\quad - \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} \binom{p}{k} (-1)^{p-k+1} x^k + 1 \right] + \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}\binom{p}{k} (-1)^{p-k+1} x^k \right] + \sum_{p\in\mathbb{P}}\frac{1}{p} + 1 - \sum_{p\in\mathbb{P}}\frac{1}{p} \\ &= \sum_{p\in\mathbb{P}}\left[\sum_{k=1}^{p-1} \frac{1}{p}\binom{p}{k} (-1)^{p-k+1} x^k \right] + 1 \end{aligned} Note that since p is a prime, p divides \binom{p}{k} for 1 \le k \le p-1. Therefore, the final expression is a polynomial with integer coefficients. Thus, f(x) is the sum of the first x terms of an integer sequence, which implies that f(x) is always an integer.
When reposting, please include the original address of this article: https://kexue.fm/archives/3103
For more detailed information regarding reposting, please refer to: Scientific Space FAQ