You don't have to do things in decimal, it's just convenient since you get the answer digit-by-digit.

The idea of long division is just that to solve A/B, we can find another problem C/B we know the answer to and break it into the smaller problem A/B = (A-C)/B + C/B.

For example, to solve 742/13, the normal way is to observe that 13×5=65 is as close as we can get to 74 without going over, so we can reduce this to

    742/13 = (742 - 13×50)/13 + 13×50/13
           = (742 - 650)/13 + 50
           = 92/13 + 50

Now we only have to solve the simpler problem 92/13. All the long division stuff is just a book-keeping method for this data.

But you could also use 13×4=52 and work out

    742/13 = (742 - 520)/13 + 40 = 222/13 + 40
    222/13 = (222 - 130)/13 + 10 =  92/13 + 10
     92/13 = ( 92 -  91)/13 +  7 =   1/13 +  7

This gives the same answer, but it goes 40->50->57. The normal long division goes 50->57, so it never "goes back" on a digit it has decided on.