Let $a,b,n$ be positive integers, $b > 1$ and $b^n-1\mid a.$ Show that the representation of the number $a$ in the base $b$ contains at least $n$ digits different from zero.
Problem
Source: IMO Shortlist 1993, Romania 2, created by Radu Todor
Tags: number theory, representation, Divisibility, IMO Shortlist
25.03.2006 21:12
Please check if my proof is correct... We need to prove that for any integer $b>1$, $n$, and $c>0$, $c(b^n-1)$ has at least $n$ non-zero digits when written in base $b$. Let $c=\sum_{i=0}^{m} x_i b^i$, where $0\leq x_i<b$. We can use induction on $m$. If $m = 0$, then $c < b$, and $a=c(b^n-1)=cb^n-c=\overline{(c-1)(b-1)...(b-1)(b-c)}$ in base $b$, giving $n$ non-zero digits for $c=1$ and $n+1$ non-zero digits for $c>1$. Now assume $c(b^n-1)$ have at least $n$ non-zero digits for $m=k$, we want to prove the statement is true for $m=k+1$. Let $c=x_{k+1}b^{k+1}+c^'$, where $c^{'}=\sum_{i=0}^{k} x_i b^i$. Let $c^{'}(b^n-1)=\sum_{i=0}^{k+n} y_i b^i$, where $0\leq y_i<b$., then $a=x_{k+1}b^{k+n+1}+y_{k+n}b^{k+n}+...+y_{k+2}b^{k+2}+y_{k+1}b^{k+1}-x_{k+1}b^{k+1}+y_kb^k+...+y_0$. If $x_{k+1}=y_{k+1}$, $a$ would have the same number of zeros in base $b$ as $c^{'}(b^n-1)$, because one digit would be changed to zero and a non-zero digit would be added, without changing anything else. If $x_{k+1}<y_{k+1}$, we will get one more. If $x_{k+1}>y_{k+1}$, then we can replace $y_{k+1}-x_{k+1}$ by $y_{k+1}-x_{k+1}+b$ (a non-zero number) and work on coefficients of larger exponents to get all coefficients in range. This would mean decrease the first non-zero coefficient met when going left from exponent $k+1$ by 1 and change all zero coefficients met on the way to $b-1$. Obviously at most 1 coefficient is changed from non-zero to zero, but again, the added non-zero coefficient for exponent $k+n+1$ would offset this decrease. In conclusion, $c(b^n-1)$ would have at least as much non-zero digits as $c^{'}(b^n-1)$.
08.07.2006 10:52
We allow nubers in base b to have leading zeroes until their numer of digits in multiple of n. The value of a number with leading zeroes in the same as without zeroes. All operations will be in b base. Assume for the purpose of contradiction that there exist a multiple of $b^{n}-1$ with less than n nonzero digits. It is easy to prove that if $g(t)$ is the number of nonzero digits of $t$ then $g(s+t)\le g(s)+g(t)$. And if $g(t),g(s)>0$ then $g(s+t)>0$ Given $s=a_{1}a_{2}...a_{kn}$ a number multiple of $b^{n}-1$ we split his digits into blocks of n digits $c_{1}=a_{1}....a_{n}$, $c_{2}=a_{n+1}...a_{2n},...,c_{k}=a_{nk-n+1}....a_{n}$ . It is easy to see that $s'=c_{1}+c_{2}+c_{3}+...+c_{k}\equiv s (\mod b^{n}-1)$ and $s'$ is strictly less than $s$ if s have more than n digits. Cotinuing this transformation we will get smaler and smaler s's until they have less than or exactly n digits. Now it is obvious that a number $s$ with $\le n$ digits and $<$ nonzero digits cannot be a multiple of $b^{n}-1$ because $0<s<b^{n}-1$. We got the desired contradction.
03.07.2014 21:35
Is this a valid proof: Let $a=k(b^n-1)$, where $k$ has $x$ nonzero digits and $y$ zeros in base $b$. Also assume that $k$ has no trailing zeros because, if it did, we can simply consider the same number without the zeros and then multiply them in later for no net effect. Then, if you consider the subtraction of $k(b^n)$ by $k$ in base $b$, we have that $k(b^n)$ is $k$ followed by $n$ zeros, and $k$ is simply $k$. Thus, when we subtract, we carry over a $1$, and all the zeros but the last one become a $(b-1)$. All the $(n-(x+y))$ $(b-1)$'s will stay that way and the $x$ nonzero digits on top will stay nonzero, and the $y$ zeros on bottom will become $(b-1)$'s. Thus, we have at least $(n-(x+y))+x+y=n$ nonzero digits, as desired. Note: This is much easier to follow if you write out the two column subtraction, but I don't know how to align that in latex...