just generalization:prove that any polynomial with degree d in $\mathbb{N}_{p_1.p_2...p_k}[x]$has at most $d^k$

People nobody could solve this this is an excellent problem think on it

Just no one see this nice problem within numerous spam messages...

sam-n wrote: just generalization:prove that any polynomial with degree d in $\mathbb{N}_{p_1.p_2...p_k}[x]$has at most $d^k$ This sentence immediately reveals how can we prove statement: by induction. We are able to show that $a_1$, $a_2$, ... can be step by step uniquely restored from $a_0$. Do you need further explanations? It is really excellent problem.

yes just u need a isomomorphism and because $N{}_p{}_i[x]$ is fieldand all polynomial in it has at most d roots.

Please explain more because I was the only peson solved this problem at the exam and my solution was different from the one you say. Well if you want me I'll send my solution that is very beautiful.

Omid Hatami! Whom are you asking? Sam-n? Me?

Well each of you that send your solution I'd be thankful.Also if you want me I'll send my solution.

Maybe tomorrow...

I've been waiting here for a few days and you haven't sent your solution.

I have not time at the moment.

Well please send your solution. I'm in a hurry.

I am not under the right circumstances now to think about olympiad problems, especially about hard number theory problems, but I just wanted to note that a particular case of the problem, namely to show that the equation $x^2=x$ has only four solutions: x = 0, x = 1 and two numbers x = ...90625 and x = ...09376 which can be constructed by a special algorithm, is solved in Е. Б. Дынкин, В. А. Успенский, Математические беседы, Moscow 1952, section 2, chapter II, 2. (Maybe this book has an English translation - it certainly has a German one: E. B. Dynkin, W. A. Uspenski, Mathematische Unterhaltungen.) The next paragraph, 3, tells something about certain p-adic numbers, but I fear these are not the "real" p-adic numbers considered in number theory. Anyway I am posting the above since it may be a bit helpful. Myth, you are a real master of one-line messages! Darij

Hi Omid Hatami! I found small difficulty in my proof yesterday. And today I have realized that your statement is wrong. There are exist non-zero number $a\in\mathbb{N}_{10}$ s.t. first $k$ digits of $a$ are divisible by $2^k$ ($a=...2112$). I am sure that you are able to prove it Analogously, there are exist non-zero number $b\in\mathbb{N}_{10}$ s.t. first $k$ digits of $b$ are divisible by $5^k$ ($b=...3125$) Consider equation $ax=0$. It has one trivial root $x=...000$. Moreover, it has one nontrivial root $b$ !!! Contradiction, since $d=\deg(ax)=1$ and $d^2=1$. What is wrong in my constuction? I still remember your fault on "golden sets" I can proof your statement if polynomial has coefficients from $\mathbb{Z}_+$ or, more precisely, not all of its coefficients are divisible by "$2^\infty$" (as number $a$) and $5^\infty$.

Well I'm so sorry. This is my second fault. The polynomial is monic.

Well I also did this and I used divisibility by $2^{\infty}$ and $5^{\infty}$. Of course my solution was induction on $d$ using the equation $d^2=(d-1)^2+2(d-1)+1$ But where is the solution using isomorphism on the field $\mathbb{N}{}_p{}_i[x]$ I also apologize becuase of my fault and I promise be careful before posting something.

Hi Omid Hatami! Maybe your fault will be good lesson for you for next time. I have changed my mind. We don't need induction. Here my solution. It is not fully detailed, but I hope everyone can complete it. Consider $\mathbb{N}_p$. We can well define number $-a$: first $k$ digits of $-a$ are first $k$ digits of $p^k-a$. Suppose $f\in\mathbb{N}_p[x]$ and $a$ is a root of $f$. Then we can write $f(x)=(x-a)\cdot g(x)$, where $g\in\mathbb{N}_p[x]$, $\deg(g)=\deg(f)-1$. Indeed, we obtain coefficients of $g$ from Horner's method. It is easy to show that product of non-zero numbers in $\mathbb{N}_p[x]$ isn't equal to zero (...00). So we conclude $f$ have at most $d=\deg(f)$ roots in $\mathbb{N}_p[x]$. Consider $\mathbb{N}_{p_1p_2...p_k}$ and $f\in\mathbb{N}_{p_1p_2...p_k}[x]$. Suppose $a$ is a root of $f$. Define number $a^{(p_i)}\in\mathbb{N}_{p_i}$: first $k$ digits of $a^{(p_i)}$ are (first $k$ digits of $a$ as $m$-ary number)$\mod p_i^k$. We state that $a^{(p_i)}$ is well defined. Ok? Finally, we have $a^{(p_i)}$ is a root of $f^{(p_i)}(x)$ (we replace coefficients of $f$ with their $...^{(p_i)}$-form). Since $f$ is monic polynomial $f^{(p_i)}(x)$ is monic too, hence each of $f^{(p_i)}(x)$ ($i=1..k$) has at most $d$ roots. Thus we conclude that each root $a$ of $f(x)$ defines a set of $k$ roots of $f^{(p_1)}(x)$, ..., $f^{(p_k)}(x)$. Moreover, due to Chinese residue theorem each set of roots of $f^{(p_1)}(x)$, ..., $f^{(p_k)}(x)$ defines unique root of $f$. It follows that number of roots of $f$ isn't exceeded $d^k$.

hello Omid, I think the solution you were asking about is like this. Actually the problem is almost completely obvious if you know two relevant facts: 1. The Chinese remainder theorem, which in this case says that N10 (a ring) is the direct product N2 x N5. In other words, a solution x in N10 of P(x)=0 is an ordered pair of solutions (x2, x5) where P(x2)=0 in N2 and P(x5)=0 in N5. 2. N2 is the ring of 2-adic integers, which lives inside the field Q2 of 2-adic rational numbers. Therefore any polynomial of degree d has at most d solutions in N2. Same story for N5. I think the hard part if you don't know these things is to prove the equivalent of fact #2 by bare hands, it would be a hard problem (and congratulations if you solved it during an exam).