Long Division in Base 36

Date: 11/05/2003 at 07:12:21
From: Nick
Subject: Divsion in a base 36 system

I am trying to use an "imaginary" system that is base 36 (ie. 1, 2, 3, 
4, 5, 6, 7, 8, 9, A=10, B=11, ..., Z=35) and I am struggling to divide 
one number in this system by another using long division.  I assume it 
would be similar to division in the hexadecimal system but I would be 
grateful for any help you could give me.

Cheers, Nick 

Date: 11/05/2003 at 12:56:58
From: Doctor Peterson
Subject: Re: Divsion in a base 36 system

Hi, Nick.

Have you seen our FAQ on bases, which includes links to answers on 
division?

  Number bases
    http://mathforum.org/dr.math/faq/faq.bases.html 

Division in any base uses exactly the same method; you just need a 
different multiplication table.  Base 36 is particularly awkward, 
since its table is so large; I would not actually write out a table 
(unless I had a sadistic teacher who made me do a lot of these!), but 
would just make a table to allow me to quickly convert digits to base 
ten, and then do the actual arithmetic in base ten where necessary.

So let's do it.  Here are the digits:

  0=0    A=10    K=20    U=30
  1=1    B=11    L=21    V=31
  2=2    C=12    M=22    W=32
  3=3    D=13    N=23    X=33
  4=4    E=14    O=24    Y=34
  5=5    F=15    P=25    Z=35
  6=6    G=16    Q=26
  7=7    H=17    R=27
  8=8    I=18    S=28
  9=9    J=19    T=29

Now let's first do a multiplication for practice; I'll multiply 4P by 
G3:

    4P
  * G3
  ----

Remember that

  4P = 4*36 + 25 = 169
  G3 = 16*36 + 3 = 579

So the answer should be

  169 * 579 = 97851

which we can convert back to base 36 by dividing by 36 repeatedly:

  97851 / 36 = 2718 rem 3
   2718 / 36 =   75 rem 18 = I
     75 / 36 =    2 rem 3
      2 / 36 =    0 rem 2

So our answer should come out to 23I3 (base 36). Let's see if we can 
do it.

We'll have to multiply four pairs of digits; let's translate each of 
those pairs into decimal, multiply, and convert back:

  3*P = 3*25 = 75 = 23
  3*4 = 12 = C
  G*P = 16*25 = 400 = B4
  G*4 = 16*4 = 64 = 1S

Now we use the usual algorithm to multiply:

    B
    2
    4P
  * G3
  ----
    E3 <- 3*4P
  234  <- G*4P
  ----
  23I3

Good. We can multiply successfully!

Now let's reverse that and divide 23I3 by 4P. We should get G3.
     _______
  4P ) 23I3

We first have to estimate 23I/4P, which we can do by finding 23/4. In 
decimal, that is 75/4, which is about 19, or J. Let's try J:

    D
    4P
  *  J
  ----
   2H7

That's bigger than 23I; the excess is E6, which is about 3 times 4P, 
so let's subtract 3 from J and try G:

    4P
  *  G
  ----
   234

That looks good; so we can use it:

     ____G__
  4P ) 23I3
       234
       ---
         E3

Now we have to divide E3 by 4P; E/4 = 14/4 (base 10) is about 3, so we 
try 3:

    4P
  *  3
  ---- 
    E3

Ah! It's exactly right:

     ____G3_
  4P ) 23I3
       234
       ---
         E3
         E3
         --
          0

So the answer is G3 (which we knew all the time, but ignored).

Now, everything I did here is exactly what I would have done if I were 
teaching you to divide in base ten, except that we had to convert 
numbers to base 36 to make our guesses (which we could have avoided if 
we had a whole multiplication table to work with), and had to multiply 
and subtract in base 36 to get the actual answers. It's very simple, 
but very ugly. And I'm doing it now so I can put it in our archive and 
never have to do it again!

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/