2
$\begingroup$

If $N= (\underbrace{323232 \cdots}_{50 \text{ digits}})_9$ (i.e in base $9$) then how to find the remainder when this $N$ is divided by $8$?

I am looking for a "fast" approach that could be used to solve this in less than $2$ minutes.

  • 0
    @Sasha:No,you didn't miss the question.I just can't see this solution before :/2011-08-26

2 Answers 2

7

The same way we find the remainder of dividing a number by $9$ when the number is written in base 10: add the digits.

Why?

Because remember that writing, say, $(38571)_9$ "really" means $1 + 7\times 9 + 5\times 9^2 + 8\times 9^3 + 3\times 9^4.$ When you divide $9$ by $8$, the remainder is $1$; when you divide $9^2$ by $8$, the remainder is $1^2 = 1$; then you divide $9^3$ by $8$, the remainder is $1^3=1$, etc. So the remainder of this number when divided by $8$ is the same as the remainder of $1 + 7\times 1 + 5\times 9^2 + 8\times 1^3 + 3\times 1^4$ which is the same as the remainder of $1+7+5+8+3 = 24$, which is $0$.

In this case, you have the digits $3$ and $2$, each of them $25$ times, so the remainder when dividing by $8$ is the same as the remainder of $(2+3)\times 25 = 125$ when divided by $8$, which is $5$.

(More generally, the remainder of dividing the number $(b_1b_2\cdots b_k)_b$ by $b-1$ is the same as the remainder of dividing the sum of the base $b$ digits, $b_1+b_2+\cdots+b_k$ by $b-1$).

(Even more generally, the remainder of dividing $(b_1b_2\cdots b_k)_b$ by any divisor of $b-1$ is the same as the remainder of dividing the sum of the base $b$ digits $b_1+b_2+\cdots + b_n$ by that number. That's why you can add the digits of a number in base 10 to find the remainders modulo $9$ or to find the remainders modulo $3$).

  • 1
    @Foo One key thing to keep in mind is that radix notation has *polynomial* form, so this can be viewed as a special case of well-known results about polynomials. Always be on the lookout for *analogies* between *numbers* and *functions* (here polynomials).2011-08-26
1

HINT $\ $ Employ the radix $\:9\:$ analog of casting out nines in decimal, namely

$\rm\quad mod\ 8:\ \ \ 9 \equiv 1\ \ \Rightarrow\ \ d_n\: 9^n +\:\cdots\:+d_1\:9 + d_0\ \equiv\ d_n +\:\cdots\:+d_1+d_0$

The same idea works generally to cast out $\rm\:b\pm1\:$'s in radix $\rm\:b\:$, e.g. see here for many links.

It may be viewed as a number-theoretic specialization of the Polynomial Remainder Theorem

$\rm\quad f(x)\ mod\ (x-r)\:=\:f(r)\:,\ $ thus $\rm\ \ f(x)\ mod\ (x-1)\:=\:f(1)\: =\: f_n +\:\cdots\:+f_1 + f_0$