How can I adapt the long division algorithm to other bases?

Question

How can I use "long division" in such a way as to get the n-ary expansion of a rational number instead of the decimal expansion? E.g. what would the long division of 866/5 look like in base 7? I'm working on showing that a number is in Q iff it has a terminating or periodic p-adic expansion, but I'm having trouble with that so I'm going over the fundamentals.

Answer 1

What follows is the long division base $7$: for example in an early row using $5 \times 3=2\times7 + 1 = 21_7$. Since the remainder starts to repeat, you get the periodic result $\frac{866_{10}}{5}=\frac{2345_7}{5}=335.\overline{1254}_7$.

Since there is a finite number of possible remainders, they must repeat and so you must get a periodic result for any rational in any base (counting terminating results as periodic $0$s). Jyrki Lahtonen's comment gives an approach which can help determine the length of the period.

       335.1254...
     ==========
  5 | 2345
      21             5×3
      ----  
       245
       21            5×3
       --- 
        35
        34           5×5
        --  
         1
         0.5         5×1
         ---
         0.2
           13        5×2
         ----
            4
            34       5×5
            --
             3
             26      5×4
             -- 
              1      repeated remainder