$\mathbb{N}_{10}$ is generalization of $\mathbb{N}$ that every hypernumber in $\mathbb{N}_{10}$ is something like: $\overline{...a_2a_1a_0}$ with $a_i \in {0,1..9}$ (Notice that $\overline {...000} \in \mathbb{N}_{10}$) Also we easily have $+,*$ in $\mathbb{N}_{10}$. first $k$ number of $a*b$= first $k$ nubmer of (first $k$ number of a * first $k$ number of b) first $k$ number of $a+b$= first $k$ nubmer of (first $k$ number of a + first $k$ number of b) Fore example $\overline {...999}+ \overline {...0001}= \overline {...000}$ Prove that every monic polynomial in $\mathbb{N}_{10}[x]$ with degree $d$ has at most $d^2$ roots.
Problem
Source: Iran 2004
Tags: algebra, polynomial, algorithm, geometry, geometric transformation, induction, number theory
18.09.2004 15:08
just generalization:prove that any polynomial with degree d in $\mathbb{N}_{p_1.p_2...p_k}[x]$has at most $d^k$
28.09.2004 11:35
People nobody could solve this this is an excellent problem think on it
28.09.2004 11:52
Just no one see this nice problem within numerous spam messages...
28.09.2004 14:03
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.
28.09.2004 14:44
yes just u need a isomomorphism and because $N{}_p{}_i[x]$ is fieldand all polynomial in it has at most d roots.
28.09.2004 21:05
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.
28.09.2004 21:09
Omid Hatami! Whom are you asking? Sam-n? Me?
28.09.2004 21:45
Well each of you that send your solution I'd be thankful.Also if you want me I'll send my solution.
28.09.2004 21:56
Maybe tomorrow...
02.10.2004 22:09
I've been waiting here for a few days and you haven't sent your solution.
02.10.2004 22:14
I have not time at the moment.
08.10.2004 19:07
Well please send your solution. I'm in a hurry.
09.10.2004 14:08
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
09.10.2004 17:51
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$.
10.10.2004 11:19
Well I'm so sorry. This is my second fault. The polynomial is monic.
10.10.2004 11:28
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.
10.10.2004 16:09
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$.
24.12.2004 01:06
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).