Let $a,b,n$ be integers greater than $1$. Suppose $(b^n-1)|a$. Prove that the integer $a$ represented in base $b$ has at least $n$ non-zero digits.

I observe that $b^n\equiv 1 \pmod{b^n-1}$ and $a\equiv 0\pmod{b^n-1}$. Write $a=a_mb^{m}+a_{m-1}b^{m-1}+\cdots + a_1b+a_0$, where $a_i\in \{0,1,2,\cdots, b-1\}$. Instead of proving it has at least $n$ digits not equal to zero, I tried to prove that at most $m-n$ digits are zero. But then I could not make any substantial progress.


1 Answer 1


Write $a = a_m b^m + \cdots + a_1 b + a_0$ in base $b$, as in the question. I'll prove a different statement: the base-$b$ digit sum of $a$ must be at least $n(b-1)$. This easily implies the original statement, because each digit is at most $b-1$.

The key idea is that we can test divisibility by $b^n-1$ by taking the digit sum in base $b^n$ instead of $b$, repeatedly if necessary. (This is analogous to the usual base-10 test for divisibility by $9$. The precise statement is that the digit sum of $a$ in base $b^n$ is congruent to $a$ modulo $b^n-1$, so one is divisible by $b^n-1$ if and only if the other is.) So if we take the digit sum in base $b^n$ repeatedly until there is only one digit left, this digit must be $b^n-1$.

To finish the proof, we observe that when taking digit sums in base $b^n$, we can never increase a number's digit sum in base $b$. To see this, recall that the base-$b^n$ representation is $(a_0 + a_1 b + \cdots + a_{n-1} b^{n-1}) + (a_n + a_{n+1} b + \cdots + a_{2n-1} b^{n-1}) b^n + \cdots$, whose base-$b^n$ digit sum is $(a_0 + a_n + \cdots) + (a_1 + a_{n+1} + \cdots) b + \cdots + (a_{n-1} + a_{2n-1} + \cdots) b^{n-1}$. If there is no carrying when adding this in base $b$, then the base-$b$ digit sum will remain the same, i.e. $a_0 + \cdots + a_m$, but carrying can only reduce it. So the base-$b$ digit sum of $a$ must have been greater than or equal to the base-$b$ digit sum of $b^n-1$, namely $n(b-1)$, and we are done.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .