# Binary division - find a remainder

I have difficulty in finding the remainder of the next expression: 111010011/1101.

What I did:

111010011/1101
1101
---------
001100
1101
---------
0001101
1101
---------
0000


So the remainder is 0 (which is not correct). Where did I go wrong?

-

You made several mistakes. Remember that in normal subtraction, you also don't have $123 - 456 = 777$. You have to carry the bits you lose from right to left to get a proper subtraction. And you have to subtract the highest power-$2$ multiple of $1101$ possible on each step, but $1101$ does not "fit" in $1100$ (as you did in the second line).

In any case, here's a proper division with remainder.

$$\begin{matrix} \color{green}{1} & \color{green}{1} & \color{green}{1} & \color{green}{0} & \color{green}{1} & \color{green}{0} & \color{green}{0} & \color{green}{1} & \color{green}{1} & \\ \color{red}{1} & \color{red}{1} & \color{red}{0} & \color{red}{1} & & & & & \\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & \\ & & & & \color{red}{1} & \color{red}{1} & \color{red}{0} & \color{red}{1} & \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & \\ & & & & & \color{red}{1} & \color{red}{1} & \color{red}{0} & \color{red}{1} \\ \hline 0 & 0 & 0 & 0 & 0 & \color{blue}{1} & \color{blue}{1} & \color{blue}{0} & \color{blue}{0} & \\ \end{matrix}$$

So $\color{green}{111010011} = (100000 + 10 + 1) \cdot \color{red}{1101} + \color{blue}{1100}$, i.e. the remainder is $\color{blue}{1100}$.

We can verify the above by converting to decimal representations, in which case we get $\color{green}{467} = (32 + 2 + 1) \cdot \color{red}{13} + \color{blue}{12}$.

-