Determine all positive integers $n$ for which there exists a polynomial $f(x)$ with real coefficients, with the following properties: (1) for each integer $k$, the number $f(k)$ is an integer if and only if $k$ is not divisible by $n$; (2) the degree of $f$ is less than $n$. (Hungary) Géza Kós
Problem
Source:
Tags: algebra, polynomial, modular arithmetic, function, number theory, greatest common divisor, system of equations
26.02.2011 21:35
01.03.2011 04:16
Part 1: We claim that all $n= p^a$ where $p$ is a prime number and $a \in \mathbb{N}$ are solutions. Consider the polynomial $f$ such that \[f(x) = \frac{(x+1)(x+2) \cdots (x+p^a -1)}{p^{A}}\] Where $A = p^{a-1} + p^{a-2} + \dots + p + 2-a$. This function can be directly verified to satisfy properties (1) and (2). Part 2: We claim that $n= p^a$ where $p$ is a prime number and $a \in \mathbb{N}$ are the only solutions. Let $f$ be a polynomial satisfying (1) and (2). First note that the values $f(k)$ are integers for all infinitely many $k \in \mathbb{Z}$. Applying Lagrange interpolation yields that $f$ has rational coefficients. Now let $f(x) = P(x)/d$ where $d \in \mathbb{N}$ and $P(x)$ has integer coefficients. By (1), $f(0)$ is not an integer. Therefore there exists a prime number satisfying that $p^b \| d$ and $p^a \| P(0)$ where $a<b$. However, $p^a \| P(p^b)$ and therefore $P(p^b)$ is not an integer. This implies that $n | p^b$ and that $n$ is a power of a prime number.
11.02.2013 23:11
Is it right to go the following way after getting $ f(x)=\frac{g(x)}{m} $? Firstly let's prove that $n\mid m$. Assume opposite. Then $f(m)=\frac{b_0}{m}$ is an integer. Then $f(mn)=\frac{mn*Q(x)+b_0}{m}=n*Q(x)+\frac{b_0}{m}$ is an integer since $\frac{b_0}{m}$ is an integer. It leads us to a contradition. Let $n=p_1^{\alpha_1}...p_k^{\alpha_k}$. Assume that $k>1$. Then consider $f(p_i^{\alpha_i})$. $n$ doesn't divide $p_i^{\alpha_i}$ since $k>1$. Then $f(p_i^{\alpha_i})$ is integer. Then $p_i^{\alpha_i} \mid n \mid g(p_i^{\alpha_i)}$ so $p_i^{\alpha_i} \mid b_0$. Since for every $i<>j$ $(p_i^{\alpha_i };p_j^{\alpha_j})=1$ we get $m \mid b_0$. Then considering $f(m)=\frac{g(m)}{m}=Q(m)+\frac{b_0}{m}$ which is integer we get final contradition. Then $k=1$. Now the only thing to do is to show examples for $n=p^\alpha$ Thanks
24.12.2013 20:37
For a polynomial $f$ with degree less than $n$ we have\[\sum_{j=0}^{n}(-1)^{j}{n\choose j}f(x+j)=0\] for each $x\in \mathbb{Z}$. By letting $x$ vary we know that ${n\choose j}f(0)\in\mathbb{Z}$ for $1\leq j\leq n-1$. If the gcd of these coefficients $1$, we conclude $f(0)\in\mathbb{Z}$. So there has to be a prime $p$ that divides ${n\choose j}$ for $1\leq j\leq n-1$. By Lucas theorem we conclude that $n$ is a power of $p$.
21.01.2015 23:39
If two primes divide n, by lagrange all coefficients are rational, and we translate the problem into the following: "prove no number $Q$ and polynomial $f \in \mathbb{Z}$ exists such that $Q | f(x) \Leftrightarrow x \neq 0 ($ mod $n$). For every $k$ take $p^e || Q$ take $x = 1$ (mod $n/(p^{v_p(n)})$), $x=k$ (mod $p^e$). with Chinese Theorem. We have $x \neq 0 $( mod $n$) $\Rightarrow Q | f(x) \Rightarrow q^e | f(x) \Rightarrow q^e | f(k)$. Therefore $ Q | f(k) $ for all $k$ and so problem is false. If only one prime $p$ divides $n$, take $g(x)=(x-1)...(x-n+1)$ and take $f(x) = g(x) / p^{v_p(g(1))} $
27.02.2015 12:33
First by the lagrange interpolation,$f$ has rational coefficients. Let $f(x)=\frac{g(x)}{d}$ where $g(x)$ has integers coefficient. Clearly $d \neq1$ and hence I will get a prime $p$ and an integer $a$ such that $p^a \nmid g(0)$.Clearly as $p^a|g(p^a)-g(0)$,hence $p^a \nmid g(p^a)$.Hence $f(p^a)$ is not integer yielding $n|p^a$.Hence $n$ must be a prime power. Now the construction for $n$ being a prime power is easy.Take $f(x)=\frac{\prod_{i=1}^{p^a-1}(x-i)}{p^a}$ which clearly satisfies the conditions.
22.08.2016 17:47
Nice!
16.05.2018 14:23
Nice problem!
04.08.2023 16:53
I forgot that we can Lagrange interpolate on things other than $\{1,\ldots,n\}$ whoops The answer is any prime powers. $n=1$ is stupid, so assume that $n=p^i$ for some $i \geq 1$. Take the polynomial $f(x)=\frac{1}{p}\binom{x+p^a-1}{p^a-1}$. By Kummer's theorem, $p$ divides the binomial coefficient iff at least one of the rightmost $a$ base-$p$ digits of $(x+p^a-1)-p^a-1=x$ is nonzero, which occurs iff $p^a \nmid x$, hence this polynomial works. Now suppose that $n$ is not a prime power. In general, the $n-2$-th finite difference $\Delta^{n-2} f$ is a linear polynomial, and furthermore if $k \equiv -1 \pmod{n}$ then $\Delta^{n-2} f(k)$ is an integer linear combination of integers (in particular, $f(k)$ through $f(k-n+2)$), hence also an integer. Then comparing $\Delta^{n-2} f(k+n)$ with $\Delta^{n-2} f(k)$, we find that the coefficient of the linear term must be a rational number (whose denominator is a divisor of $n$, but this doesn't matter), hence the constant term is also rational. Therefore $f$ is also a rational polynomial. Since $f(0)$ is a rational non-integer, there must exist some prime $p$ with $\nu_p(f(0))<0$. Then for large enough $m$, we also have $\nu_p(f(p^m))<0$ (multiply $f$ by some integer $N$ it an integer polynomial, and then divide it out again after getting $Nf(0) \equiv Nf(p^m) \pmod{p^m}$), so $f(p^m)$ is not an integer, which is a contradiction since $n \mid p^m$ as $n$ is not a prime power.
13.03.2024 22:13
Cute! We claim that the answer is power of primes. Construction is $f \equiv \frac{1}{p}\binom{x+p^c-1}{p^c-1}$ which works by Kummer-Lucas theorem. Now by lagrange interpolation on numbers not divisible by $n$ we have $P \in \mathbb{Q}[X]$ so let $P = \frac{Q}{D}$ for some constant $D$ and integer polynomial $Q$, since $P(0) \not\in \mathbb{Z}[X]$ we have a prime whose $v_p$ in denominator is higher, but this immediately yields $n$ i s a power of prime. Done.