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.

  • 1
    This is computing $N\mod 8$. Since the $9\mod 8 \equiv 1$, this is just the sum of digits of the number $N$, i.e. $(3+2)\times 25\mod 8 \equiv (3+2)\times 1\mod 8 = 5$. Did I miss the question ?2011-08-26
  • 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$).

  • 0
    I feel like stupid now,the first general result is not new to me and could be easily be shown as follows:$N = (a_1a_2\cdots a_k)_r = a_k + \cdots +a_2 \times r^{k-2} + a_2 \times r^{k-1}$ and $ S = a_1 + a_2 + \cdots a_k$ then it could be easily shown that $\frac{N-S}{r-1} = I \text{ (an integer) }+\frac{S}{r-1}$,which proves that result. But I don't know why I can't see this direct application before! :/2011-08-26
  • 0
    Anyways,the more general result is new to me,and perhaps a very useful one,could you hint me a *easy* proof for the same?2011-08-26
  • 0
    @FoolForMath The key idea is to learn modular arithmetic and, more generally, modular reductions of problems in quotient algebras. It's one way to algebraically *divide and conquer*. You can find further discussion of such in some of my posts here if you follow the link I gave, and its links...2011-08-26
  • 0
    I understood it now :D and it was before Bill Dubuque's post :-) but yes Bill you are right,my understanding is due to modular arithmetic.2011-08-26
  • 0
    @Foo So you knew modular arithmetic before posting, but it was not clear how to apply it here?2011-08-26
  • 0
    @Bill Dubuque:Yes I knew modular arithmetic before I made this post and the first general result too(from Higher algebra classes),but may be due of lack of sufficient practice of this theory,I didn't see the *direct* application :/2011-08-26
  • 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$