1

An integer $N$, expressed in base $b$, is $6789$. If $N$ is a multiple of $b-1$, and $b$ is less than $16$, then what is the successor of $b$?

I couldn't develop anything more than $$N_b = \left(\;n\cdot (b-1)\;\right)_b = 6789_b$$ (with subscripts indicating "in base $b$").

Blue
  • 75,673
Lambert macuse
  • 4,266
  • I don't understand how you got that equation. I'm also not sure I understand what it means. Please use MathJax to format your posts. – saulspatz Aug 25 '19 at 00:49
  • The successor of $b$? Wouldn't that just be $b + 1$? Are you being as to solve for $b$? – fleablood Aug 25 '19 at 01:15
  • 2
    Are you familar with the rule of nines? (If a number is a multiple of $9$ then the sum of the digits is a multiple of $9$?) Are you familiar with the fact that it can be extended to any base $b$ for $b-1$? (If a number is a multiple of $b-1$ then the sum of its digits (in base $b$) is a multiple of $b-1$?) – fleablood Aug 25 '19 at 01:28

2 Answers2

3

It seems there are multiple answers.

Since $N$ can be written as $6789$ in base $b$ we know $$6b^3+7b^2+8b+9=N$$ If we divide this polynomial by $b-1$ we get $$6b^2+13b+21+\frac{30}{b-1}$$ but we know that $b-1$ divides $N$ so $\frac{30}{b-1}$ is an integer. $$b-1=1,2,3,5,6,10,15,30$$ $$b=2,3,4,5,7,11,16,31$$ but $b < 16$ and $b>9$ as noted by John Omielan hence $$b+1=12$$

Ryan
  • 1,691
  • 2
    Since the digits $6,7,8,9$ occur in base $b$, this means that $b \ge 10$. As such, the only valid value based on $b \lt 16$ is $b = 11$, so $b + 1 = 12$. Also, note that in general, if any number written in base $b$ is a multiple of $b - 1$, then the sum of the digits is a multiple of $b - 1$, with this being $6 + 7 + 8 + 9 = 30$ in this case. This corresponds to a number in base $10$ being a multiple of $9$ iff the sum of the digits is a multiple of $9$. – John Omielan Aug 25 '19 at 01:24
  • Very interesting. I've improved my answer. – Ryan Aug 25 '19 at 01:28
2

If $N$ is a multiple of $b-1$ then by the rule of nines[1] the sum of the digits is a multiple of $b-1$ as well.

So $b-1| 6+ 7 + 8 + 9 = 30$. So $ b-1 = 1,2,3,5,6,10,15,30$

Bu $9$ is a digit so $b\ge 10$. And $b < 16$ so $b-1 < 15$.

... so $b-1 < 15$ and so $b-1 =10$ and $b =11$ and then successor of $b$ is $12$.

[1] Rule of nines: $\sum_{k=0}^n a_k b^k \equiv \sum_{k=0}^n a_k \pmod {(b-1)}$.

Pf: $\sum_{k=0}^n a_k b^k - \sum_{k=0}^n a_k = \sum_{k= 0}^n a_k (b^k-1) $

Now each $b^0 - 1 = 0$ and $b^1 - 1 =b-1$ and for $k > 1$ then $b^k -1 = (b-1)(b^{k-1} + b^{k-1} + ...... + 1)$ so $b-1|b^k-1$. So $b-1|\sum_{k= 0}^n a_k (b^k-1)$

And so $\sum_{k=0}^n a_k b^k - \sum_{k=0}^n a_k\equiv 0 \pmod {(b-1)}$.

In other words, $N =\sum_{k=0}^n a_k b^k$ and the sum of the digits of $N$ (in base $b$) have the same remainder when divided by $b-1$.

And therefor $b-1|N$ if and only if $b-1|$ the sum of the digits if $N$ (in base $b$)

fleablood
  • 124,253
  • Rather coincidentally time-wise, your answer addresses the points I raised in my comment to the answer by Ryan Greyling at https://math.stackexchange.com/a/3333335 just only about a minute earlier. – John Omielan Aug 25 '19 at 01:28
  • I would hardly call two people solving a problem the same way a "coincidence". The "rule of nine" is fairly well known. – fleablood Aug 25 '19 at 01:30
  • I was referring particularly to the timing of your answer, as well as the content. I've edited my earlier comment to make this more explicit. – John Omielan Aug 25 '19 at 01:31