Find all integers $ n\ge 2$ having the following property: for any $ k$ integers $ a_{1},a_{2},\cdots,a_{k}$ which aren't congruent to each other (modulo $ n$), there exists an integer polynomial $ f(x)$ such that congruence equation $ f(x)\equiv 0 (mod n)$ exactly has $ k$ roots $ x\equiv a_{1},a_{2},\cdots,a_{k} (mod n).$
Problem
Source: Chinese TST 2009 4th P2
Tags: algebra, polynomial, modular arithmetic, number theory, prime numbers, number theory proposed
06.04.2009 12:18
I have a small question : k can take all values in the set ${ \{1,..,n}$ or it a fixed number ? If it takes all values in the set $ \{1,..,n\}$ then only $ n=1,2,4,p$ satisfy condition .
09.04.2009 07:35
Can you answer my question ,Fang-jh ? To prevent spamming , I will post my solution in the case $ k$ can take all values in the set $ \{1,..,n\}$ . The first ,we will show that $ n$ must be a power of prime . Suppose the contrary , then $ n$ can be written in the form $ pq$ where $ p,q$ is relative prime and greater than 1 . Consider $ n-1$ numbers $ {1,..,n-1}$ . By the condition of problem ,exist a polynomial f such that the equation $ f(x)\equiv 0(\mod n)$ has exactly n-1 solution 1,..,n-1 . We will show that 0 is also a solution of this equation . Because $ p,q>1$ so $ p,q<n-1$ , by the fundamental property of polynomial , we have $ p|f(p)-f(0)$ and $ q|f(q)-f(0)$ ,and because $ p|f(p),q|f(q)$ so $ pq|f(0)$ ,and this gives contrary . Therefore n must be a power of prime . Let $ n=p^a$ ,we have two cases : 1) $ p$ is an odd integer (or $ p>2$ ) . We will show that $ a=1$ ,if not consider two numbers $ 0,p^{a-1}$ .By the condition of the problem ,exist f such that equation $ f\equiv 0 (\mod p^a)$ has exactly two solution 0 and $ p^{a-1}$ (obvious solutions are considered in $ F_n$) . We can write f in the form : $ f(x)=(x-0)(x-p^{a-1})G(x)+ax+b$ . Because $ p^a|f(0),f(p^{a-1})$ so $ p^a|b$ and $ p|a$.Consider $ x=2p^{a-1}$ , it is not very hard to show that it is a solution of equation $ f=0 (\mod p^a)$ and it gives contrary . Hence in this case only $ a=1$ ,or $ n=p$ is a prime number satisfies condition . 2) p=2 . By the similar trick ,we have $ a\leq 3$ (by consider two numbers $ 0,2^{a-2}$ and and other number $ 2^{a-1}$ ) . If $ a=3$ we only need to consider two number 0,6 and 4 . Hence $ a\leq 2$ and then $ n\in \{1,2,4\}$ . Thus all numbers satisfy condition are 1,2,4,p.
09.04.2009 13:18
The official solution is $ n=4$ or $ n$ is prime.
07.05.2010 18:29
Another solution. Let $f(x)=a_nx^n+...+a_0x^0=\sum_{k=0}^{n} a_kx^k$ Suppose we can represent $n$ as $n=pq$, Where $1<p\le q$. If $p=q=2$, then, obviously, the statement holds. Otherwise assume $q<p+q<pq$ $(1)$ Notice that expanding binom, we get $(p+q)^k=p^k+q^k$ for any $k>0$. So, if we set $f$ to have $0, p, q$ as its roots (or $0, p$ if $p=q$) then we have: $f(p+q) \equiv f(p)+f(q) \equiv 0 \pmod{n}$ yielding that $p+q$ is a root too, which contradicts $(1)$ The only cases left (when we can't represent $n$ as $pq$ where $1<p \le q$) are $2,p$ and also $n=4$ when $p=q=2$. For prime numbers and $n=4$ the statement, obviously, holds. Hurray!
18.09.2019 23:33
I am assuming that $k$ is a fixed integer.Clearly any $n \le k$ is a solution since the condition we will be nothing then.From here we will assume that $n >k$.First I will show that $n$ is a prime power.Assume for country that $m$ has at least two prime divisors write $m=pq$ where $gcd(p,q)=1$ then greedily take all residues mod $q$ and mod $p$ that weren't taken before(I mean we haven't taken a $a$ so that $a$ produces the same residue mod$p$ or mod $q$) if there isn't any take one that has a residue mod $p$(or $q$ if $q>p$) not taken before if there is non take one arbitary then it is easy to see that there is a residue $r$ that $r$ is not in the set but $r \pmod q$ and $r \pmod p$ are in the set which by CRT we will get a contradiction.Now assume that $n=p^{\alpha }$ where $p$ is an odd prime then let $0,p^{\alpha -1}$ be in our set but $2.p^{\alpha -1}$ not to be there then we will get a contradiction using the fact that $f(a+kp^{\alpha -1}) \equiv f(a)+kp^{\alpha -1}f'(a)$ and so $\alpha =1$.In this case Since we have a fild we can use lagrange interpolation formula.Next assume that $n=2^{\alpha }$.If $\alpha \ge 3$ then take $0,2^{\alpha -1},2$ in the set but not $2+2^{\alpha -1}$ in the set then again using hensel's lemma and the fact that $f'(0) \equiv f'(2) \pmod 2$ we get a contradiction.So $\alpha \le 2$ meaning that all the solutions are: $\{x| x \le k \} \cup \{p|p is a prime \} \cup \{ 1,4 \}$