Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.